分散処理プラットフォームHadoopに よるWikipediaデータの解析 森 竜也 (東京電機大学) 2010.11.7 1 概要 • Wikipediaで配布されているデータファイル • 日本語版で6.5GBほどの巨大なXMLファイル1個 に全ページ内容が記述されている • 公式にはSQLダンプに変換して使用する • オープンソースの分散処理プラットフォーム Hadoopによる処理方法を紹介 2 何ができるか? • 例えば – ページ名やページの種別を出力する – 記事中に挙げられている参考文献を集める – テレビ番組の記事を抽出する などプログラミング次第で色々できる しかし得手不得手はある 3 見出し • • • • • • • Wikipediaの配布データ Hadoopとは Hadoopプログラム入門 Wikipediaデータへの応用 実例 Medawikiとの比較 ダウンロード 4 Wikipediaの配布データ 5 ダウンロードサイト • http://download.wikimedia.org/jawiki/latest/ jawiki-latest-interwiki.sql.gz jawiki-latest-pages-meta-current.xml.bz2 6 jawiki-latest-pages-meta-current.xml • 全ページ内容が記述されているXMLファイル • 6.5GB • page要素がWikipedia1ページ分の情報 <mediawiki> <siteinfo>ヘッダー情報</siteinfo> <page>ページ内容1</page> <page>ページ内容2</page> <page>ページ内容3</page> ・ ・ ・ <page>ページ内容n</page> </mediawiki> ページ要素 1,880,711個 7 page要素 <page> <title>Hadoop</title> <id>1805248</id> <revision> <id>34222653</id> <timestamp>2010-09-28T14:57:34Z</timestamp> <contributor> <username>Tire works</username> <id>456732</id> </contributor> <minor/> <comment>バージョンを更新。</comment> <text xml:space="preserve"> 記事本文…… </text> </revidion> </page> title要素 ページタイトル id要素 ページID text要素 記事本文 Wiki形式の 生データ 8 公式で紹介されている使い方 1. MediaWikiのインポート機能で取り込む 2. 変換ツールを使用してSQLダンプに変換 – xml2sql, mwdumper • Hadoopを利用した手法 – 簡単なプログラミングで分散処理が可能 9 Hadoopとは 10 Hadoopとは • Apacheで開発されている分散コンピューティ ングプラットフォーム • GoogleのGFS(Google File System)と MapReduceのJavaによるクローン • もちろんオープンソース • 分散処理、分散ファイルシステムなど – Hadoopを活用するためのサブプロジェクト有 Hadoopマスコット 11 特徴 • スケーラビリティ • • • • Hadoopで使用するのは普通、一般的な性能のマシン 5台分の処理能力が必要なら5台 100台分の処理能力が必要なら100台 というように必要に応じた規模のクラスタを構成できる • Yahoo!やfacebook、楽天などでも利用 – 数千台のマシン、数TBのデータ – Wikipediaの数GBのデータはHadoopの利用例からすれば 小さいほう 12 Hadoopプログラム入門 13 MapReduce • Hadoopで使用する分散処理のアルゴリズム • map処理とreduce処理の2段階でkeyとvalue のデータ組を出力、集約する map reduce 14 MapReduce • 元データがレコード単位に分割されてmapに配布さ れる • mapでデータを加工しkeyとvalueの組データを出力 • reducerはkey毎にまとめられたvalue群を受け取り、 新たなkeyとvalueの組を出力 map reduce 15 MapReduceの例 • 学校のテスト結果 • 1人分の結果を書いたカードがある • 手作業で組ごとの平均点を求めるには? 1組 20番 75点 16 組ごとの平均点を算出 • どうするか? 3組 12番 90点 2組 7番 20点 2組 31番 50点 1組 20番 75点 1組 5番 80点 1組 25番 80点 3組 15番 90点 3組 3番 35点 2組 10番 75点 1組 4番 20点 17 組ごとの平均点を算出 • 当然 1. 組ごとにカードを分ける 2. 組ごとに点数を足す 3. 平均点=合計点/カードの枚数 1組 4番 20点 2組 7番 20点 3組 3番 35点 1組 5番 80点 2組 10番 75点 3組 12番 90点 1組 20番 75点 2組 31番 50点 3組 15番 90点 1組 25番 80点 255 255/4=63.75 145 145/3=48.33 215 215/3=71.66 18 MapReduceにあてはめる • 1人分のデータをmapに配布 • mapは組をkey, 点数をvalueにして出力 • reduceは組ごとにグループ化されたデータ群 を受け取れるので、平均点を算出 1組 4番 20点 ・・・・・・ 3組 7番 20点 2組 15番 90点 1 1 20 20, 80, 75,80 3 20 2 20, 75, 50 1組 63.75 2組 48.33 3組 71.66 2 90 3 35, 90, 90 19 処理対象データ 組 番号 3 1 2 1 3 2 44 32 33 21 1 ・ ・ ・ 42 点数 63 89 74 36 99 84 20 MapReduceプログラム実装 • mapを行うMapperクラスの定義 • reduceを行うReducerクラスの定義 • 実行時の設定であるJobオブジェクトの生成 21 MapperクラスとReducerクラス • Hadoop側で用意されている抽象クラス MapperとReducerをオーバーライドして定義 する • 必要なのは1つのメソッドだけ – Mapperならmapメソッド – Reducerならreduceメソッド – 先ほどの平均点プログラムの場合…… 22 平均点算出Mapper 総称型で入出力データ の型を定義 valueが 入力ファイル1行分 public class ScoreAverageMapper extends Mapper<LongWritable, Text, IntWritable, IntWritable> { protected void map(LongWritable key, Text value, Context context) throws IOException ,InterruptedException { String[] columns = value.toString().split("\t"); int classN = Integer.parseInt(columns[0]); int score = Integer.parseInt(columns[2]); context.write(new IntWritable(classN), new IntWritable(score)); }; } keyが組 valueが点数 として出力 23 平均点算出Reducer keyが組 key(組)と結びついている value(点数)が Iterableとして取得できる public class ScoreAverageReducer extends Reducer<IntWritable, IntWritable, IntWritable, DoubleWritable> { protected void reduce(IntWritable key, Iterable<IntWritable> values, Context context)throws IOException ,InterruptedException { int sum = 0; int students = 0; for (IntWritable score : values) { sum += score.get(); students++; } context.write(key, new DoubleWritable((double)sum / (double)students)); }; } keyが組 valueが平均点 として出力 24 Jobオブジェクトの生成 Job job = new Job(getConf()); job.setJarByClass(ScoreAverage.class); job.setMapperClass(ScoreAverageMapper.class); Mapperクラスの指定 job.setReducerClass(ScoreAverageReducer.class); Reducerクラスの指定 job.setMapOutputKeyClass(IntWritable.class); Mapperクラスの出力keyの型 job.setMapOutputValueClass(IntWritable.class); Mapperクラスの出力valueの型 job.setOutputKeyClass(IntWritable.class); Reducerクラスの出力keyの型 job.setOutputValueClass(DoubleWritable.class); Reducerクラスの出力valueの型 job.setInputFormatClass(TextInputFormat.class); Mapperへのデータの与え方 job.setOutputFormatClass(TextOutputFormat.class); 出力結果の形式 FileInputFormat.addInputPath(job, new Path(args[0])); 入力ファイルのパス FileOutputFormat.setOutputPath(job, new Path(args[1])); 出力ファイルのパス return job.waitForCompletion(true) ? 0 : 1; 設定内容でMapReduceを実行 25 実際に動作させる • Hadoopの3つのモード – スタンドアロン • 開発用 – 疑似分散 • 動作確認用 – 分散環境 • 実環境 26 Hadoopの利点1 • 1つのmap, reduceタスクは、ほかのタスクの進捗状 況を考慮する必要がない • プログラミングが容易 • 他人の書いたMapReduceを再利用可能 ・・・・・・ このmapタスクからすれば、 他のmapがどういう状況であろうと、 自分の作業には関係ない 1組 63.75 2組 48.33 3組 71.66 27 Hadoopに向かないこと • MapReduceの実行には小さくないオーバー ヘッドが掛かる • リアルタイムで結果を求めれるような処理に は不向き – 例えば検索システム – ×検索の度にMapReduceでデータを解析 – ○あらかじめインデックスなどの2次的なデータを MapReduceで生成しておく 28 Wikipediaデータへの応用 29 Wikipediaデータへの応用 • 平均点の時と同様に、このMapReduceの枠 組みに当てはめて考える jawiki-latest-pagesmeta-current.xml map reduce 30 Wikipediaデータへの応用 • page要素(1ページ分のデータ)がMapperに 配布する単位としてちょうど良さそうである <mediawiki> <siteinfo>ヘッダー情報</siteinfo> <page>ページ内容1</page> <page>ページ内容2</page> <page>ページ内容3</page> ・ ・ ・ <page>ページ内容n</page> </mediawiki> ページ要素 1,880,711個 31 InputFormatの定義 • 入力ファイルをMapperに与える形に分割する クラス • 平均点プログラムではTextInputFormat – 入力ファイルを1行ずつ切り出す – 継承してpage要素を切り出すInputFormatを定義 Input Format 32 WikipediaXmlInputFormat • 実際にはTextInputFormatの機能を利用して1 行ずつ読みだし、page要素の始まりから終わ りまでをMapperへ渡す <mediawiki> <siteinfo>ヘッダー情報</siteinfo> <page>ページ内容1</page> <page>ページ内容2</page> <page>ページ内容3</page> ・ ・ ・ <page>ページ内容n</page> </mediawiki> 1ページの分のデータを Mapperへ配布する 33 ページ名やページの種別を出力 • 記事、カテゴリ、リダイレクトを抽出 • ページ名はtitle要素から取得 • 判断基準 – カテゴリ • ページ名が”Category:”で始まる – リダイレクト • 本文が#REDIRECT [[転送先]]という記述 – 記事 • それ以外 34 実行時間 • 日本語版データファイル • 使用マシン – OS: CentOS 5 – CPU: Xeon 3060 2.40GHz – メモリ: 4GB – マスタ1台、スレーブ3台 • ページの種別を抽出のに3分程度 35 記事中に挙げられている 参考文献を集める • Wikipediaでは情報の出典を記載するガイドラ インがある – 残念ながらあまり守られていない…… – (特に日本語版では) • ISBNコードを集める – 世界中を書籍を識別するためのコード – Wikipediaは書籍の出典にISBNコードを記述する のは任意 36 記事中に挙げられている 参考文献を集める • ページが記事であれば、本文からISBNコード を抽出 – 正規表現によるパターンマッチ – ISBN (*[\d-]+) – 10桁の旧規格と、13桁の新規格が混在 – 新規格への変換手順があるので、新規格に統一 して出力 37 参考文献 英語版 日本語版 ドイツ語版 フランス語版 外部リンクがあ る 42% 39% 52% 30% 参考文献のセ クションがある 34% 6% 20% 10% ISBNコードがあ る 6% 5% 14% 3% • 書籍と、Web上の資源で参照している割合が異なる 38 テレビ番組の記事を抽出する • 以下の基準でテレビ番組であるか判定する – カテゴリに”~番組”がある – テンプレートに”基礎情報_番組”がある 39 MediaWikiとの比較 40 MediaWikiとの比較 処理データ 分散処理 言語 Wiki記法 Hadoop XMLファイル 可能 Java 自前で解析 MediaWiki データベース 不可能 PHP 標準のParser • MediaWikiは単独のマシン上でPHPとRDBを使う • Hadoopは複数のマシン上でJavaを使う • 複雑なWiki文法を解析するのは困難 41 テンプレート • 与えた引数に応じてParserが文字列を出力す る仕組み • {{Lang-en|United States of America}} – Lang-enというテンプレート – 引数は” Lang-en|United States of America” • Parserの出力は • 英語: United States of America 42 なぜHadoop上でテンプレートを 解析しにくいか1 {{Lang-en|United States of America}} • 記事の • という記述を見ても、Lang-enが呼び出されて いることは分かっても、Lang-enがどのような テンプレートかは分からない ・・・・・・ Mapperは自分が与えらたデータの 1組 63.75 ほかには参照できるデータがない 2組 48.33 3組 71.66 43 なぜHadoop上でテンプレートを 解析しにくいか2 • テンプレートは入れ子にできる • リンクやタグを書ける 44 MediaWikiとの使い分け 処理データ 分散処理 言語 Wiki記法 Hadoop XMLファイル 可能 Java 自前で解析 MediaWiki データベース 不可能 PHP 標準のParser • 複雑な文法を解析する場合は、MediaWikiを利 用したほうが効率的 • Javaにも代替パーサがある • http://code.google.com/p/gwtwiki/ • ある程度の文法はサポートされているが、 Wikipediaで使われている多くのextensionまで はサポートしきれない 45 おわりに • 本日紹介したプログラムはソースコードと共 に公開しています • http://sourceforge.jp/projects/wik-ie/ • ご清聴ありがとうございました 46
© Copyright 2024 ExpyDoc