並列分散処理フレームワークSparkを用いた TF-IDF計算手法の提案

Presentation on theme: "並列分散処理フレームワークSparkを用いた TF-IDF計算手法の提案"— Presentation transcript:

1 並列分散処理フレームワークSparkを用いた TF-IDF計算手法の提案
数理情報科学専攻　 福永研究室 西村建郎

2 目次 研究背景 TF-IDF計算手法（既存のライブラリ を用いた手法） TF-IDF計算手法（提案手法） スケーラビリティ比較 結論・まとめ
並列処理 テキストマイニング 研究概要 TF-IDF計算手法（既存のライブラリ を用いた手法） TF-IDF計算手法（提案手法） スケーラビリティ比較 結論・まとめ 私の研究室では並列処理の研究を行ってきましたが、今年度から並列処理のテキストマイニングへの応用について取り組み始めました。 まずは研究背景として、並列処理とテキストマイニングについて紹介したあと、研究概要をお話します。 それから、今回の研究テーマであるTF-IDF計算について、既存の手法と、今回提案する手法について説明し、 それらのスケーラビリティを比較し、結論まとめと進めたいと思います。

3 研究背景（並列処理） 並列処理 1つの処理を複数に分割して同時に行うこ と（逐次処理） 通信等によるオーバーヘッドがかかる 時間 1
：並列処理によるオーバーヘッド ：計算時間 1/2 まず並列処理とは、1つの処理を複数に分割して同時に行うことをいいます。 反対に、分割せずに処理を行うことを逐次処理と呼びます。 逐次処理でかかる時間を1とすると、2分割で並列処理した場合は1/2、4分割で並列処理した場合は1/4の時間で処理ができることが期待されます。 しかし、先の登壇者の説明では省力されていましたが、 実際は通信等による図のようなオーバーヘッドが生じるため期待通りにはいきませんが、分割数を増やすほど処理時間を短くすることが出来ます。 1/4 逐次処理 並列処理 （2分割） 並列処理 （4分割）

4 研究背景（並列処理） 並列処理の方法 マルチコア クラスタ コアと呼ばれる演算装置を複数個持つCPU
複数のサーバを連結し、全体で１台のサーバで あるかのように振舞うシステム サーバ CPU コア コア コア コア 並列処理の方法として代表的な2つが、マルチコアとクラスタです。 マルチコアとは、○。マルチコアを用いると、1つの処理を1台のサーバ内でコアごとに分割して並列処理が行えます。 また、クラスタとは、複数のサーバを連結して、全体で1台のサーバであるかのように振舞うシステムのことをいいます。 先の登壇者の研究ではマルチコアを用いていましたが、私はクラスタを用いました。 クラスタを用いると、1つの処理をサーバごとに分割して並列処理を行います。また、各サーバがマルチコアを用いていればさらに分割して並列化が可能になります。 しかし、通常のプログラミングを用いてクラスタでの並列処理を実現するのは困難です。 クラスタ サーバ サーバ サーバ サーバ

5 研究背景（並列処理） Spark 現在最も注目を浴びている並列分散処理 フレームワーク
膨大なデータに対して高速な並列分散処理をす るための仕組みを提供するソフトウェア 高速かつ汎用的な処理を行うために開発された 有名なIT企業が中心となって現在も発展中 Java,Python,Scala等の言語を用いてシン グルスレッドのプログラミングと同じ感覚で 並列分散処理を実装可能 機械学習用ライブラリMLlibが含まれている そこで、クラスタを用いて簡単に並列処理を実装するための仕組みとして、Sparkと呼ばれるものが登場しました。

6 研究背景（並列処理） Sparkで用いるクラスタ マスターサーバ（1台） スレーブサーバ（1台～数1,000台）
アプリケーションの管理・制御 並列処理部分をスレーブサーバのタスクに変換 し、タスクをスレーブサーバに割り当てる スレーブサーバ（1台～数1,000台） 割り当てられたタスクの実行 マスターサーバ Sparkで用いるクラスタ構成について説明します。 Sparkはマスタースレーブ構成をとっており、マスターサーバがスレーブサーバに指示を出し、スレーブサーバで実際の並列処理を行うという関係になっています。 具体的には、マスターサーバが大元となるアプリケーションを実行し、○。 そして、スレーブサーバは○。 スレーブサーバは1～数1,000台まで拡張することができ、台数を増やすほど処理時間が短くなるように設計されています。 スレーブサーバ スレーブサーバ スレーブサーバ

7 研究背景（テキストマイニング） 大量のテキストデータから、価値ある情報の 抽出を行うための分析 価値ある情報の抽出
テキストから特徴ベクトルへの変換がよく行われる 特徴ベクトルによってテキスト間の距離を定義できる ⇒クラスタリング等への応用 テキストデータに対して最も基本的な特徴ベクトルが TF(term frequency)ベクトル 特徴ベクトル （TFベクトル） 1:hello 1 2 ⁞ テキスト(例) Hello spark world. Good bye spark. 2:spark 大量のテキスト 3:world 4:word 続いてテキストマイニングの説明をします。テキストマイニングとは簡単に言うと、○です。 分析手法にはこのようにさまざまなものがありますが、分析をする下準備として、テキストデータを特徴ベクトルに変換することがよくあります。 特徴ベクトルとは、分析したい各データに対する特徴をまとめてベクトルとして表現したものです。 テキストデータをベクトルに変換することで、テキスト同士の距離が定義できることから、クラスタリング等に応用できます。 テキストデータに対する最も基本的な特徴ベクトルがTFベクトルです。これは～の略であり、単語の出現頻度をもとにベクトル化を行う方法です。 このように、例えばこのようなテキストがあった時に、各単語をあるベクトルの次元に対応させ、その単語が何回出現したかを各次元の要素とします。 5:good 分析手法（例） クラスタリング 潜在意味解析 機械学習 6:bye 単語抽出 7:text 価値ある情報の抽出 [hello,spark,world,good,bye,spark]

8 研究背景（テキストマイニング） DF(document frequency) ある単語が含まれるテキスト数 テキスト1 テキスト2
テキスト3 テキスト4 各単語に対する DF TFベクトル TFベクトル TFベクトル TFベクトル 1:hello 2 ⁞ 8 1 ⁞ 4 2 3 ⁞ 2 1 ⁞ 2 3 4 1 ⁞ また、テキストマイニングにおける重要な概念として、DFというものがあります。 これは～の略であり、ある単語がいくつのテキストに含まれているかを表すものです。 例えば全部で4つのテキストがあり、それぞれこのようなTFベクトルが生成されたとすると、 DFは、各単語に対するTFが0でないベクトルの個数によって計算することが出来ます。 2:spark 3:world 4:word

9 研究背景（テキストマイニング） DF(document frequency) ある単語が含まれるテキスト数 テキスト1 テキスト2
テキスト3 テキスト4 各単語に対する DF TFベクトル TFベクトル TFベクトル TFベクトル 1:hello 2 ⁞ 8 1 ⁞ 4 2 3 ⁞ 2 1 ⁞ 2 3 4 1 ⁞ DFが大きい単語は、多くのテキストで出現するため重要度が低く、逆にDFが小さい単語はある特定のテキストでのみ出現するので、重要度が高いと言えます。 このDFを用いてTFベクトルに重み付けをしたものが、 ここまで5分 2:spark 3:world 4:word

10 研究背景（テキストマイニング） TF-IDFベクトル
TFベクトルに重み(IDF:inverse document frequency)を掛け合わせた特徴ベクトル TFベクトルよりもテキストの特徴を強調する 𝑇:総テキスト数 𝑇𝐹 𝑤𝑡 :テキスト𝑡内で単語𝑤の出現した回数 𝐷𝐹 𝑤 :全テキストの中で、単語𝑤が含まれるテキスト数 𝐼𝐷𝐹 𝑤 = 𝑙𝑜𝑔 𝑇 𝐷𝐹 𝑤 𝑇𝐹𝐼𝐷𝐹 𝑤𝑡 = 𝑇𝐹 𝑤𝑡 𝐼𝐷𝐹 𝑤 重み𝐼𝐷𝐹 𝑤 は、多くのテキストで現れる単語では小さくな り、少ないテキストでしか現れない単語では大きくなる。 𝑇𝐹𝐼𝐷𝐹 𝑤𝑡 が大きい⇒テキストの内容を表す重要な単語 TF ベクトル TF-IDF ベクトル IDF 1 2 ⁞ × = TF-IDFベクトルです。 これは、先ほど説明したTFベクトルに、DFをもとに計算されるIDFという重みをかけあわせることで、テキストの特徴をより強調したベクトルを生成します。 こちらがその定義になります。 ここで、IDFはDFの逆数をとっているため、IDFは○。

11 研究背景（研究概要） SparkのMLlib（ライブラリ）を用いると、簡単に テキストをTF-IDFベクトルに変換できる
長所 高速に動作する 短所 正確さを犠牲にしている 分析の幅が狭くなる 短所を改善し、かつ実行時間の増加を最小限 にとどめた計算手法を提案し、実装した ここから研究概要に移ります

12 MLlibを用いたTF-IDF計算 単語のリストからTFベクトルを生成 ベクトルの次元数Nを指定
ハッシュ関数の特徴 与えられた単語から1~Nの値を生成する 同じ単語からは必ず同じ値が生成される 出力値の値から単語を求めることは出来ない TFベクトル 1:hello 1 2 ⁞ 2:spark 3:world 単語リスト 4:word MLlibでは、単語のリストからTFベクトルを生成する機能が提供されています。 初めにベクトルの次元数Nを指定し、ハッシュ関数により各単語を1~Nの数値に対応させます。 ここで用いるハッシュ関数というのは、○○○。 このように、各単語に対してハッシュ関数を適用させ、例えばその出力値が1であれば、1次元の箇所ににTFを格納します。 [hello,spark,world,good,bye,spark] 5:good 6:bye ハッシュ関数適用 7:text 各単語 1～N ⁞ （例）hash(“hello”)=1 N:the

13 MLlibを用いたTF-IDF計算 TFベクトル計算 大量のテキストファイル スレーブサーバ1 スレーブサーバ2 スレーブサーバ3
ファイル① 大量のテキスト ファイル② 大量のテキスト ファイル③ 単語抽出 単語抽出 単語抽出 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト ・・・ リスト リスト ・・・ リスト TFベクトル TFベクトル TFベクトル 1→ この処理をスレーブサーバ3台で並列処理させた様子がこのような図になります。 まず分析対象とする大量のテキストファイルを3台のサーバに分割して保存しておきます。 それぞれのサーバで、割り当てられたテキストに対し、単語を抽出し、単語リストを生成します。そして、先ほど述べた方法で単語リストをTFベクトルに変換します。 2→ ・・・ ・・・ ・・・ ・・・ N→

14 MLlibを用いたTF-IDF計算 TFベクトル計算 1つのテキストに対応 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3
マスターサーバ 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト ・・・ リスト リスト ・・・ リスト TFベクトル TFベクトル TFベクトル 1→ ここで、各リストとTFベクトルそれぞれが、1つのテキストに対応します。 2→ ・・・ ・・・ ・・・ ・・・ N→

15 MLlibを用いたTF-IDF計算 IDF計算 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ TFベクトル
1→ 2→ そうすると、各テキストに対して、TFベクトルを求めることが出来ました。 しかし、最終的にTF-IDFベクトルを求めるためには、IDFが必要となるため、全サーバと通信する必要があります。 ・・・ ・・・ ・・・ ・・・ N→

16 MLlibを用いたTF-IDF計算 IDF計算 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ TFベクトル
1→ 2→ 全スレーブサーバのデータをマスターサーバに集約し、各単語に対するIDFを計算します。 ・・・ ・・・ ・・・ ・・・ N→

17 MLlibを用いたTF-IDF計算 TF-IDF計算 各単語に対するIDF スレーブサーバ1 スレーブサーバ2 スレーブサーバ3
マスターサーバ 各単語に対するIDF TFベクトル TFベクトル TFベクトル 1→ 2→ そして、求まったIDFを各TFベクトルに掛け合わせることによって、 ・・・ ・・・ ・・・ ・・・ N→

18 MLlibを用いたTF-IDF計算 TF-IDF計算 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ
1→ 2→ ・・・ ・・・ ・・・ ・・・ N→

19 MLlibを用いた手法の短所 各次元がどの単語に対応しているのかを知る ことが出来ない 異なる単語が同じ次元に対応し、衝突する可 能性がある
TFベクトル 各次元がどの単語に対応しているのかを知る ことが出来ない ⇒分析方法が制限される（特徴ベクトルから頻出単語・ 重要単語の抽出が出来ない） 異なる単語が同じ次元に対応し、衝突する可 能性がある ⇒正確さを要求する処理には使用できない 1 1 8 ⁞ 2 2 この頻出単語 は何か 3 4 5 ⁞ N TFベクトル 1 2 以上がMllibを用いたTF-IDFベクトル計算手法になります。 この手法だと高速にベクトル化ができるのですが、いくつか短所があることが分かりました。 まず、○です。 次に、○です。 3 4 word1 5 ハッシュ関数適用 hash(word1) = hash(word2) ⁞ word2 N

20 提案手法 DF計算 大量のテキストファイル スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ 大量のテキスト ファイル①
ファイル② 大量のテキスト ファイル③ 単語抽出 単語抽出 単語抽出 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ 各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト ・・・ リスト リスト ・・・ リスト 各リストから重複を除く 各リストから重複を除く 各リストから重複を除く 重複除いたリスト 重複除いたリスト 重複除いたリスト 重複除いたリスト 重複除いたリスト 重複除いたリスト そこで、これらの短所を改善する手法を提案しました。 まずは先程と同じように 先程と異なり、初めに各単語のDFを計算するために、単語リストから、重複を除いた単語のみを抽出します。 そしてそれらをマスターサーバに集約することで各単語のDFを計算します。 ・・・ ・・・ ・・・ 各単語に対するDF 単語 DF word1 3 word2 7 ⁞ 集約

21 提案手法 各単語に通し番号を付与し単語辞書生成 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ 各単語に対するDF
word1 3 word2 7 ⁞ 単語辞書 単語 DF 通し番号 word1 3 1 word2 7 2 ⁞ ここまでで、各単語に対するDF求まりましたが、さらに各単語に対して、通し番号を割り振ります。 ここで割り当てた通し番号をあとでベクトルに変換する際、各単語に対応するベクトルの次元とすることで、 先ほどの問題点であった衝突を防ぐことが出来ます。 ここで生成したものを本研究では単語辞書と呼びます。 そしてコピー 各スレーブサーバにコピー 単語 DF 通し番号 word1 3 1 word2 7 2 ⁞ 単語 DF 通し番号 word1 3 1 word2 7 2 ⁞ 単語 DF 通し番号 word1 3 1 word2 7 2 ⁞

22 提案手法 単語リストと単語辞書からTF-IDFベクトル生成 スレーブサーバ1 スレーブサーバ2 スレーブサーバ3 マスターサーバ
各テキストの単語リスト 各テキストの単語リスト 各テキストの単語リスト リスト ・・・ リスト リスト ・・・ リスト リスト ・・・ リスト 単語辞書 単語辞書 単語辞書 単語 DF 通し番号 単語 DF 通し番号 単語 DF 通し番号 TF-IDFベクトル TF-IDFベクトル TF-IDFベクトル 1→ 2→ ここで、先ほど生成した各テキストの単語のリストと、全単語に対するDFと通し番号を用いて、 TF-IDFベクトルを計算します。 ・・・ ・・・ ・・・ ・・・ N→

23 スケーラビリティの比較 用いたテキストデータ 評価方法 アプリケーション（仕様） エンロンコーパス
テキスト数：約500,000 言語：英語 総データ量：1.35GB 評価方法 2つのアプリケーションを用意し、スレーブサーバ1 ～6台に対して、それぞれ100回ずつ実行し、平均 実行時間を比較する アプリケーション（仕様） テキストデータをスレーブサーバに分散して格納しておく アプリケーション実行開始 すべてのテキストをTF-IDFベクトルに変換し、スレーブサ ーバに格納する アプリケーション終了

24 結果・考察 スケーラビリティ スレーブサーバの台数にかかわらず、本提案手法は実行時間に関してはMllibを用いた手法には及びませんでした。
また、スケーラビリティの面では、 提案手法は増やすごとに時間が短縮しているのに対し、MLlibではサーバ数を増やすほど時間が伸びている部分があります。 このことから、提案手法の方が、通信などによるオーバーヘッドが小さく、並列化に向いているアルゴリズムであると考えられます。

25 まとめ Sparkを用いたTF-IDF計算について MLlibを用いた手法 提案手法 ハッシュ関数を用いて、正確さを犠牲に高速化を実現 する
テキスト間の距離による分析にしか使えない 提案手法 初めにDFを計算し、単語辞書を生成することにより、 正確な分析が可能 単語辞書を参照することにより、TF-IDFベクトルから 重要単語の抽出が可能（分析の幅が広がる） スレーブサーバの台数を増やすことでMLlibを用いた 手法の速度に追いつく可能性がある

26 終わりです ～ご清聴ありがとうございました～