ノート/テキストマイニング
訪問者数 1212      最終更新 2010-06-27 (日) 13:55:41

>>ノート/テキストマイニング/剽窃1

文書類似度を距離とした文書(学生レポート)のクラスタ化 (2010/06/26)

原理

ノート/テキストマイニング/剽窃1では、単語出現頻度ベクトルを計算し、そのベクトルの方向の近さ=2ベクトル間のなす角(実はcosine=内積として)を求めた。

ここでは、その「類似度」を文書間の距離とみなして、(正確には類似度と距離は逆の関係なので修正必要)、類似しているもの同士を「クラスタ化」してみる。

結果

結果を先に表示すると、前記ページのサンプルデータについて、単純な(階層型)クラスタリングを行った結果、

hclust-ward_400x400.pnghclust-complete_400x400.png

が得られた。但し、23〜30は計算上のダミーで、意味が無い。

処理・計算法

原理上は非常にストレートである。

唯一考えるのは、単語出現頻度ベクトル間の角度のcosine値が内積として求められているが、1.0が高類似(ベクトルの方向が一致、つまり同一)、0.0が類似性なし(ベクトル間のなす角が90度)であるのに対し、クラスタリング時には「距離」によって計算を行う。怠けてパッケージを使いたいので、データの形を合わせておく必要がある。ここでは最大手抜きで、

距離 =(1.0−類似度cosine値)

としてしまった。必ずしも「距離」を表していないという批判は可能で、もっと「それらしい」距離を頻度ベクトルから考えてもいいだろう。

尚、頻度ベクトルから直接クラスタリングをすることも考えられるだろうが、後の課題として、置いておく事にする。

ここから、統計パッケージ R を利用する。Pythonと同様に、とても手軽で便利なので最近多用している。R標準パッケージ中のクラスタリング機能hclustをまずは試してみよう。以下、参考にしたのは
 新納浩幸 「Rで学ぶクラスタ解析」 オーム社 ISBN978-4-274-06703-7

われわれのデータを、hclustの入力に合わせる必要がある。hclustはクラスdist (距離マトリックス)を入力とする。2つの要素(レポート)の距離を行列上に表したものだが、下三角行列(上半分は対称なので省略)になっている。以下サンプル。

            1         2         3         4         5         6         7
2   0.5385165                                                            
3   0.5099020 0.3000000                                                  
4   0.6480741 0.3316625 0.2449490                                        
5   0.1414214 0.6082763 0.5099020 0.6480741                              
6   0.6164414 1.0908712 1.0862780 1.1661904 0.6164414                    
7   0.5196152 0.5099020 0.2645751 0.3316625 0.4582576 0.9949874

なお、対角要素も 0 である(同じものだから、距離は 0 )。

剽窃1での画面出力は

./OS2/s17.txt ./OS2/s18.txt 1.0000
./OS2/s13.txt ./OS2/s7.txt 0.8622
./OS2/s13.txt ./OS2/s17.txt 0.7567
./OS2/s13.txt ./OS2/s18.txt 0.7567

であるから、やるべきことは、(1)各行の1番目のファイル名の番号部分を数字xに変換、(2)2番目のファイル名を数字yに変換、(3)3番目の値zを距離行列の第(x, y)要素に書き込む、ということである。

更に、下三角行列にするために、右上にあれば左下に移動する((3)の書き込みで、もし右上x>yなら、(x,y)に書く代わりに(y,x)に書くようにする。

もう1つ、(3)で書き込む値は、類似度cosine値のzではなくて、距離として使う(1-z)を書き込む。

これらの処理は、Rでやってもいいが、馴れたpythonでやってしまおう。

#!/usr/bin/env python
# coding: utf-8
import re
import Numeric
import csv
import codecs
import sys

sys.stdout = codecs.getwriter('utf_8')(sys.stdout)

# Function filenumber converts filename "./OS2/s12.txt" into integer 12.
def filenumber(fn):
  x = fn.split('/')
  y = x[2].split('.')
  z = y[0][1:]
  return int(z)

a = Numeric.zeros((30,30), Numeric.Float)
            # Size of dist matrix is set to 30 for simplicity.  Need more work.
# Read the input file
fname = "100204_sorted_cosines.txt"
file = open(fname, "r")
for line in file:
  u =  line.split(' ')   # split input line by space(' ') into list u
  x = filenumber(u[0])   # convert 1st element of the list u into the number
  y = filenumber(u[1])   # convert 2nd element of u
  z = float(u[2].strip('\n'))  # remove '\n' (end-of-line) from z
  if x>y:
    a[x-1,y-1] = 1.0-z   # set (1.0-z) to distance matrix. subtract 1 because the file number starts from 1.
  else:
    a[y-1,x-1] = 1.0-z

#print a
writer = csv.writer(open("dist.csv", "wb"))  # write out the dist table as CSV
writer.writerows(a)

これによって、距離行列がCSV形式でファイルdist.csvに書かれる。

0.0   , 0.0   , 0.0   , 0.0   , ...
0.9526, 0.0   , 0.0   , 0.0   , ...
0.9766, 0.9988, 0.0   , 0.0   , ...
0.9211, 0.4752, 0.9971, 0.0   , ...
...

これを統計パッケージRに読み込んで、hclustを使ってクラスタリング処理を行う。

Rでの処理は、次のRのプログラムによる。

# Convert the distance list (sxx, syy, dist) to distance table(matrix)
# Read the distance table 
u <- matrix(scan("dist.csv", sep=","), ncol=30, byrow=TRUE)
   # sep="," indicates that each data is separated by a comma
   # ncol=30 indicates that the data consists of 30 columns in each line
   # byrow=TRUE means that the data is stored row-by-row
# Convert the table to the "distance table" format (class)
d <- as.dist(u)
   # This converts the matrix data u into a class-dist object d
# Then, apply hclust(d)
c <- hclust(d, method="ward")
# Display the result c
plot(c)
hclust-ward_400x400.pnghclust-complete_400x400.png

左側がWard法によるクラスタ化、右側が完全連結法(complete法)によるクラスタ化の結果である。なお、23~〜30はダミーで値0が入っている。細かく観察すると、


添付ファイル: filehclust-ward_400x400.png 233件 [詳細] filehclust-complete_400x400.png 217件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-06-27 (日) 13:55:41 (2707d)