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

Slides:



Advertisements
Similar presentations
ゲームプログラミング講習 第2章 関数の使い方
Advertisements

サービス管理責任者等研修テキスト 分野別講義    「アセスメントと        支援提供の基本姿勢」 <児童発達支援管理責任者> 平成27年10月1日.
ヒトの思考プロセスの解明を目的とするワーキングメモリの研究
第27講 オームの法則 電気抵抗の役割について知る オームの法則を使えるようにする 抵抗の温度変化を理解する 教科書P.223~226
コラッツ予想の変形について 東邦大学 理学部 情報科 白柳研究室 山中 陽子.
コンパイラ 第3回 字句解析 ― 決定性有限オートマトンの導出 ―
第5章 家計に関する統計 ー 経済統計 ー.
公共財 公共経済論 II no.3 麻生良文.
VTX alignment D2 浅野秀光 2011年12月15日  放射線研ミーティング.
冷却フランシウム原子を用いた 電子の永久電気双極子能率探索のための ルビジウム磁力計の研究
生命情報学 (8) スケールフリーネットワーク
前半戦 「史上最強」風 札上げクイズ.

認知症を理解し 環境の重要性について考える
フッ化ナトリウムによる洗口 2010・9・13 宮崎市郡東諸県郡薬剤師会 学校薬剤師  日高 華代子.
食品の安全性に関わる社会システム:総括 健康弱者 ハイリスク集団 HACCP (食肉処理場・食品工場) 農場でのQAP 一般的衛生管理
規制改革とは? ○規制改革の目的は、経済の活性化と雇用の創出によって、   活力ある経済社会の実現を図ることにあります。
地域保健対策検討会 に関する私見(保健所のあり方)
公共政策大学院 鈴木一人 第8回 専門化する政治 公共政策大学院 鈴木一人
医薬品ネット販売規制について 2012年5月31日 ケンコーコム株式会社.
平成26年8月27日(水) 大阪府 健康医療部 薬務課 医療機器グループ
平成26年度 呼吸器学会からの提案結果 (オレンジ色の部分が承認された提案) 新規提案 既収載の変更 免疫組織化学染色、免疫細胞化学染色
エナジードリンクの危険性 2015年6月23日 経営学部市場戦略学科MR3195稲沢珠依.
自動吸引は 在宅を変えるか 大分協和病院 院長         山本 真.
毎月レポート ビジネスの情報 (2016年7月号).
医療の歴史と将来 医療と医薬品産業 個人的経験 3. 「これからの医療を考える」 (1)医薬品の研究開発 -タクロリムスの歴史-
社会福祉調査論 第4講 2.社会調査の概要 11月2日.
2015年12月28日-2016年3月28日 掲載分.
2010度 民事訴訟法講義 補論 関西大学法学部教授 栗田 隆.
腫瘍学概論 埼玉医科大学国際医療センター 包括的がんセンター 緩和医療科/緩和ケアチーム 奈良林 至
“企業リスクへの考え方に変化を求められています。 トータルなリスクマネジメント・サービスをプロデュースします。“
情報漏えい 経済情報学科 E  西村 諭 E  釣 洋平.
金融班(ミクロ).
第11回 2009年12月16日 今日の資料=A4・4枚+解答用紙 期末試験:2月3日(水)N2教室
【ABL用語集】(あいうえお順) No 用語 解説 12 公正市場価格 13 債権 14 指名債権 15 事業収益資産 16 集合動産 17
基礎理論(3) 情報の非対称性と逆選択 公共政策論II No.3 麻生良文.
浜中 健児 昭和42年3月27日生まれ 東京都在住 株式会社ピー・アール・エフ 代表取締役 (学歴) 高 校:千葉県立東葛飾高校 卒業
COPYRIGHT(C) 2011 KYUSHU UNIVERSITY. ALL RIGHTS RESERVED
Blosxom による CMS 構築と SEO テクニック
記入例 JAWS DAYS 2015 – JOB BOARD 会社名 採用職種 営業職/技術職/その他( ) 仕事内容 待遇 募集数
ネットビジネスの 企業と特性 MR1127 まさ.
Future Technology活用による業務改革
ネットビジネス論(杉浦) 第8回 ネットビジネスと情報技術.
g741001 長谷川 嵩 g740796 迫村 光秋 g741000 西田 健太郎 g741147 小井出 真聡
自然独占 公共経済論 II no.5 麻生良文.
Autonomic Resource Provisioning for Cloud-Based Software
Webショップにおける webデザイン 12/6 08A1022 甲斐 広大.
物理的な位置情報を活用した仮想クラウドの構築
ハイブリッドクラウドを実現させるポイントと SCSKのOSSへの取組み
寺尾 敦 青山学院大学社会情報学部 第12回 情報デザイン(4) 情報の構造化と表現 寺尾 敦 青山学院大学社会情報学部
【1−1.開発計画 – 設計・開発計画】 システム開発計画にはシステム開発を効率的、効果的に実行する根拠(人員と経験、開発手順、開発・導入するシステム・アプリケーション・サービス等)を記述すること。 システム開発の開始から終了までの全体スケジュールを記載すること。 アプリケーション機能配置、ソフトウェア、インフラ構成、ネットワーク構成について概要を示すこと。
6 日本のコーポレート・ガバナンス 2008年度「企業論」 川端 望.
急成長する中国ソフトウェア産業 中国ソフトウェアと情報サービス産業の規模 総売上高は5年間で約5.3倍の成長
米国ユタ州LDS病院胸部心臓外科フェローの経験
公益社団法人日本青年会議所 関東地区埼玉ブロック協議会 JCの情熱(おもい)育成委員会 2011年度第1回全体委員会
次世代大学教育研究会のこれまでの活動 2005年度次世代大学教育研究大会 明治大学駿河台校舎リバティタワー9階1096教室
子どもの本の情報 大阪府内の協力書店の情報 こちらをクリック 大阪府内の公立図書館・図書室の情報
第2回産業調査 小島浩道.
〈起点〉を示す格助詞「を」と「から」の選択について
広東省民弁本科高校日語専業骨幹教師研修会 ①日本語の格助詞の使い分け ②動詞の自他受身の選択について   -日本語教育と中日カルチャーショックの観点から- 名古屋大学 杉村 泰.
■5Ahバッテリー使用報告 事例紹介/東【その1】 ■iphon4S(晴れの昼間/AM8-PM3) ◆約1時間で68%⇒100%
『ワタシが!!』『地域の仲間で!!』 市民が始める自然エネルギー!!
ポイントカードの未来形を形にした「MUJI Passport」
SAP NetWeaver を支える Microsoft テクノロジーの全貌 (Appendix)
ガイダンス(内業) 測量学実習 第1回.
Python超入門 久保 幹雄 東京海洋大学.
熱力学の基礎 丸山 茂夫 東京大学大学院 工学系研究科 機械工学専攻
京都民医連中央病院 CHDF学習推進委員会
資料2-④ ④下水道.
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
Presentation transcript:

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

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

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

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

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

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

研究背景(テキストマイニング) 大量のテキストデータから、価値ある情報の 抽出を行うための分析 価値ある情報の抽出 テキストから特徴ベクトルへの変換がよく行われる 特徴ベクトルによってテキスト間の距離を定義できる ⇒クラスタリング等への応用 テキストデータに対して最も基本的な特徴ベクトルが 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]

研究背景(テキストマイニング) 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

研究背景(テキストマイニング) 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

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

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

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

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

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

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

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

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

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

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

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

提案手法 各単語に通し番号を付与し単語辞書生成 スレーブサーバ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 ⁞

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

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

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

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

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