アルゴリズム入門演習課題例：英語版Wikipedia

演習用データについて

データの出典

データの内容

corpus.txt
英語版wikipediaの一部を抽出したもの（以下コーパスと呼ぶ）である。解析を簡単にするため、大文字は全て小文字化されており、リンクや英語にない文字等は取り除かれている。原則として一行が一文に対応する。
stopwords.txt
解析の精度を上げるためにあえて無視する単語（以下ストップワードと呼ぶ）の一覧である。一行が一単語に対応する。
vocabulary.txt
解析対象とする単語（以下語彙と呼ぶ）の一覧である。全ての単語を考えるのは計算時間がかかりすぎるため、比較的よく現れる3000語を抽出している。一行が一単語に対応する。

データの読み込み方法

一例だが、以下のプログラムを実行することで、ストップワードが配列として変数stopwordsに、語彙が配列として変数vocabularyに、コーパスが2次元配列（文の配列であり、各文は単語の配列）として変数corpusに、それぞれ読み込むことができる。

  stopwards = open('stopwords.txt').read().splitlines()
  vocabulary = open('vocabulary.txt').read().splitlines()
  corpus = [s.split() for s in open('corpus.txt').readlines()]

演習課題例

文章の簡易要約

コーパスに比べてよく現れる単語を抽出することで、文章を象徴するような単語の抽出を行う。

corpusの各行を連結して得られる1次元配列を求めよ。
コーパス全体での単語の出現回数のヒストグラムを求め、corpus_wordsとせよ。
文章が文字列で与えられたとき、以下の処理を行う関数をプログラムせよ。
1. 文章を単語に分解せよ。（ヒント：split()関数を使う）
2. 文章に現れる各単語について、その文章中での出現回数をcorpus_wordsでのその単語の出現回数で割った値（比）を求める。例えば、文章中に「cat」という単語が3回、コーパス中に300回現れるなら、「cat」の比は0.01となる。
3. 単語を比が大きいものから5件出力する。
様々な英文を入力し、その文章を象徴するような単語が出力されているか確認せよ。

単語の出現確率

単語中にどのような2文字の並びが現れやすいかを計算し、それを元に語彙中のどの単語が現れやすいかを求めてみる。

各2文字の並びがコーパス中に何回現れるかを2次元配列countとして求めよ。countは行番号を1文字目、列番号が2文字目に対応させる。例えば、count[1][2]はabの出現回数、count[3][5]はceの出現回数である。また、count[0][2]は単語先頭にbが現れた回数、count[2][0]は単語末尾にbが現れた回数とする。（ヒント：文字αが何番目かは、ord('α') - 96で求められる）
countの各行ごとに、その行の値の総和で行の各値を割り確率にした配列bigramを作れ。bigram[1][2]はaの後にbが続く確率、bigram[0][2]は単語先頭にbが現れる確率、bigram[2][0]はbの後何も続かない（単語末尾である）確率となる。
（発展）bigramを2次元ヒートマップとして可視化してみよ。
単語を与えると、bigramに従いその単語の現れる確率を求める関数probabilityをプログラムせよ。例えばcatの現れる確率はbigram[0][3] * bigram[3][1] * bigram[1][20] * bigram[20][0]となる。
語彙中の長さ3の各単語についてその単語の現れる確率を求め、上位10件・下位10件を出力せよ。また、長さ4の各単語・長さ5の各単語についても同様にせよ。

単語のクラスタリング

単語をその周辺に現れやすい単語によってクラスタリングし、「周辺に同じような単語が現れる単語同士は似ている」という仮説を検証する。

準備として、vocabulary = set(vocabulary)とせよ。これは以降の処理の効率を改善する。
パラメータwを適当に決め（例えばw=5）、ある単語の「周辺」をその単語の前後w個の単語で語彙に含まれるものとする。例えば、w=3のとき、"copy and redistribute the material in any medium or format" の "material" の「周辺」は and, the, in, any となる（redistributeとmediumは語彙に含まれない）。
文sのn番目の単語の「周辺」を求める関数neighbor(s, n)をプログラムせよ。（ヒント：単語αが語彙に含まれるかどうかは 'α' in vocabularyで調べられる）
単語が与えられたとき、その単語のコーパス中の各出現ごとに「周辺」を求め、「周辺」中にどの単語が合計何回現れたかを求める関数contextをプログラムせよ。以下これをその単語の「文脈」と呼ぶ。
語彙中の全単語について文脈を求めよ。
2つの文脈の「距離」を求める関数cosineをプログラムせよ。この関数は、文脈同士の「内積」（両方の周辺に現れる単語の出現数の積の総和）を文脈の大きさ（周辺中の単語出現回数の総和）の積で割ったものとする。
cosineを距離関数として語彙の文脈をクラスタリングせよ
（発展）以上の処理を、「ストップワードに含まれる単語は『周辺』に含めない」として行なえ。結果はどう変化するだろうか？（ヒント：単語αが語彙に含まれストップワードに含まれないかどうかは 'α' in vocabulary and 'α' not in stopwordsで調べられる）

戻る

アルゴリズム入門 演習課題例：英語版Wikipedia