ノート/テキストマイニング
訪問者数 1092      最終更新 2010-05-28 (金) 18:01:55

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

遺伝子配列アラインメント技法による類似度計算と剽窃検出 (2010/05/28)

前振り
剽窃1で議論したように、レポートの類似性を判定する方法として、まずは単語の出現頻度分布のパターンの類似性を測る方法が考えられている。実際、かなりよく類似性が検出できると思われる。
別の方法として、出現頻度分布ではなく、単語の並びとしてみる方法が考えられるだろう。英語では既に、遺伝子の配列の類似性を検出するのに使われるSmith-Waterman法を使った研究がある。私の興味としては、たとえば次のような点がある。

原理

遺伝子配列のアラインメント技術、たとえば広く使われているSmith-Waterman法を使って、単語列のアラインメント(=位置合せ)をする。
R. W. Irving
"Plagiarism and Collusion Detection using the Smith-Waterman Algorithm"
http://www.dcs.gla.ac.uk/publications/PAPERS/7444/TR-2004-164.pdf

その昔に戯れに書いたSmith-Watermanのプログラムがそのまま使えそうなので、何が起こるか試してみよう。

道具立て

Smith-Watermanのアルゴリズム

アルゴリズムそのものは教科書を参考にされたい。

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

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

def match(x, y):
  print "match ", x, " and ", y,
  if (x == y):
    print "returns ", +1
    return +1
  else:
    print "returns ", -1
    return -1

def MAXwithDirection(p, q, r):
  print "MAXwithDirections", p, q, r
  if (p>q):
    if (q>r):
      return [p,1]
    elif (p>r):
      return [p,1]
    else:
      return [r,3]
  elif (q<r):
    return [r,3]
  else:
    return [q,2]

f = open('testdata.txt','r')
s1 = f.readline()
s2 = f.readline()
s1 = s1[:len(s1)-1]
s2 = s2[:len(s2)-1]
f.close()

d = 1
# 横len(s1)、縦len(s2)の配列arを作る
## Assuming NumPy for "array"
ar = reshape( array([0 for x in range(0,(len(s1)+1)*(len(s2)+1))]),
              ((len(s1)+1),(len(s2)+1))   )
az = reshape( array([0 for x in range(0,(len(s1)+1)*(len(s2)+1))]),
              ((len(s1)+1),(len(s2)+1))   )
# Initialize ar
for x in range(1,(len(s1)+1)):
  ar[x, 0] = -x
  az[x, 0] = 2
for y in range(1,(len(s2)+1)):
  ar[0, y] = -y
  az[0, y] = 1

for x in range(1,(len(s1)+1)):
  for y in range(1,(len(s2)+1)):
    u = MAXwithDirection( (ar[x, y-1]-d), (ar[x-1,y]-d), (ar[x-1,y-1]+match(s1[x-1],s2[y-1]) )  )
    # print('u=', u, 'x,y=', x, y)
    ar[x,y] = u[0]
    az[x,y] = u[1]

#    print 'ar[x,y-1]:', ar[x,y-1], 'ar[x-1,y]:', ar[x-1,y], 'ar[x-1,y-1]:', ar[x-1,y-1],
#    print 'x:', x, ' y:', y, ' ar[x,y]:', ar[x,y]

print(ar)
print(az)

##  Follow-up the trace table
trace = []
x = len(s1); y = len(s2)
line1 = ''; line2 = ''
while ((x>=1) or (y>=1)):
  #print('x ', x, ' y ', y, ' s1 ', s1, ' s2 ', s2);
  trace.append((x,y))
  if (az[x,y]==1):
    line1 = line1+' '
    line2 = line2+s2[y-1]
    y = y-1
  elif (az[x,y]==2):
    line1 = line1+s1[x-1]
    line2 = line2+' '
    x = x-1
  elif (az[x,y]==3):
    line1 = line1+s1[x-1]
    line2 = line2+s2[y-1]
    x = x-1
    y = y-1
  else:
    print("Error")

print(trace)

## Show the aligned result in 2-line format
print(line1[::-1])
print(line2[::-1])

入力ファイルとして

TAGGCA
AGGCAT

のようなものを用意して実行すると、Smith-Watermanの中で用いる表として

[[ 0 -1 -2 -3 -4 -5 -6]
 [-1 -1 -2 -3 -4 -5 -4]
 [-2  0 -1 -2 -3 -3 -4]
 [-3 -1  1  0 -1 -2 -3]
 [-4 -2  0  2  1  0 -1]
 [-5 -3 -1  1  3  2  1]
 [-6 -4 -2  0  2  4  3]]

のようなものが出来、バックトラック用の表として(手抜き、というか学生に見える形にするためバックトラックの状況を示す表を作った。1は左へ戻る、2は上へ戻る、3は斜め左上へ戻る、を示す)

[[0 1 1 1 1 1 1]
 [2 3 3 3 3 3 3]
 [2 3 1 1 1 3 1]
 [2 2 3 3 1 1 1]
 [2 2 2 3 1 1 1]
 [2 2 2 2 3 1 1]
 [2 2 2 2 2 3 1]]

バックトラックした結果は、

[(6, 6), (6, 5), (5, 4), (4, 3), (3, 2), (2, 1), (1, 0)]

のようになる。それを見やすい形に2つの配列を表示すると

TAGGCA
 AGGCAT

のようになる。

上記のプログラムを、形態素解析出力に対して作用させる

次に、Smith-Watermanの入力として、chasenの出力の単語リストを与える。剽窃1の実験で使ったプログラムを援用する。以下の関数を用意した。

def getTokens(fname):  # Returns word list only (word properties are omitted)
  f = open(fname, 'r')
  txt = hankakuAlphaNum2zenkakuAlphaNum(f.read())
  wordlist = pycha.pycha(txt)
  f.close()
  w = []
  for u in wordlist:
    w.append(u[0])
  ##for u in w:
  ##  print '>' + u + '< length', len(u)
  return w

この中で、hankakuAlphaNum2zenkakuAlphaNumは、入力文データ中の英数字や記号が半角であると比較しづらいし見づらいので、全部全角に直してしまうというものである。ここのページから借用した。

def hankakuAlphaNum2zenkakuAlphaNum(s):  # Converts hankaku AN to zenkaku AN
  t = dict((0x0020 + ch, 0xff00 + ch) for ch in range(0x5f))
  t[0x0020] = 0x3000
  return s.translate(t)

もう1つ厄介な問題が、出力の表示である。遺伝子配列の場合は各要素はA, G, C, Tの1文字(たんぱく質も同じ)であるが、ここでは(形態素解析の出力である)「単語」である。単語は長さ不定なので、一方が欠失だと、その欠室部分を、相手側の単語の長さの文だけ空白を入れなければ、単語の縦位置が揃わない。その辺のごちゃごちゃを含めて作ったのが、以下のやや長くなったプログラムである。

#!/usr/bin/env python
# coding: utf-8
import sys
import codecs
import re
import math
from Numeric import *
import glob
import pycha
import unicodedata

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

def match(x, y):    # matches words(as strings)
  ## print "match ", x, " and ", y,
  if (x == y):
    ## print "returns ", +1
    return +1
  else:
    ## print "returns ", -1
    return -1

def MAXwithDirection(p, q, r):
  #print "MAXwithDirections", p, q, r
  if (p>q):
    if (q>r):
      return [p,1]
    elif (p>r):
      return [p,1]
    else:
      return [r,3]
   elif (q<r):
     return [r,3]
  else:
    return [q,2]

def hankakuAlphaNum2zenkakuAlphaNum(s):  # Converts hankaku AN to zenkaku AN
  t = dict((0x0020 + ch, 0xff00 + ch) for ch in range(0x5f))
  t[0x0020] = 0x3000
  return s.translate(t)

def getTokens(fname):  # Returns word list only (word properties are omitted)
  f = open(fname, 'r')
  decoded_f = codecs.getreader('utf-8')(f)
  txt = hankakuAlphaNum2zenkakuAlphaNum(decoded_f.read())
  wordlist = pycha.pycha(txt)
  f.close()
  w = []
  for u in wordlist:
    w.append(u[0])
  ##for u in w:
  ##  print '>' + u + '< length', len(u)
  return w

#########################
#  Main starts here
#########################
s1 = getTokens('OS2/s13.txt')
s2 = getTokens('OS2/s17.txt')
print len(s1), len(s2) 

d = 1
# 横len(s1)、縦len(s2)の配列arを作る
## Assuming NumPy for "array"
ar = reshape( array([0 for x in range(0,(len(s1)+1)*(len(s2)+1))]),
              ((len(s1)+1),(len(s2)+1))   )
az = reshape( array([0 for x in range(0,(len(s1)+1)*(len(s2)+1))]),
              ((len(s1)+1),(len(s2)+1))   )
# Initialize ar
for x in range(1,(len(s1)+1)):
  ar[x, 0] = -x
  az[x, 0] = 2
for y in range(1,(len(s2)+1)):
  ar[0, y] = -y
  az[0, y] = 1

for x in range(1,(len(s1)+1)):
  for y in range(1,(len(s2)+1)):
    u = MAXwithDirection( (ar[x, y-1]-d), (ar[x-1,y]-d), (ar[x-1,y-1]+match(s1[x-1],s2[y-1]) )  )
    ar[x,y] = u[0]
    az[x,y] = u[1]

#    print 'ar[x,y-1]:', ar[x,y-1], 'ar[x-1,y]:', ar[x-1,y], 'ar[x-1,y-1]:', ar[x-1,y-1],
#    print 'x:', x, ' y:', y, ' ar[x,y]:', ar[x,y]

print(ar)
print(az)

##  Follow-up the trace table
trace = []
x = len(s1); y = len(s2)
line1 = []; line2 =[]
while ((x>=1) or (y>=1)):
  #print('x ', x, ' y ', y, ' s1 ', s1, ' s2 ', s2);
  trace.append((x,y))
  if (az[x,y]==1):
    line1.append(u' ')
    line2.append(s2[y-1])
    y = y-1
  elif (az[x,y]==2):
    line1.append(s1[x-1])
    line2.append(u' ')
    x = x-1
  elif (az[x,y]==3):
    line1.append(s1[x-1])
    line2.append(s2[y-1])
    x = x-1
    y = y-1
  else:
    print("Error")

print(trace)

## Show the aligned result in 2-line format
str1 = ''; str2 = ''
if len(line1)==len(line2):
  for i in range(len(line1)-1, 0, -1):
    l1 = len(line1[i])/3; l2 = len(line2[i])/3
    if (line1[i]!=u' ') and (line1[i]==line2[i]):
      str1 = str1 + line1[i]
      str2 = str2 + line2[i]
    elif (line1[i]==u' ') and (line2[i]==u' '):
      str1 = str1 + u' '; str2 = str2 + u' '
    elif (line1[i]==u' '):
      for j in range(0,l2):
        str1 = str1 + u' '
      str2 = str2 + line2[i]
    elif (line2[i]==u' '):
      for j in range(0,l1):
        str2 = str2 + u' '
      str1 = str1 + line1[i]
    else:
      str1 = str1 + line1[i]
      str2 = str2 + line2[i]
      if (l1 > l2):
        for j in range(0, l1-l2):
          str2 = str2 + ' '
      elif (l1 < l2):
        for j in range(0, l2-l1):
          str1 = str1 + ' '

    str1 = str1 + ' '; str2 = str2 + ' '
  print str1
  print str2
else:
  print 'Error: result length differs'

このバージョンでは、漢字コードはすべてunicode/utf-8で扱うこととしたため、文字列の長さを返す関数lenはすべて3倍(3バイトで1文字)を返している。ここはもう少し整理して依存性をなくしたい。ユニコードの場合一般にはlen関数は文字数を返すはずなのだが。

とにかく実行結果である。実際には1行に出るのだが、見づらいので、行を適宜折り返してある。

            O S の 基本 モジュール すなわち 中核 で ある 。
 カーネル と は 、 O S の 基本 モジュール         で ある 。

 狭義 の カーネル で あり 、 割り込み 処理 と システム サービス および プロセス
 (  a )           割り込み 処理 と システム サービス 及び  プロセス

 の それぞれ の 実行 を 管理 する   プロセス ディスパッチャ と を 統合 し た
 の それぞれ の 実行 を 管理 する 「 プロセス ディスパッチャ 」 を 統合 し た

 基本 機能 として 実現 する 。 O S の 管理 機能 の うち 、 プロセス 管理 機能
 基本 機能 として 実現 する 。 O S の 基本 機能 の うち 、 プロセス 管理 機能

 の 中核 は 、 この カーネル 機能 として 実現 する 。 
 の 中核 は 、 この カーネル 機能 として 実現 する 。 

のようになる。2行目の第2文側の先頭は、元は半角の「(a)」であるが、全角文字に変換してある。

レポート剽窃の観点からの評価は、これから行う必要があるが、現時点で明瞭に見えるのは、


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-05-28 (金) 18:01:55 (2672d)