九州大学学術情報リポジトリ
Kyushu University Institutional Repository
構造化・非構造化データの特異な部分構造の検出
谷口, 雄太
https://doi.org/10.15017/1441267
出版情報：Kyushu University, 2013, 博士（情報科学）, 課程博士 バージョン：
権利関係：Fulltext available.
構造化・非構造化
特異 部分構造 検出
谷口 雄太
2014 年 2 月
要旨
人類 蓄積 膨大 量 及 ， 蓄積 利活用 基盤
技術 確立 強 求 ． ，内容・形式 多岐 渡
，大 構造化 非構造化 2 分 ．非構造化 ，
例 文書 ，音声 自然現象 観測 時系列
． 明示的 構造 ，連続 記号 事象 単純 列，
，文字列 見 ．他方，構造化 ，例 原子同士 結合 表 分子構造，論文 共著関係 人間同士 関係 表
． 明示的 構造 多 ，異 2 実体間 関係 集
， ， 見 ．今日 ，文字列 ，計算機科学
様々 抽象的 取 扱 基本的 表現 用 ．
大量 利活用 ，構造化・非構造化 ，
中 埋没 高次 部分構造 捉 重要 ．例 ，
文字 並 ， 意味 把握 場合 単語 列 見 必要 ， 高次 意味 捉 ，文 列 ， 高次 構造 解析 必要 出
．同様 ，例 ， 中 築 見
社会学， 有用 ．
部分構造 検出 関 既存研究 多 ，部分構造 特異性 基 検出 行 ． 既存手法 ，専門家 領域知識 利用 以外
分 ．前者 ，領域知識 活用 精度 高 反
面， 高 ，未知 対応 問題 ．一方，後者 大
未知 含 様々 普遍的 適用 ， 発見的 結果
期待 ．本研究 ，構造化・非構造化 対 ，
隠 部分構造 後者 検出 問題 取 組 ． 結果， (1) Purity
尺度 配列上 水平伝播遺伝子 発見， (2) 大 文
字列 対 Purity 尺度 改良， (3) 対 頑健 手法 提
案， 研究成果 ．
(1) ，文字列 部分文字列 特異性 測 尺度 ， Yamada (2012)
提案 Purity 尺度 着目 ，複数 細菌 配列 Purity 尺度 水平伝
播遺伝子 呼 遺伝子 特徴付 明 ．細菌 微生物 ，通 常 生殖 異 遺伝子伝播 水平伝播 存在 ．水平伝播 獲 得 遺伝子 特定 ， 理解 進化 過程 解明 繋 重要視
．本研究 ，実験 配列 配列注釈 用 評価 通 ， RNA
， ，水平伝播 考 遺伝
子 ， Purity 尺度 高 与 確 ．
(2) ，短 部分文字列 対 Purity 尺度 問題点 指摘 ， 克服 新
尺度 Atomicity 尺度 提案 ． 配列 4 種類程度 記号 記述
，解析 対象 比較的長 部分文字列 ．一方，英文
文字列 多 記号 使 ，情報 短 文字列 記述 ，
比較的短 部分文字列 解析 対象 ．対象 部分文字列 短
場合， Purity 尺度 値 特定 値 集中 短 部分文字列 差別化
問題 ．本研究 提案 Atomicity 尺度 ， 問題 改善
．英文 中 単語 文字 実験 ， Purity 尺度 差別化
部分文字列 Atomicity 尺度 差別化 確認 ．
(3) ， 頂点 問題 対 ，巨視的構造 呼 粗視化 導入 ，既存手法 比 頑健 手法 提案 ．
問題 定式化 種々 問題 中 ， 間 多数 辺 ( )
扱 場合 ．本研究 ，巨視的構造 呼
間 関係性 記述 導入 ， 間 辺 絶対数 左右 ， 間 内 辺密度 差 依存 手法 提案 ．人工
実 用 実験 ，提案手法 多 上 既存手法 凌
性能 示 ．
謝辞
本研究 遂行 多 方々 支援 ， 無 不可能 ． 場 借 感謝申 上 ．
学部 4 年次 現在 至 ，終始研究 御指導 賜 九州大学大学院 情報科学研究院 池田大輔准教授 心 感謝申 上 ． ，本論文
，貴重 御助言 頂 九州大学大学院 情報科学研究院 竹田正幸教授，
瀧本英二教授 深 感謝申 上 ．特 配列 分析 ，九州大学大学院 農学研究院 久原哲教授，九州大学 ・ ・ 研究所 丸山修准教授 貴重 御助言 頂 ．深 感謝申 上 ．
，事務手続 全般 支援 頂 秘書 方々 感謝申 上 ．研究 議論 雑談 至 ， 愉快 時間 共 過 頂 池田研究室，鈴木研究室，
瀧本研究室 先輩方，後輩 感謝申 上 ．
最後 ，博士課程修了 至 経済的 支援 行 ， 変 愛情 注
両親 感謝申 上 ．
目次
第 1 章 序論 8
1.1 背景 . . . . 8
1.2 主結果 . . . . 9
1.3 本論文 構成 . . . . 10
第 2 章 Purity 尺度 領域 適用 水平伝播遺伝子 発見 11 2.1 背景 . . . . 11
2.2 関連研究 . . . . 12
2.3 手法 . . . . 13
2.3.1 Purity 尺度 . . . . 13
2.3.2 Blumer 部分文字列 . . . . 14
2.4 結果 考察 . . . . 15
2.4.1 . . . . 15
2.4.2 機能別 評価 . . . . 18
2.4.3 水平伝播遺伝子検出性能 . . . . 25
2.5 結論 . . . . 26
第 3 章 大 文字列 対 Purity 尺度 改良 27 3.1 背景 . . . . 27
3.2 手法 . . . . 29
3.3 実験 . . . . 29
3.3.1 20 Newsgroups . . . . 30
3.3.2 Brown . . . . 33
3.4 結論 . . . . 36
第 4 章 巨視的構造 最適化 基 37
4.1 背景 . . . . 37
4.2 関連研究 . . . . 39
4.2.1 先行研究 . . . . 40
4.2.2 分類手法 HITS . . . . 41
4.3 手法 . . . . 41
4.3.1 問題定義 . . . . 41
4.3.2 巨視的構造 . . . . 42
4.3.3 最適化 . . . . 43
4.4 実験 . . . . 44
4.4.1 評価 . . . . 44
4.4.2 実験環境 . . . . 45
4.4.3 実験 1: 多様 量 持 対 網羅的調査 . . . . . 46
4.4.4 実験 2: 応用 . . . . 50
4.5 結論 . . . . 54
第 5 章 結論 55
参考文献 57
図目次
2.1 閾値以上 Purity 値 部分文字列 数 変化 . . . . 17
2.2 見方 . . . . 18
2.3 E. coli K-12 [GenBank:NC_000913] . . . . 19
2.4 E. coli O157:H7 [GenBank:NC_002695] . . . . 20
2.5 G. metallireducens [GenBank:NC_007517] . . . . 21
2.6 M. mycoides [GenBank:NC_015431] . . . . 22
2.7 F 値 . . . . 24
2.8 F 値 高 Purity 値 . . . . 24
2.9 F 値 低 Purity 値 . . . . 25
3.1 Purity 値 分布 . . . . 33
3.2 Atomicity 値 分布 . . . . 34
4.1 巨視的構造 . . . . 38
4.2 適用 . . . . 42
4.3 人工 生成過程 . . . . 46
4.4 生成 人工 例 . . . . 47
4.5 提案手法 結果 . . . . 48
4.6 各 性能 比較 . . . . 49
4.7 変換 . . . . 51
4.8 人工 対 結果 . . . . 52
4.9 Iris 対 結果 . . . . 53
表目次
2.1 実験 用 細菌 配列 一覧 . . . . 16
2.2 水平伝播遺伝子 検出性能 評価結果 . . . . 26
3.1 Purity 尺度 単語列 ( ) 評価例 . . . . 28
3.2 Purity 尺度・ Atomicity 尺度 評価結果 . . . . 31
3.3 Atomicity 尺度 評価結果 . . . . 35
第 1 章
序論
1.1 背景
普及， 整備，多様 機器 導入，
化 動 ，人類 創出 量 加速度的 増加 ，蓄積
膨大 量 及 ． ， 蓄積 利活用 基盤技術 確立 強
求 ． ，内容・形式 多岐 渡 ，大 構
造化 非構造化 2 分 ．非構造化 ，例 文書
，音声 自然現象 観測 時系列 ． 明
示的 構造 ，連続 記号 事象 単純 列， ，文字列 見
．他方，構造化 ，例 Web 間 関係
表 Web ，原子同士 結合 表 分子構造，論文 共著関係 人間同士 関係
表 ，言葉同士 類義関係 表 WordNet ．
明示的 構造 多 ，異 2 実体間 関係 集 ，
， 見 ．今日 ，文字列 ，計算機科学
様々 抽象的 取 扱 基本的 表現 用 ．
大量 利活用 ，構造化・非構造化 ，
中 埋没 高次 部分構造 捉 重要 ．例 ，
文字 並 ， 意味 把握 場合 単語 列 見 必要 ， 高次 意味 捉 ，文 列 ， 高次 構造 解析 必要 出
．同様 ，例 ， 中 築 見
社会学， 有用 ．
部分構造 検出 関 既存研究 多 ，部分構造 特異性 基
検出 行 ． 既存手法 ，専門家 領域知識 利用 以
外 分 ．前者 ，例 既存 解析済 比較 行
特異 部分 検出 行 ． 領域知識 活用 検出 精度 高
，同時 高 必要 ， 未知 対応 問題
．一方，後者 多 場合，解析対象 用 ，
部分 特異性 直接的 評価 ． 方法 既知 比較 行
， 抑 ， 未知 発見的 結果 期待
．本研究 構造化・非構造化 対 ， 隠 部分構造
後者 検出 問題 取 組 ．非構造化 ， 配列
対象 ， 構造化 対象 ．
1.2 主結果
本研究 貢献 次 3 構成 ． (1) Purity 尺度 配列上 水平伝
播遺伝子 発見 [39] ， (2) 大 文字列 対 Purity 尺度 改
良 [46] ， (3) 対 頑健 手法 提案 [38] ． (1) ，文字列 部分文字列 特異性 測 尺度 ， Yamada [44] 提
案 Purity 尺度 着目 ，複数 細菌 配列 Purity 尺度 水平伝播
遺伝子 呼 遺伝子 特徴付 明 ．細菌 微生物 ，通常 生殖 異 遺伝子伝播 水平伝播 存在 ．水平伝播 獲得
遺伝子 特定 ， 理解 進化 過程 解明 繋 重要視
．本研究 ，実験 配列注釈 用 評価 通 ，
RNA ， ，水平伝播 考
遺伝子 ， Purity 尺度 高 与 確 ．
(2) ，短 部分文字列 対 Purity 尺度 問題点 指摘 ， 克服 新
尺度 Atomicity 尺度 提案 ． 配列 4 種類程度 記号 記述
，解析 対象 比較的長 部分文字列 ．一方，英文
文字列 多 記号 使 ，情報 短 文字列 記述 ，
比較的短 部分文字列 解析 対象 ．対象 部分文字列 短
場合， Purity 尺度 値 特定 値 集中 短 部分文字列 差別化
問題 ．本研究 提案 Atomicity 尺度 ， 問題 改善
．英文 中 単語 文字 実験 ， Purity 尺度 差別化
部分文字列 Atomicity 尺度 差別化 確認 ．
(3) ， 頂点 問題 対 ，巨視的構造 呼 粗視化 導入 ，既存手法 比 頑健 手法 提案 ．
問題 定式化 種々 問題 中 ， 間 多数 辺 ( )
扱 場合 ．本研究 ，巨視的構造 呼
間 関係性 記述 導入 ， 間 辺 絶対数 左右 ， 間 内 辺密度 差 依存 手法 提案 ．人工
実 用 実験 ，提案手法 多 上 既存手法 凌
性能 示 ．
1.3 本論文 構成
次章以降，本論文 次 構成 ． 第 2 章 Purity 尺度 配 列 適用 ．次 ，第 3 章 Purity 尺度 適用 ， 新 尺度 提案
． 第 4 章 問題 対 手法 提案 ．最後 第 5 章
結論 述 ．
第 2 章
Purity 尺度 領域 適用
水平伝播遺伝子 発見
2.1 背景
解析 配列 構造 機能的 領域 解明 確立
．従来， 配列 解析 ， 隠
頻繁 用 [8] ． 機能的領域 同定 関 成功 収
．
Yamada [44] 分野 Purity 尺度 提案 ．
与 文字列 部分文字列 対 ， 特異性 測 尺度 ．彼 Purity 尺 度 日本語 対 適用 ． 結果，大学 名前
部分 高 与 示 ． 彼 配列 対 適
用 行 ． Escherichia coli Bacillus subtilis 配列 適用 結果，高
Purity 値 領域 多 RNA 遺伝子 対応
示 ．
注目 ， 遺伝子 水平伝播遺伝子 [22] 考 ， Purity 尺度 特徴付 可能性 示唆 点 ．遺伝子 水平伝播 突然変異 比 大 変化 ，細菌 遺伝的多様性 主要 原因 1 考
[10] ． 水平伝播遺伝子 微生物 進化 密接 関 ，
特定 重要 ． ， Yamada [44] 実験 ，最 高
Purity 値 与 100 個 領域 評価 ，示唆 限定的
． ， Purity 尺度 種類 遺伝子領域 同定 ，広
調査 意義 ．
本論文 Purity 尺度 細菌 配列 対 有効性 ， 広範 渡 調査
．先行研究 [44] ， RNA Purity 尺度 特徴付
， 加 高 Purity 値
新 示 ．面白 ，新 見 遺伝子 水平伝播遺伝
子 考 [18, 45] ．従 ， 事実 Purity 尺度 水平伝播遺伝子 予測
有用 意味 ．
2.2 関連研究
領域 計算的 特徴付 大 2 分 ．生物学的
知識 基 組成 特徴 利用 ． 分類 下 ，
Purity 尺度 組成尺度 一種 考 ，後者 属 ．
前者 ，多 手法 異 領域知識 基 提案
．例 ， 相同性 [13, 25, 32] 特定 遺伝子 共通 構造 [28, 33]
． 手法 ，検出 領域 既知 領域 類似 領域 偏 傾向
，後者 比較 ，未知 機能的領域 発見 難 ．
他方，後者 ，特定 領域 組成 変異 特
徴付 ． ，単一塩基 組成 [1] ， 2 連塩基 存在量 [36] ，確率 [20] ，複雑
度 [21, 43] ，数多 組成 基 尺度 提案 ．通常 組成特徴
変異 ，平均的 組成 [1] 背景 配列 確率 [20] 「基準」 比較
測 ． 水平伝播遺伝子 特徴付 広 用
[7, 14, 31, 40] ．基本的 ， 手法 長 1 〜 3 程度 低次 連続塩基 組成
考 ．比較的長 程度 連続塩基 利用
[31] ，組成 考慮 連続塩基 長 限定 ．
対照的 Purity 尺度 ，任意 長 連続塩基 考慮 ． ，特定 基準 対
変異 測 代 ，普遍的 適用可能 仮定 基 ， Purity 尺度 水平伝播
遺伝子 上手 ， 頑健 特徴付 可能性 ．
2.3 手法
2.3.1 Purity 尺度
Purity 尺度 ，与 文字列 部分文字列 特異性 評価 尺度 ，「短
部分文字列 長 部分文字列 多 出現 」 仮定 基 ．例
，文字列 T 与 部分文字列 x 特異 評価 考 ． x 任意 部分文字列 y ，先 仮定 通常， T y 出現頻度 ，
T x 出現頻度 多 考 ． Purity 尺度 x 特異性 ，仮定 満
y 多少 定量化 ．仮定 反 y ，極端 場合 x 同頻
度 y ， x 固有 y ．
Purity 尺度 測 特異性 ，部分文字列 x 「 良 」 「分割不可能
性」 言 ．
Yamada [44] 具体的 Purity 尺度 定義 確率， 差 3
提案 ． 内， 1 目 尺度 彼 配列 対 実験 用
， RNA 特徴付 ． ，本研究 特 尺度
考 ，以降 単 Purity 尺度 呼 ．
Purity 尺度 形式的 以下 定義 ． N 非負整数 集合 ． Σ 文
字 有限集合 呼 ． 0 個以上 文字 有限列 集合 Σ
∗表記 ， 集合 要素 文字列 呼 ．文字列 x ∈ Σ
∗長 | x | 書
．長 n 文字列 x = a
1a
2· · · a
n∈ Σ
∗関 ，任意 正 整数 i 対 x
i 番目 文字 a
ix[i] 表記 ． ， i ≤ j 満 任意 正 整数 i , j 対 x
連続 部分 a
i· · · a
jx[i : j] 表記 ， x 部分文字列 呼 ．
文字列 x ∈ Σ
∗対 ， sub(x) 次 定義 ．
sub(x) = { ⟨ i , j ⟩ ∈ N
2| 1 ≤ i ≤ j ≤ | x | } 文字列 T , x ∈ Σ
∗対 ， pos
T(x) 次 定義 ．
pos
T(x) = { ⟨ i , j ⟩ ∈ sub(T ) | T [i : j] = x }
文字列 T , x ∈ Σ
∗対 ， freq
T( x) freq
T(x ) = pos
T( x) 定義 ．直感的 ，
sub( x) x 全 部分文字列 重複 含 集合， pos
T(x) x T 全 出
現位置 集合， freq
T(x) x T 出現頻度 表 ．例 、 sub(“aab”) =
{⟨ 1 , 1 ⟩, ⟨ 2 , 2 ⟩, ⟨ 3 , 3 ⟩, ⟨ 1 , 2 ⟩, ⟨ 2 , 3 ⟩, ⟨ 1 , 3 ⟩} ， pos
“aab”(“a”) = {⟨ 1 , 1 ⟩, ⟨ 2 , 2 ⟩} ， freq
“aab”(“a”) = 2
．
定義 1 入力文字列 T 部分文字列 x 与 ， x T Purity 値
次 定義 ．
purity
T(x ) = { ⟨ k , l ⟩ ∈ sub(x) | freq
T( x[k : l]) = freq
T( x) }
| sub(x) |
Purity 尺度 x 特異性 ， x 部分文字列 内， T 中 x 部分 出現
固有 「割合」 定量化 ．
接尾辞木 接尾辞配列 [17] 構造 用 ， T 全 Blumer 部
分文字列 Purity 値 ， T 長 関 線形時間・領域 計算 ． Blumer 部分文
字列 次節 詳述 ．
2.3.2 Blumer 部分文字列
Purity 尺度 入力文字列 部分文字列全 適用 ，最 高 Purity 値 部分文字
列 見 可能 ，入力長 2 乗 比例 膨大 数 部分文字列 人
手 評価 現実的 ． Blumer [4] 提案
同値関係 利用 冗長 部分文字列 削減 考 ．
文字列 T 与 ． T 部分文字列 x 対 ， ← → x = α x β 定義 ．
， x T 出現 常 α β x 接頭辞・接尾辞
， α, β 中 最 長 ． ， Blumer 同値関
係 ≡ ， x ≡ y ⇐⇒ ← → x = ← → y 定義 ． x 同値類 [x]
≡= { y | y ≡ x } ， 代表元 ← → x 定義 ． 代表元 一意 ，同値類 極大元
．例 ， T = “acgacctacga” ， ←→
“g” = ←−→
“cg” = ←−−→
“acg” = ←−−→
“cga” = ←−−−→
“acga” = “acga”
， 同値類 ， “acga” 代表元 ．
Blumer 同値類 数 ，最大 文字列 T 長 関 線形個 存在 ，従
同値類 代表元 Purity 尺度 対象 ，大 数 減
．以降 Blumer 同値類 代表元 Blumer 部分文字列 呼 ． ，
Purity 尺度 T 評価 意味 ， T 代表元 「 1 回
出現 部分文字列 同値類」 考 ．
2.4 結果 考察
本節 種類 遺伝子領域 Purity 尺度 特徴付 ，
領域 Purity 値 強 関連 ， 11 本 細菌 配列
対 実験 示 ． 実験 配列 機能的領域 高 精度 特定
狙 ．代 ，複雑 手続 行 ，様々 配列上
Purity 尺度 性能 視覚的・定量的 示 目的 ．
実験 手順 ， (1) 配列 Blumer 部分文字列 列挙， (2) Blumer 部分文字列
Purity 値 計算 ．実験後，出力 Blumer 部分文字列 Purity 値 ，
配列 付与 注釈 用 評価 ．使用 11 本 細菌 表 2.1 示
．表 ，評価 用 注釈 含 GenBank ID 示 ．
様々 「門」 幅広 生物種 選択 ，系統的 長
G + C 含量 様々 含 ．以下 実験 ， GenBank 記載
配列 一本鎖 用 ， 相補鎖 考 ．
図 2.1 閾値 ( 横軸 ) 大 Purity 値 部分文字列 数 ( 縦軸 ) 各
示 ．縦軸 対数軸 注意．全体 数百
万 Blumer 部分文字列 存在 ． 閾値 大 ， 大
Purity 値 Blumer 部分文字列 数 急激 減少 ， 限 数 Blumer
部分文字列 大 Purity 値 分 ．
全 実験 単一 Linux 上 行 ． Intel Core i7 3.4 GHz
16 GB 構成 ．先述 実験手続 C ++ 言語 実装 ，全
GCC 4.8.1 ．
2.4.1
評価 作成 ．対象 各 配列 ， GenBank
注釈 遺伝子， Blumer 部分文字列 Purity 値
上 並 表示 ，配列領域 機能 Purity 値間 関連 視覚的 理解 試
．図 2.2 見方 説明 ．作成
中 4 図 2.3 ， 2.4 ， 2.5 2.6 示 ．
1 本 配列 示 ，各行 3 「 」 構成
． 1 目 GenBank 記載 注釈 情報 示 ．
表 2.1: 実験 用 細菌 配列 一覧．各 配列 ， GenBank
ID ，長 ， G + C 含量 生物名 記載 ．幅広 門 様々 長 ， G + C
含量 含 選択 ．
ID 長 G + C
(%)
生物名
NC_000911.1 3,573,470 47.7 Synechocystis sp. PCC 6803
NC_000913.2 4,639,675 50.8 Escherichia coli str. K-12 substr. MG1655 NC_000964.3 4,215,606 43.5 Bacillus subtilis subsp. subtilis str. 168 NC_002695.1 5,498,450 50.5 Escherichia coli O157:H7 str. Sakai NC_002946.2 2,153,922 52.7 Neisseria gonorrhoeae FA 1090 NC_003228.3 5,205,140 43.2 Bacteroides fragilis NCTC 9343 NC_007517.1 3,997,420 59.5 Geobacter metallireducens GS-15 NC_008261.1 3,256,683 28.4 Clostridium perfringens ATCC 13124
NC_010572.1 8,545,929 72.2 Streptomyces griseus subsp. griseus NBRC 13350 NC_012973.1 1,576,758 39.2 Helicobacter pylori B38
NC_015431.1 1,153,998 23.8 Mycoplasma mycoides subsp. capri LC str. 95010
注釈 付 全 領域 機能 種類 7 分類 ．分類
注釈 特定 特徴修飾子 (feature qualifier) 値 (qualifier value) ，特定 機能 示
言葉 含 判断 基準 ．例 領域 注釈 ，単語 “phage”
修飾子値 部分 含 “function” ， “product” “note” 特徴修飾
子 場合，「 」 分類 ． 分類規則 説明 省略 ．次 ，
分類 注釈付 領域 分類 色 付 上 表示 ．
赤色， Rhs (rearrangement hot spot element [11, 19]) 橙色， 黄 色， ( 含 ) 緑色， tRNA 水色， rRNA 青色 示
． 他 分類 注釈付 領域 上 表示 ．「 他」以外 6
，水平伝播遺伝子 ， 挿入 関連 考 ．
2 目 ，重 l-mers 対 「局所 G + C 含量」 示 ．局
所 G + C 含量 ， l-mers 構成要素 “g” “c” 占 割合 ，水
平伝播遺伝子 特徴付 使 [14] ，参考 表示 ． ，
l = 1000 ． 上 ，各 l-mer G + C 含量 色付 ，最
●
●
● ● ● ● ● ●
●
●
●
●
● ● ● ● ● ● ● ●
●
●
● ● ● ● ● ●
●
●
●
●
● ● ● ● ● ●
● ●
●
●
● ● ● ● ● ● ● ●
●
●
● ● ● ● ● ●
● ●
●
●
● ● ● ● ● ● ● ●
●
●
● ● ● ● ● ● ●
●
●
●
● ● ● ● ● ●
● ●
●
●
● ● ● ● ● ● ● ●
●
●
● ● ● ● ● ●
● ●
NC_000911.1 NC_000913.2 NC_000964.3 NC_002695.1
NC_002946.2 NC_003228.3 NC_007517.1 NC_008261.1
NC_010572.1 NC_012973.1 NC_015431.1
1e+02 1e+04 1e+06
1e+02 1e+04 1e+06
1e+02 1e+04 1e+06
0.2 0.4 0.6 0.8 0.2 0.4 0.6 0.8 0.2 0.4 0.6 0.8 Purity threshold
Number of Patterns
図 2.1: 閾値以上 Purity 値 部分文字列 数 変化．横軸 Purity 値 閾値，
縦軸 閾値以上 Purity 値 部分文字列 数 対数 ．
大値 1 l-mer 赤色 ，最低値 0 l-mer 緑色 示 ． 色付
凡例 下部 示 ．
最後 3 目 ， Blumer 部分文字列 対応 領域 対 ，部分文字列
「 Purity 値」 示 ． Purity 値 G + C 含量 同 0 1 実数 ，同
様 色付 行 ． ，最大値 (1) 場合 赤色 ，最低値 (0) 場合
緑色 示 ．図 2.3 ，表示 Blumer 部分文字列 Purity 値 最低値 閾
値 設 ，全 Blumer 部分文字列 表示 ． 以外 Purity 値
0 . 5 以上 Blumer 部分文字列 表示 ．
Purity 尺度 RNA ， Rhs 分類 領域 非
常 上手 捉 分 ． 機能的領域 通
常多数 Blumer 部分文字列 集団的 被覆 ， 少数 Blumer 部分文
字列 領域全体 被覆 稀 ．全体 覆 尽 程 ，
領域 高 Purity 値 Blumer 部分文字列 集 ．
対照的 ，局所 G + C 含量 水平伝播遺伝子 領域 程強 結
0 30000 60000 90000 120000
300000 330000 360000 390000 420000
Annotations (1st track)
Local G+C % (2nd track) Found paerns (3rd track) Positions
Mobile elements Rhs
Phage
Transposon tRNA rRNA Coloring of functional regions:
図 2.2: 見方．左図 一部 示 ， 構造 説
明 ．最上段 機能的領域 色 付 示 ．色 機能
対応 右図 示 ．
分 ． Purity 尺度 配列 対 同様 ，水
平伝播遺伝子 領域 対応 Blumer 部分文字列 高 Purity 与 ，値 変異 領域 特有 ．一方，局所 G + C 含量 機能性 関係 変異 ，水平伝播
遺伝子 特徴付 ．
Blumer 部分文字列 水平伝播遺伝子 間 強 関連性 無 図 2.3 読
取 ． 全 Blumer 部分文字列 Purity 値 示 ． 3
目 全体的 通 色 ， Blumer 部分文字列 配列
全体 渡 存在 意味 ， Blumer 部分文字列 水平伝播遺伝子
特有 分 ． ，大部分 Blumer 部分文字列 緑色 ，
Blumer 部分文字列 必 高 Purity 値 分 ．従 ，
特 Purity 尺度 水平伝播遺伝子 捉 言 ．
2.4.2 機能別 評価
本節 ， 示 Purity 値 領域 特定 機能
関連性 ，定量的 評価 ． ， GenBank 注釈 各領域
， 領域 最 被覆 最適 Blumer 部分文字列 求 ．
後，対応付 注釈付 領域 Blumer 部分文字列 組全 ，領域 分類 部分文字列 Purity 値 関連 分析 ． ，分類 先 説明 7 種類 用 ．
領域 対 部分文字列 被覆 良 評価 ，情報検索 分野
利用 F 尺度 用 ． 配列 T ∈ Σ
∗， 機能的領域
r = ⟨ i , j ⟩ ∈ sub(T ) 対 ， 配列 T 部分文字列 x F 値 F (x , r ) 次
図 2.3: E. coli K-12 [GenBank:NC_000913] ．全 Blumer 部 分 文 字 列 Purity 値 従 表 示 ．
Purity�/�Local�G+C�(%) 0.000.050.100.150.200.250.300.350.400.450.500.550.600.650.700.750.800.850.900.951.00
04000080000120000160000200000240000280000320000360000 400000440000480000520000560000600000640000680000720000760000 80000084000088000092000096000010000001040000108000011200001160000 1200000124000012800001320000136000014000001440000148000015200001560000 1600000164000016800001720000176000018000001840000188000019200001960000 2000000204000020800002120000216000022000002240000228000023200002360000 2400000244000024800002520000256000026000002640000268000027200002760000 2800000284000028800002920000296000030000003040000308000031200003160000 3200000324000032800003320000336000034000003440000348000035200003560000 3600000364000036800003720000376000038000003840000388000039200003960000 4000000404000040800004120000416000042000004240000428000043200004360000 4400000444000044800004520000456000046000004640000468000047200004760000 4800000484000048800004920000496000050000005040000508000051200005160000 520000052400005280000532000053600005400000544000054800005520000
図 2.4: E. coli O157:H7 [GenBank:NC_002695] ． Purity 値 0.5 以 上 Blumer 部 分 文 字 列 表 示 ．
Purity�/�Local�G+C�(%) 0.000.050.100.150.200.250.300.350.400.450.500.550.600.650.700.750.800.850.900.951.00
0300006000090000120000150000180000210000240000270000 300000330000360000390000420000450000480000510000540000570000 600000630000660000690000720000750000780000810000840000870000 900000930000960000990000102000010500001080000111000011400001170000 1200000123000012600001290000132000013500001380000141000014400001470000 1500000153000015600001590000162000016500001680000171000017400001770000 1800000183000018600001890000192000019500001980000201000020400002070000 2100000213000021600002190000222000022500002280000231000023400002370000 2400000243000024600002490000252000025500002580000261000026400002670000 2700000273000027600002790000282000028500002880000291000029400002970000 3000000303000030600003090000312000031500003180000321000032400003270000 3300000333000033600003390000342000034500003480000351000035400003570000 3600000363000036600003690000372000037500003780000381000038400003870000 39000003930000396000039900004020000
図 2.5: G. metallir educens [GenBank:NC_007517] ． Purity 値 0.5 以 上 Blumer 部 分 文 字 列 表 示 ．
Purity�/�Local�G+C�(%) 0.000.050.100.150.200.250.300.350.400.450.500.550.600.650.700.750.800.850.900.951.00
080001600024000320004000048000560006400072000 800008800096000104000112000120000128000136000144000152000 160000168000176000184000192000200000208000216000224000232000 240000248000256000264000272000280000288000296000304000312000 320000328000336000344000352000360000368000376000384000392000 400000408000416000424000432000440000448000456000464000472000 480000488000496000504000512000520000528000536000544000552000 560000568000576000584000592000600000608000616000624000632000 640000648000656000664000672000680000688000696000704000712000 720000728000736000744000752000760000768000776000784000792000 800000808000816000824000832000840000848000856000864000872000 880000888000896000904000912000920000928000936000944000952000 96000096800097600098400099200010000001008000101600010240001032000 1040000104800010560001064000107200010800001088000109600011040001112000 112000011280001136000114400011520001160000
図 2.6: M. mycoides [GenBank:NC_015431] ． Purity 値 0.5 以上 Blumer 部分文字列 表示 ．
定義 ． F( x , r ) = max
{ H
( overlap( ⟨ i , j ⟩, ⟨ k , l ⟩ )
j − i , overlap( ⟨ i , j ⟩, ⟨ k , l ⟩ ) l − k
)
∀⟨ k , l ⟩ ∈ pos
T( x) }
H(p , q) = 2pq p + q overlap( ⟨ a , b ⟩, ⟨ c , d ⟩ ) =
{ min(b , d) − c + 1 (a ≤ c ≤ b) min(b , d) − a + 1 (c ≤ a ≤ d)
．簡単 言 ， F 値 部分文字列 x 領域 r 重 大 大 程高 値 ．極端 場合，例 x r 一致 場合 F 値 1 ， x r 重
場合 0 ．
F 値 分布 図 2.7 示 ．図 F 値 ，対象 11 本
配列 機能的領域 最適 Blumer 部分文字列 組全 総合 作成
． 横軸 F 値，縦軸 範囲 F 値 領域 部分文字列 組
数 対応 ．領域 最適 Blumer 部分文字列 求 拘 ，図
上手 機能的領域 被覆 Blumer 部分文字列 数多 存在 分
． rRNA 関 ，領域 上手 覆 Blumer 部分文字列 存在
多 ， 0 . 5 以上 F 値 84% ， 0 . 87 以上 F 値 半数
．
Purity 値 領域 機能 関連性 明 目的 ，
Blumer 部分文字列 単一 注釈付 領域 性質 十分 反映 ， F 値 高
組 考 ． ，領域 部分文字列 組 F 値 0 . 5 以上
0 . 5 未満 分 ．
図 2.8 ， 2.9 Purity 値 ， F 値 高 低
示 ． 横軸 Purity 値，縦軸 範囲 Purity
値 領域 部分文字列 組 数 対応 ．図 2.8 ，水平伝播遺伝子 対応
Blumer 部分文字列 多 高 Purity 値 ， 「 他」 領域 対応
部分文字列 大部分 低 Purity 値 分 ．他方，図 2.9 機能 分類
， 全 Blumer 部分文字列 低 Purity 値
分 ．
観察 ，次 2 仮説 立 ． 「水平伝播遺伝子 対応 Blumer 部分文
字列 場合 ， F 値 Purity 値 間 正 相関 」， 「 他 機能的領域 対
Others rRNA Transposon
tRNA Mobile Element Phage
Rhs 0
10000 20000 30000
0 10 20 30 40
0 20 40 60
0 50 100 150 200
0 10 20 30 40
0 50 100 150 200 250
0 1 2 3 4 5
0.00 0.25 0.50 0.75 1.00
F−measure
Number of Substrings
図 2.7: F 値 ．機能的領域 最適 Blumer 部分文字列 組全
，機能 各分類 全対象 配列 渡 示 ．横軸
F 値，縦軸 範囲 F 値 領域 部分文字列 組 数 対応 ．
Others rRNA Transposon
tRNA Mobile Element Phage
Rhs 0
200 400 600 800
0 10 20 30
0 20 40
0 30 60 90
0 5 10
0 10 20 30
0.0 0.5 1.0 1.5 2.0
0.00 0.25 0.50 0.75 1.00
Purity
Number of Substrings
図 2.8: F 値 高 Purity 値 ．高 F 値 (0 . 5 以上 ) 機能
的領域 最適 Blumer 部分文字列 組全 ，機能 各分類 全
対象 配列 渡 示 ．横軸 Purity 値，縦軸 範囲
Purity 値 領域 部分文字列 組 数 対応 ．
Others rRNA Transposon
tRNA Mobile Element Phage
Rhs 0
5000 10000 15000 20000
0 2 4 6
0 10 20 30 40
0 20 40 60
0.0 2.5 5.0 7.5 10.0
0 50 100 150 200
0 1 2 3 4
0.00 0.25 0.50 0.75 1.00
Purity
Number of Substrings
図 2.9: F 値 低 Purity 値 ．低 F 値 (0 . 5 以下 ) 機能
的領域 最適 Blumer 部分文字列 組全 ，機能 各分類 全
対象 配列 渡 示 ．横軸 Purity 値，縦軸 範囲
Purity 値 領域 部分文字列 組 数 対応 ．
応 Blumer 部分文字列 場合 ， F 値 Purity 値 間 相関 」． 仮
説 順位相関係数 定式化 ，統計的検定 確 ．有意水準 1% ．水平伝播遺伝子 場合 相関係数 0 . 58 0 . 01 未満 p 値 得 ． 従 水平伝播遺伝子 場合 ， F 値 Purity 値 間 正 相関 言 ． 他方「 他」 機能的領域 場合 ，相関係数 − 0 . 18 p 値 1 得 ．従 ， 水平伝播遺伝子以外 機能的領域 ， F 値 Purity 値 間 相関 言
．以上 議論 ， Purity 尺度 特 水平伝播遺伝子 特徴付 ，
機能性 十分 反映 ，水平伝播遺伝子 機能性 有 部分文字列 ，高
Purity 値 与 結論 ．
2.4.3 水平伝播遺伝子検出性能
本節 Purity 尺度 水平伝播遺伝子 検出 試 場合 性能 評
価 ． F 値 0 . 5 以上 ，注釈付 領域 Blumer 部分文字列 組全 ，
Blumer 部分文字列 Purity 値 ，対応 領域 水平伝播遺伝子 分類
領域 判定 ． 単純 Purity 値 閾値 0 . 5 以上
表 2.2: 水平伝播遺伝子 検出性能 評価結果． Purity 値 水平伝播遺伝子，
以外 判定 Blumer 部分文字列 数 示 ． F 値 0 . 5 以上 機
能的領域 Blumer 部分文字列 組 考慮 ．
水平伝播遺伝子 他
Purity ≥ 0 . 5 734 1035
Purity < 0 . 5 286 2209
水平伝播遺伝子 判定 方法 採 ．表 2.2 結果 示 ．水平 伝播遺伝子 判定 内，実際 水平伝播遺伝子 割合 (false discovery rate) 1035 / (734 + 1035) = 0 . 59 比較的高 ．一方 ，水平伝播遺伝子 多 (734 / (734 + 286) = 0 . 72) 上手 検出 ，水平伝播遺伝子 領域 過半
数 (2209 / (1035 + 2209) = 0 . 69) 正 判定 言 ．
2.5 結論
本章 ， Purity 尺度 配列 対 有用性 広 調査 ．興味深
， Purity 値 水平伝播遺伝子 呼 複数 遺伝子 間 顕著 関係
， 視覚的 示 ． Purity 尺度 水平伝播遺伝子 総合的
特徴付 ，他方 G + C 含量 異 傾向 見 ． 定量的 評価 結果， 配列 領域 水平伝播遺伝子 機能性 Purity 値
有意 相関 示 ． ， Purity 尺度 水平伝播遺伝子 検出 用
場合 ， 70% 程度 注釈付 領域 正 判定 分 ．一方 ， false
discovery rate 0 . 59 高 値 ．
以上 結果 Purity 尺度 水平伝播遺伝子 属 複数 遺伝子 総称的 特徴付
示唆 ．従 ， Purity 尺度 水平伝播遺伝子 検出
有用 可能性 意味 言 ．
第 3 章
大 文字
列 対 Purity 尺度 改良
3.1 背景
前章 配列 対 Purity 尺度 適用 扱 ，他 文字列 適用
考 ．例 Yamada [44] 配列 ，日本語
対 実験 行 ．彼 対象 模 人工
的 挿入 不自然 含 ，実際 実験 結果， Purity 尺度
部分 特異性 捉 報告 ． 以外 「明治大学」 大学
名前 捉 方向 ． 日本語 記述 ，単
語 境界 明 ． 拘 ，形態素解析 単語分割 処
理 行 ， Blumer 同値関係 [4] Purity 尺度 適当 抽出
興味深 ． Purity 尺度 有用
可能性 ．
文字列 多 ， 4 種類程度 記号
配列 異 ，多 記号 多 ．例 酸配列
20 種類 酸 ，自然言語 多 記号 使
．記号 数 多 特定 情報 短 単位 文字列 表現
．例 配列 個々 遺伝子 数百 超 数 塩基 普通
，例 英語 単語 単位 短 ． ，
Purity 尺度 配列以外 広範 文字列 適用 場合，部分文字列 長短 影響
受 部分文字列 評価 行 求 ．
表 3.1: Purity 尺度 単語列 ( ) 評価例． Brown 含
“News” 文書 抜 出 ， Purity 値 求 ．最 高
Purity 値 上位 10 位 Purity 値 示 ．
News Purity 値
0.666667 outcom in 0.666667 tatter remain 0.666667 essex counti 0.666667 36 year 0.666667 portion of 0.666667 lafayett squar 0.666667 rescind the 0.666667 greec and 0.666667 deadlin for 0.666667 didn t
， Purity 尺度 短 部分文字列 上手 扱 問題
． Purity 尺度 計算 評価値 有理数 形 ，分母 数 対象
部分文字列 長 依存 決 ． ，短 文字列 特定 評価値 集中 易 ，評価 差別化 行 ．例 ，表 3.1 単語 文字 見 文字列
「単語列」 対 Purity 適用 結果 示 ．表 Purity 値順 上位 10 個 部分文字列 示 ， 10 個全 同 Purity 値 2 / 3 = 0 . 666 · · · 与
分 ．実際 上位 136 件 対 同 Purity 値 与 ，
単語列 互 区別 ．
本研究 ， 問題 克服 新 尺度 Atomicity 尺度 提案 ．以下
，第 2.3.1 節 Atomicity 尺度 定義 ． 後，第 3.3 節 実験 説明
後，最後 結論 述 ．
3.2 手法
Purity 値 偏 生 ，頻度 同一 数 ．
，頻度 異 場合 ， 近 考慮 値 多様性
考 ．例 入力文字列 部分文字列 x 評価 考 ．
， x 部分文字列 y 総出現回数 10 回 内 9 回 x 一部 出現 ， x 部分文字列 z 総出現回数 5 回 内 1 回 x 一部 出現 ． 場合，前者 y 方 x 強 関連 考 ， Purity 尺度
場合 Purity 値 貢献 0 ．
本研究 提案 Atomicity 尺度 ，先 例 8 / 10 , 1 / 5 頻度 比 関連度
見 ，評価値 計算 関連度 考慮 ， 違 細
表現 ．具体的 次 定義 ．
定義 2 入力文字列 T ， 部分文字列 x = T [i : j] 与 ， T 上 x
Atomicity 値 以下 定義 ．
atomicity
T(x) =
∑
⟨k,l⟩∈sub(x)
freq
T( x) freq
T(x[k : l])
/ | sub(x ) |
定義 ，任意 x 対 Purity 値 Atomicity 値 0 < purity
T( x) ≤
atomicity
T(x) ≤ 1 関係 満 分 ．
3.3 実験
本節 2 対 異 方法 Purity 尺度 Atomicity
尺度 適用 ， 尺度 対 有効性 吟味 ．一
20 Newsgroups 呼 ， 中 連続 部分
( ) 対 Purity 尺度 適用 ． 一 Brown 呼
， 中 単語列 ( ) 対 ， Purity 尺度 適用 ．
3.3.1 20 Newsgroups
20 Newsgroups 投稿 収集 ， 20 異
， 1000 投稿 含 ． 投稿 ，
記事 比較的 表現 多 ， 片 多様
混在 ，未知語 多 含 言 ．
本 用 実験 目的 ， 含 多様 表現 対
Purity 尺度・ Atomicity 尺度 値 付与 調 ．
含 全投稿 1 入力文字列 ，今回 特
部分文字列 ( ) 尺度 評価対象 ．
20 Newsgroups 対 ，各投稿 部分 削除 ，全 投稿
1 連結 ．次 連結 抽出 ． 連続
2 文字以上 列 取 出 ．
結果
表 3.2 切 出 Purity 尺度 Atomicity 尺度 評価 結果
一部 示 ．与 評価値 高 順 上位 15 件，下位 15 件 示 ．長 末尾 一部省略 表示 ．
切 出 見 ， “aammmaaaazzzzzziinnnnggggg”
“hahahahaha” 代表 ， 表現 多 分 ． ，
系 ， 名 中 変数名，
添付 由来 文字列 ，通常 単語 性質 異 多 取 出
．
次 Purity 値・ Atomicity 値 合 ， 上位 観察 ．両尺
度 ，比較的長 一見単語 比較的長 文字列 大 値 与
．実際 “wholesomegodfearingbiblebelievingtraditionalfamilyvalues” ，投稿 者 単語 組 合 作 造語 含 ．他方，下位
見 ， Purity 尺度 場合 ，反復的 文字列 比較的最下位 集中 ，
Atomicity 尺度 場合 広範囲 分散 ．表中 示 上位
部分 ，両尺度 単語 思 文字列 分布 ．
，大 傾向 ， Purity 値 Atomicity 値 大 部分文字列 通常
表 3.2: Purity 尺 度 ( 左 側 ) ・ Atomicity 尺 度 ( 右 側 ) 評 価 結 果 ．高 評 価 値 上 位 ， 低 評価値 下位 15 個表示 ．長 後半部分 省略 示 ．
Purity値Atomicity値 0.881brownbladerunnersugarcubeselectroni...0.892brownbladerunnersugarcubeselectronicblayloc... 0.844plutoniumsurveillanceterroristciaas...0.851costellobeatlesspinaltapfawltytowersmuttsav... 0.842costellobeatlesspinaltapfawltytower...0.846plutoniumsurveillanceterroristciaassassinationira... 0.827prxnpueuszqeiiusmcvcrcgnwbavrxfja0.836prxnpueuszqeiiusmcvcrcgnwbavrxfja 0.821wholesomegodfearingbiblebelievingtr...0.830pnaqevxgqaoxrviaggvpvrdlwzchbnqo 0.818pnaqevxgqaoxrviaggvpvrdlwzchbnqo0.827evyynlzbboryvhfszyyhyheqqqilhek 0.817evyynlzbboryvhfszyyhyheqqqilhek0.825wholesomegodfearingbiblebelievingtraditiona... 0.805gasbpxcdhsrhpmebpjklyikuijzat0.813gasbpxcdhsrhpmebpjklyikuijzat 0.791hrrrtnaiwyjmfaqxpeyrodvfdxc0.806abcdefghijklmnopqrstuvwxyz 0.779iainmbanksneworderheathersbatmanpjorourke0.805iainmbanksneworderheathersbatmanpjorourke 0.777gestaltpowermanagerattributesfoodspreadproduct0.803vxxwtpaqebkgqasgoxctzjdzmzurfm 0.776vxxwtpaqebkgqasgoxctzjdzmzurfm0.799hrrrtnaiwyjmfaqxpeyrodvfdxc 0.767moorcockpratchettdenislearydelasoulu0.789mqcnaitfksqaaaeeakceejwi 0.764eocclpkstavebtdcligqhnzowc0.788moorcockpratchettdenislearydelasoulu 0.763tyyobpbtlqgsurgkgdzpxwfh0.785gestaltpowermanagerattributesfoodspreadproduct 0.008ttttttttttttttt0.027compressions 0.008hahahahahahahahahahaha0.027nominates 0.007halesshavethewhalesshavethewhalesshavethewhal...0.027hmmmmmmmmmmmmmmmmmmmmmmmmmm... 0.007vethewhalesshavethewhalesshavethewhalesshavet...0.027regenerates 0.007xxxxxxxxxxxxxxxxx0.026inversions 0.006hmmmmmmmmmmmmmmmmmmmmmm...0.026impresses 0.006immmmmmmmmmmmmmmmmmmmmm...0.026deflections 0.005jjjjjjjjjjjjjjjjjjj0.025exterminations 0.004vvvvvvvvvvvvvvvvvvvvv0.025rationals 0.003oooooooooooooooooooooooooo0.023emulations 0.002esshavethewhalesshavethewhalesshave...0.023constantinov 0.002shavethewhalesshavethewhalesshaveth...0.022separations 0.002wmwmwmwmwmwmwmwmwmwmwmwmwmw...0.021groundings 0.001vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...0.018vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv... <0.001vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...0.018oppositions単語 大 異 文字列 ，逆 値 小 部分文字列 単語 文字列 言 ． 両尺度 評価対象 部分文字列 組成， 構成 ， 小 部分文字列 頻度 考慮 考 ．頻繁 出現 文字 組
合 言語 依存 考 ， 文字 組 部分
文字列 小 評価値 与 ．逆 ，滅多 出現 文字 組 合 用
部分文字列，例 表現 文字列 外来語，合成
語 大 値 与 ．
以上 観察 定量的 確認 ．具体的 ，英語 単語辞書 用 評価対象
「単語」 「単語 類似 文字列」 「 以外」 分類 ，
Purity 値・ Atomicity 値 分布 毎 分析 ． 単語集合
MySpell 1 英語辞書 含 単語，
英語 Wikitionary 2 登録 単語 併 用 ．以下 単語 集合
単 辞書 呼 ．
分類 以下 手順 行 ．
1. 全 内，辞書 含 全 「 word1 」 分類
2. 1 分類 内，語幹 辞書 含 単語 語幹
同一 「 word2 」 分類
3. 2 分類 内，辞書 含 単語 編集距離
3 以下 「 word3 」 分類
4. 3 分類 内，辞書 含 3 文字以上 単語 連接
「 word4 」 分類
5. 4 分類 全 「 others 」 分類
語幹 Snowball 3 用 計算 ． ， word1 ，
word2 word3 単語 単語 類似 文字列 ，
word4 others 合成 語 単語 文字列 ．
図 3.1 ， 3.2 ， Purity 値 Atomicity 値 密度分布 ，
毎 示 ．密度分布 密度推定 計算 ．前述
， Purity 値 特定 値 偏 性質 ， Atomicity 値 分布 滑
． 違 ，両者 大 同様 傾向 言 ．
1http://code.google.com/a/apache-extras.org/p/ooo-myspell/
2http://en.wiktionary.org/wiki/Wiktionary:Main_Page 3http://snowball.tartarus.org/
0 5 10
0.00 0.25 0.50 0.75 1.00
purity
density
class words1 words2 words3 words4 others
図 3.1: Purity 値 分布．
単語 最 類似 文字列 word1 ， word2 ， word3 Purity 値・ Atomicity 値
低 値 偏 ． ，残 2 ，低 値 与
，全体 比較的高 値 偏 ，先 観察 裏
付 言 ． Purity 値 Atomicity 値 偏 ，例 機械学習
不要 語 辞書 依 削除 応用 考 ．
3.3.2 Brown
Brown 英語 ， 15 ，様々
収集 含 ． 本 ，単語 文字 考
文字列 「単語列」 扱 ，単語列 部分文字列 対 Purity 評価 調
． 配列 通常 英文 比 圧倒的 文字数 多 場合 相当 ，
場合 両尺度 振 舞 調査 ． Brown
0 5 10
0.00 0.25 0.50 0.75 1.00
purity
density
class words1 words2 words3 words4 others
図 3.2: Atomicity 値 分布．
採用 ，文章 20 Newsgroups 対照的 比較的整 ，単語
不要 多様性 排除 ． 前章 同様 ，単語列 部分文字列 内
Blumer 部分文字列 考 ， 呼 ．
15 毎 1 連結 ，結果 15 入力 用意 ，
個別 扱 ．
結果
表 3.3 ， Brown 15 内 4 対 結果 示
． Atomicity 値順 上位 10 件 下位 10 件 示 ．表 3.1 示
Purity 尺度 多数 同一 値 与 ， 値
性質 表現 考 省略 ． ，先 20 Newsgroups 場合 比
長 ( 構成 単語数 ) 圧倒的 短 ， 対象
出現回数 2 回以上 限定 ．
表 3.3: Atomicity 尺 度 評 価 結 果 ． Bro wn 選 択 4 ，各 ，文 書 抽 出 Atomicity 尺 度 評 価 ． Atomicity 値 上 位 下 位 ， 10 個 示 ．
NewsReviewsGovernmentRomance Atomicity値Atomicity値Atomicity値Atomicity値 1.000000puertorico1.000000catfishbend1.000000losangel1.000000hongkong 1.000000dolcvita1.000000wharfrat1.000000puertorico0.958333grattshafer 1.000000corpuschristi1.00000018esiecl1.000000dupont0.925926oclock 1.000000sterltownship1.000000sanchopanza1.000000amicicuria0.895833evadnamaeevan 1.000000pinardelrio1.000000olgamoiseyeva1.000000conscientiobjector0.888889waltperri 1.000000hardwicketter1.000000zealousvolunt1.000000nonresidalien0.888889signorraymond 1.000000duncanphyfe1.000000peewee0.973985regionofficinatlanta gaboston...0.888889vshapeinlet 1.000000scottishrite1.000000teatray0.954545rhodeisland0.863636wetgrahamcracker 1.000000notrdame1.000000andreapalladio0.944444lanternslide0.857143mousichandler 1.000000hongkong0.944444sanfrancisco0.942529samrayburn0.857143sandiego 0.176417oneofa0.192778oneofit0.160240intheunitstateor0.166052hesaid“i 0.174724inthepresid0.192667itisthe0.159587oftheunitnation0.162456whichhehadbeen 0.174002tothefirst0.189765intheprogram0.154709partoftheunitstate0.160008anditwasnot 0.173955itwillbethe0.188133atthefirst0.154322departofthestate0.159077“illbe 0.170289totheun0.187400ofthe“0.146225oftheunitstateor0.157727thavetobe 0.164508presidoftheunivers0.187307withthemusic0.139310partofthenation0.155281said“im 0.163976hesaid“we0.184279andthemusic0.133474thegovernoftheunit stateofamericain 0.147193said“ill 0.162041chairmanofthere- publican
0.182640inthemusic0.126949ofthegovernofindia0.137401hesaid“im 0.155763hesaid“i0.182511isoneofthemost0.121070oftheunitstateand0.135393anditwasa 0.140840oneofthefirst0.165639oneofthegreat0.116950intheunitstateand0.132477isaid“i
