並列分散処理フレームワークSparkを用いた TF-IDF計算手法の提案 数理情報科学専攻 福永研究室 西村建郎 目次 研究背景 並列処理 テキストマイニング 研究概要 TF-IDF計算手法（既存のライブラリ を用いた手法） TF-IDF計算手法（提案手法） スケーラビリティ比較 結論・まとめ 研究背景（並列処理） 並列処理 1つの処理を複数に分割して同時に行うこ と（逐次処理） 通信等によるオーバーヘッドがかかる 時間 1 ：並列処理によるオーバーヘッド ：計算時間 1/2 1/4 逐次処理 並列処理 並列処理 （2分割） （4分割） 研究背景（並列処理） 並列処理の方法 マルチコア • コアと呼ばれる演算装置を複数個持つCPU サーバ CPU コア コア コア コア クラスタ • 複数のサーバを連結し、全体で１台のサーバで あるかのように振舞うシステム クラスタ サーバ サーバ サーバ サーバ 研究背景（並列処理） Spark 現在最も注目を浴びている並列分散処理 フレームワーク • 膨大なデータに対して高速な並列分散処理をす るための仕組みを提供するソフトウェア • 高速かつ汎用的な処理を行うために開発された • 有名なIT企業が中心となって現在も発展中 Java,Python,Scala等の言語を用いてシン グルスレッドのプログラミングと同じ感覚で 並列分散処理を実装可能 機械学習用ライブラリMLlibが含まれている 研究背景（並列処理） Sparkで用いるクラスタ マスターサーバ（1台） • アプリケーションの管理・制御 • 並列処理部分をスレーブサーバのタスクに変換 し、タスクをスレーブサーバに割り当てる スレーブサーバ（1台～数1,000台） • 割り当てられたタスクの実行 マスターサーバ スレーブサーバ スレーブサーバ スレーブサーバ 研究背景（テキストマイニング） 大量のテキストデータから、価値ある情報の 抽出を行うための分析 テキストから特徴ベクトルへの変換がよく行われる 特徴ベクトルによってテキスト間の距離を定義できる ⇒クラスタリング等への応用 テキストデータに対して最も基本的な特徴ベクトルが TF(term frequency)ベクトル テキスト(例) 大量のテキスト Hello spark world. Good bye spark. 分析手法（例） クラスタリング 潜在意味解析 機械学習 価値ある情報の抽出 単語抽出 [hello,spark,world,good,bye,spark] 特徴ベクトル （TFベクトル） 1:hello 1 2:spark 2 3:world 1 4:word 0 5:good 1 6:bye 1 7:text 0 ⁞ 研究背景（テキストマイニング） DF(document frequency) ある単語が含まれるテキスト数 テキスト1 テキスト2 テキスト3 テキスト4 TFベクトル TFベクトル TFベクトル TFベクトル 各単語に対する DF 1:hello 0 8 4 0 2 2:spark 2 1 0 2 3 3:world 2 1 2 1 4 4:word 0 0 3 0 1 ⁞ ⁞ ⁞ ⁞ ⁞ 研究背景（テキストマイニング） DF(document frequency) ある単語が含まれるテキスト数 テキスト1 テキスト2 テキスト3 テキスト4 TFベクトル TFベクトル TFベクトル TFベクトル 各単語に対する DF 1:hello 0 8 4 0 2 2:spark 2 1 0 2 3 3:world 2 1 2 1 4 4:word 0 0 3 0 1 ⁞ ⁞ ⁞ ⁞ ⁞ 研究背景（テキストマイニング） TF-IDFベクトル TFベクトルに重み(IDF:inverse document frequency)を掛け合わせた特徴ベクトル TFベクトルよりもテキストの特徴を強調する 𝑇:総テキスト数 TF ベクトル 1 2 𝑇𝐹𝑤𝑡 : テキスト𝑡内で単語𝑤の出現した回数 1 𝐷𝐹𝑤 : 全テキストの中で、単語𝑤が含まれるテキスト数 0 𝑇 𝐼𝐷𝐹𝑤 = 𝑙𝑜𝑔 𝐷𝐹𝑤 𝑇𝐹𝐼𝐷𝐹𝑤𝑡 = 𝑇𝐹𝑤𝑡 𝐼𝐷𝐹𝑤 重み𝐼𝐷𝐹𝑤 は、多くのテキストで現れる単語では小さくな り、少ないテキストでしか現れない単語では大きくなる。 𝑇𝐹𝐼𝐷𝐹𝑤𝑡 が大きい⇒テキストの内容を表す重要な単語 TF-IDF ベクトル IDF 1 1 0 ⁞ × = 研究背景（研究概要） SparkのMLlib（ライブラリ）を用いると、簡単に テキストをTF-IDFベクトルに変換できる 長所 • 高速に動作する 短所 • 正確さを犠牲にしている • 分析の幅が狭くなる 短所を改善し、かつ実行時間の増加を最小限 にとどめた計算手法を提案し、実装した MLlibを用いたTF-IDF計算 単語のリストからTFベクトルを生成 ベクトルの次元数Nを指定 ハッシュ関数により各単語を1～Nの整数に対応さ せる ハッシュ関数の特徴 TFベクトル • 与えられた単語から1~Nの値を生成する • 同じ単語からは必ず同じ値が生成される 1:hello 1 • 出力値の値から単語を求めることは出来ない 2:spark 2 3:world 1 単語リスト 4:word 0 [hello,spark,world,good,bye,spark] 5:good 1 6:bye 1 7:text 0 ⁞ ⁞ N:the 0 各単語 ハッシュ関数適用 1～N （例）hash(“hello”)=1 MLlibを用いたTF-IDF計算 TFベクトル計算 大量のテキスト ファイル① 大量のテキストファイル 大量のテキスト ファイル② 単語抽出 単語抽出 大量のテキスト ファイル③ 単語抽出 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト ・・・ リスト リスト ・・・ TFベクトル TFベクトル TFベクトル ・・・ ・・・ ・・・ 1→ 2→ ・ ・ ・ N→ リスト マスターサーバ MLlibを用いたTF-IDF計算 TFベクトル計算 1つのテキストに対応 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト ・・・ リスト リスト ・・・ TFベクトル TFベクトル TFベクトル ・・・ ・・・ ・・・ 1→ 2→ ・ ・ ・ N→ リスト マスターサーバ MLlibを用いたTF-IDF計算 IDF計算 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 TFベクトル TFベクトル TFベクトル ・・・ ・・・ ・・・ 1→ 2→ ・ ・ ・ N→ マスターサーバ MLlibを用いたTF-IDF計算 IDF計算 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 TFベクトル TFベクトル TFベクトル ・・・ ・・・ ・・・ 1→ 2→ ・ ・ ・ N→ マスターサーバ DF IDF MLlibを用いたTF-IDF計算 TF-IDF計算 各単語に対する IDF スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ TFベクトル TFベクトル TFベクトル 各単語に対する IDF ・・・ ・・・ ・・・ 1→ 2→ ・ ・ ・ N→ MLlibを用いたTF-IDF計算 TF-IDF計算 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ TF-IDFベクトル TF-IDFベクトル TF-IDFベクトル 各単語に対する IDF ・・・ ・・・ ・・・ 1→ 2→ ・ ・ ・ N→ MLlibを用いた手法の短所 各次元がどの単語に対応しているのかを知る ことが出来ない ⇒分析方法が制限される（特徴ベクトルから頻出単語・ 重要単語の抽出が出来ない） TFベクトル 1 1 2 0 3 8 4 0 5 1 ⁞ ⁞ N 2 異なる単語が同じ次元に対応し、衝突する可 能性がある TFベクトル 1 2 3 ⇒正確さを要求する処理には使用できない 4 word1 ハッシュ関数適用 hash(word1) = hash(word2) この頻出単語 は何か 5 ⁞ word2 N 提案手法 大量のテキストファイル DF計算 大量のテキスト ファイル① 大量のテキスト ファイル② 単語抽出 単語抽出 大量のテキスト ファイル③ 単語抽出 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト 各リストから 重複を除く 重複 除いた リスト ・・・ 重複 除いた リスト ・・・ リスト リスト 各リストから 重複を除く 重複 除いた リスト ・・・ 重複 除いた リスト ・・・ マスターサーバ リスト 各リストから 重複を除く 重複 除いた リスト ・・・ 重複 除いた リスト 各単語に対するDF 集約 単語 DF word1 3 word2 7 ⁞ ⁞ 提案手法 各単語に通し番号を付与し単語辞書生成 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ 各単語に対するDF 単語 DF word1 3 word2 7 ⁞ ⁞ 単語辞書 各スレーブサーバにコピー 単語 DF 通し番号 単語 DF 通し番号 単語 DF 通し番号 word1 3 1 word1 3 1 word1 3 1 word2 7 2 word2 7 2 word2 7 2 ⁞ ⁞ ⁞ ⁞ ⁞ ⁞ ⁞ ⁞ ⁞ 単語 DF 通し番号 word1 3 1 word2 7 2 ⁞ ⁞ ⁞ 提案手法 単語リストと単語辞書からTF-IDFベクトル生成 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト 単語辞書 単語 DF 通し番号 ・・・ リスト リスト 単語辞書 単語 DF 通し番号 ・・・ 単語辞書 単語 DF ・ ・ ・ N→ 通し番号 TF-IDFベクトル TF-IDFベクトル TF-IDFベクトル ・・・ ・・・ ・・・ 1→ 2→ リスト マスターサーバ スケーラビリティの比較 用いたテキストデータ エンロンコーパス • テキスト数：約500,000 • 言語：英語 • 総データ量：1.35GB 評価方法 2つのアプリケーションを用意し、スレーブサーバ1 ～6台に対して、それぞれ100回ずつ実行し、平均 実行時間を比較する アプリケーション（仕様） 1. テキストデータをスレーブサーバに分散して格納しておく 2. アプリケーション実行開始 3. すべてのテキストをTF-IDFベクトルに変換し、スレーブサ ーバに格納する 4. アプリケーション終了 結果・考察 スケーラビリティ 70 60 50 平均実行時間 （秒） 40 30 20 10 0 1 2 3 4 スレーブサーバの数（台） MLlib 提案手法 5 6 まとめ Sparkを用いたTF-IDF計算について MLlibを用いた手法 • ハッシュ関数を用いて、正確さを犠牲に高速化を実現 する • TF-IDFベクトルから重要単語を抽出することが出来 ない • テキスト間の距離による分析にしか使えない 提案手法 • 初めにDFを計算し、単語辞書を生成することにより、 正確な分析が可能 • 単語辞書を参照することにより、TF-IDFベクトルから 重要単語の抽出が可能（分析の幅が広がる） • スレーブサーバの台数を増やすことでMLlibを用いた 手法の速度に追いつく可能性がある 終わりです ～ご清聴ありがとうございました～
© Copyright 2024 ExpyDoc
