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

サイトトップ

ノート
データ処理
├マイニング
├バスケット解析
├バスケット解析をＲで
├図書貸出をＲで
├モデルクラスタリング
└
テキストマイニング
├テキストマイニングTM
├TMとシソーラス
├PubMedをTM
├TMとMeSH
├TMとNLTK
├テキストマイニングとtagger
├医薬品添付文書ＤＢ
├論文の処理1
├剽窃１
├Bing検索
└
分子進化学
├分子進化学
└
Pythonと論文アクセス
├Pythonを使ってみる
├PythonでPubMed
├Pythonで...続き
└
Macメモ
├Script

&ref(): File not found: "favicon_story.txt" at page "ノート/ノート";

自信ないので
├Winのバッチ
│├スクリプト入門
│├バッチファイル
│├SETコマンド
│├自分のメモ
│└
└

メニュー編集

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

前振り
剽窃１で議論したように、レポートの類似性を判定する方法として、まずは単語の出現頻度分布のパターンの類似性を測る方法が考えられている。実際、かなりよく類似性が検出できると思われる。
別の方法として、出現頻度分布ではなく、単語の並びとしてみる方法が考えられるだろう。英語では既に、遺伝子の配列の類似性を検出するのに使われる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のプログラムがそのまま使えそうなので、何が起こるか試してみよう。

↑

道具立て †

楽をしたいので、制御は原則Pythonを使う
Smith-Watermanのアルゴリズムは、その昔Pythonの勉強のために書いたプログラムをほとんどそのまま使う。
かなり手抜きだが、動作原理を確認するための第０版としては、そのままでよいことにする。パフォーマンス等は全部がうまく行ったらゆっくり考えよう。
形態素解析は必要である。英文の場合は単語分割は自明だが、日本語の場合はそれなりの形態素解析が必要になる。
ここでは、chasenを借用する。Pythonからのインターフェースは簡単なものを自作したものを使う。－－＞ノート/テキストマイニング/oregano3
単語分割の出力の具合、特に合成語についてどう分割するか、英字の略語などにどう対応するかなどは、かなり結果に影響する可能性がある。しかし、まずは原理が動作することを確かめる目的なので、これも後から考えることにする。
データはいろいろなものを試してみる。まずは、剽窃1の実験で使った、学生の書いた宿題レポートについて、学生間の類似度を試してみよう。

↑

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)]

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

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)

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

#!/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はすべて３倍（３バイトで１文字）を返している。ここはもう少し整理して依存性をなくしたい。ユニコードの場合一般にはlen関数は文字数を返すはずなのだが。

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

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

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

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

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

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

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

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

第１文と第２文の差が、目に見える形で表示できる。どちらが元でどちらが書換えたものかは、確実に判定できるルールにまでは考えていないが、何となく見える気がする。
剽窃1の方法とのこまかい比較は未だであるが、語の順番を考慮するという点でこの方法が優れているのに対し、盗んだ後で語の順番（特に文の順番）を変えると、この方法では検出できないだろう。
なお、検出のためのスコア（２文の距離尺度）はまだ計算していないので、剽窃１の方法と直接比較はまだやっていない。

最新の5件

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

原理 †

道具立て †

Smith-Watermanのアルゴリズム †

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