張 洪， 鐘凱迪， 柴 源， 魏 濟， 吳 艷， 譚錦濤， 葉文韜

(1.成都大學 信息科學與工程學院, 四川 成都 610106；2.成都大學 模式識別與智能信息處理四川省高校重點實驗室, 四川 成都 610106)

0 引 言

隨著“大數(shù)據(jù)”時代的興起，由于大量的數(shù)據(jù)往往包含著許多重復與相似的部分，分析這類數(shù)據(jù)所得的結果總與實際偏差較大[1].隨著信息技術的發(fā)展，科研人員針對數(shù)據(jù)清洗技術方面的研究已經(jīng)取得了一定的成果[2].目前，數(shù)據(jù)清洗主要針對英文或數(shù)值型數(shù)據(jù)，而對于中文文本數(shù)據(jù)清洗方面的相關研究基本還是空白.所以，研究和發(fā)展基于中文的數(shù)據(jù)清洗技術具有重要的現(xiàn)實意義.研究表明，余弦相似度算法通過計算文本中2個向量的夾角余弦值來表示其統(tǒng)計學方法中的相似程度，其余弦相似度值越大表示文本之間的相似度越大[3].當面對大量的文本數(shù)據(jù)情況下，余弦相似度算法常被用來計算單文本對應的其他各文本之間的余弦相似度值，通過制定相應的閾值來給重復與相似的文本分類.但該算法的計算步驟隨著數(shù)據(jù)量的增加而呈幾何級增長，且十分冗雜[4].N-Gram算法是針對英文與數(shù)值的概率計算，通過計算文本中每個詞出現(xiàn)的概率計算出文本的概率，將其作為文本屬性值[5].事實上，文本之間的屬性值越相近，則表示文本之間的數(shù)據(jù)相似度越高[6].為了提高余弦相似度算法在海量數(shù)據(jù)中的計算速度以及減少因數(shù)據(jù)量增加而產(chǎn)生的誤差，本研究提出基于N-Gram的余弦相似度改進算法[7]，并對改進后的算法制定出一種合理的動態(tài)滑動窗口進行重復或相似檢驗.同時，通過對國家工商行政管理總局商標評審委員會網(wǎng)站獲取的數(shù)據(jù)進行算法測試，結果表明，基于N-Gram的余弦相似度改進算法結合動態(tài)滑動窗口策略具有更快的運行速度，且在數(shù)據(jù)量增加的情形下誤差也較小.

1 算法與改進

1.1 N-Gram算法

N-Gram算法認為：某條數(shù)據(jù)出現(xiàn)的概率與數(shù)據(jù)中包含的各個詞有著密切關系，因此可以用數(shù)據(jù)中每個詞出現(xiàn)的概率來描述該條數(shù)據(jù)出現(xiàn)的概率，且該條數(shù)據(jù)出現(xiàn)的概率即為其N-Gram值.當2個數(shù)據(jù)的N-Gram值越相近，則表示其相似程度越高.N-Gram算法的具體步驟如下：

1)對目標數(shù)據(jù)進行預處理，刪除其中的特殊字符與標點符號，并對數(shù)據(jù)進行分詞處理.

例如，待處理的數(shù)據(jù)有下列幾種：

S1=我剛剛?cè)tarbucks買了1杯Vanilla Latta和4塊Oatmeal Raisin Cookie.搭配起來還挺不錯的.

S2=Tom Robyn,對剛剛發(fā)生的事情感到很意外.

S3=Many people argue that living in the city has more advantages.

對這些數(shù)據(jù)預處理后的結果為(詞與詞之間用空格隔開):

S1=我 剛剛 去Starbucks買了 1杯 Vanilla Latta 和 4塊Oatmeal Raisin Cookie 搭配 起來 還 挺不錯 的

S2=Tom Robyn 對 剛剛 發(fā)生的 事情 感到 很意外

S3=Many people argue that living in the city has more advantages

2)對所有數(shù)據(jù)進行處理后，掃描所有數(shù)據(jù)的詞，建立語料庫，記錄每個詞出現(xiàn)的次數(shù)，記為N.

3)處理后的某條數(shù)據(jù)進行N元分割處理，即取出該條數(shù)據(jù)的具有N個詞的子字符串.當N=2時，處理后的數(shù)據(jù)如下所示：

S1={“我 剛剛"，“剛剛 去"，“去 Starbucks"，“Starbucks 買了"，“買了 1杯"，“1杯 Vanilla"，“Vanilla Latta"，“Latta 和"，“和 4塊"，“4塊 Oatmeal"，“Oatmeal Raisin"，“Raisin Cookie"，“Cookie 搭配"，“搭配 起來"，“起來 還"，“還 挺不錯"，“挺不錯 的"}

S2={“Tom Robyn"，“Robyn對"，“對 剛剛"，“剛剛 發(fā)生的"，“發(fā)生的 事情"，“事情 感到"，“感到 很意外"}

S3={“Many people"，“people argue"，“argue that"，“that living"，“l(fā)iving in"，“in the"，“the city"，“city has"，“has more"，“more advantages"}

4)各條數(shù)據(jù)出現(xiàn)的概率與數(shù)據(jù)中的詞密切相關，而數(shù)據(jù)中某詞出現(xiàn)的概率與其前面的詞息息相關.利用馬爾科夫概率計算公式，

P(S)=P(c1c2c3…cn)

=P(c1)P(c2|c1)P(c3|c2c1)…P(cn|cn-1cn-2…c1)

(1)

其中，P(S)為整條數(shù)據(jù)出現(xiàn)的概率，而c為對應的詞.顯然可見，當數(shù)據(jù)的詞量越大時，cn-1cn-2…c1等計算量越大，模型也更加冗雜.

對此，馬爾可夫提出了簡化的計算方法，假設該條數(shù)據(jù)中某個詞的出現(xiàn)概率僅與前一個詞有關，則式(1)可簡化為，

P(S)≈P(c1)P(c2|c1)P(c3|c2)…P(cn|cn-1)

(2)

實際計算式為，

(3)

其中，N(c)為詞c出現(xiàn)的次數(shù).

5)通過以上計算出的數(shù)據(jù)出現(xiàn)概率即為該條數(shù)據(jù)的N-Gram值，也可看成是該條數(shù)據(jù)的屬性.

通過計算每條數(shù)據(jù)的N-Gram值，并對所有數(shù)據(jù)進行排序，利用滑動窗口等方法，對數(shù)據(jù)進行比較或求閾值，就能找出數(shù)據(jù)中重復與相似的部分.

1.2 余弦相似度算法

余弦相似度用空間中2個向量的余弦值來表示它們之間的相似程度：當余弦值越接近1時，2個向量之間的夾角值越接近0°，則2個向量的相似程度就越大.相反，當余弦值越接近0時，2個向量的夾角越接近90°，其相似度就越小.余弦相似度算法本身的特點導致其更適合處理較少量的數(shù)據(jù)，而面對大量數(shù)據(jù)的情形時，往往會導致計算緩慢且冗雜.

1.3 改進余弦相似度算法

相似度算法在數(shù)據(jù)量較大的情況下進行數(shù)據(jù)挖掘，往往需要進行重復與相似數(shù)據(jù)的清洗.本研究通過N-Gram算法的排序思路改進余弦相似度算法，并采用動態(tài)滑動窗口對重復與相似記錄進行清洗，其數(shù)據(jù)清洗流程圖如圖1所示.

圖1重復與相似數(shù)據(jù)清洗流程圖

改進余弦相似度算法首先對清洗的數(shù)據(jù)進行預處理，即去掉標點符號與特色字符，并進行分詞操作.本研究采用Python的jieba庫進行精確分詞，分詞主要有兩種模式：在不存在冗余的情形下把文本精準切分的精確模式；把文本中所有可能的詞語都掃描出來的全模式.分詞后，本研究再通過N-Gram算法計算出每條數(shù)據(jù)的N-Gram值，對數(shù)據(jù)進行排序處理.

同時，算法還采用動態(tài)滑動窗口對數(shù)據(jù)進行分組：當某窗口的N-Gram值相對差別較小時，則增加該窗口的大小來提高計算的準確性；而當窗口的N-Gram值相對差別較大時，則減小該窗口的大小來提高運算的速率.

Wi表示第i個窗口的大小，通過窗口中數(shù)據(jù)的離散程度來改變窗口的大小.Si表示窗口中的N-Gram值的方差，則動態(tài)滑動窗口大小為，

(4)

其中，n為窗口的動態(tài)變化量.

在本研究中，窗口變化有以下情形：

1)窗口大小向窗口中第一條數(shù)據(jù)往上變化，若運行至總數(shù)據(jù)開端處，則停止變化.此種方式能更全面處理重復與相似數(shù)據(jù).

2)窗口大小向窗口最后一條數(shù)據(jù)往下變化，若運行至總數(shù)據(jù)的最后一條，則固定窗口大小且停止移動.此種方式能使運算過程更加快捷.

在研究中，采用余弦相似度算法計算滑動窗口中重復與相似的數(shù)據(jù)，對滑動窗口中的數(shù)據(jù)進行預處理，得到分詞的數(shù)據(jù)，選取窗口中的2條數(shù)據(jù)，掃描此2條數(shù)據(jù)的所有詞匯，制定出該次計算的語料庫.根據(jù)語料庫，本研究計算出2條數(shù)據(jù)的詞頻向量，并根據(jù)詞頻向量得出其余弦相似度值，如式(5)所示，

(5)

當余弦值大于規(guī)定的其閾值時，即判定此2個數(shù)據(jù)為重復與相似的.例如，2條數(shù)據(jù)進行預處理后的結果如下所示：

S1={“當"，“1個"，“量"，“在"，“1個"，“既定的"，“時間"，“周期"，“中"，“其"，“百分比"，“增長"，“是"，“1個"，“常量"，“時"，“這個"，“量"，“就"，“顯示"，“出"，“指數(shù)"，“增長"}

S2={“當"，“1個"，“量"，“在"，“1個"，“既定的"，“周期"，“中"，“呈現(xiàn)"，“出"，“指數(shù)"，“增長"，“其"，“百分比"，“增長"，“是"，“1個"，“常量"}

本研究計算每個詞出現(xiàn)的次數(shù)，構成對應的字典，即為語料庫：

Corpus={‘當'：2，‘1個'：6，‘量'：3，‘在'：2，‘既定的'：2，‘時間'：1，‘周期'：2，‘中'： 2，‘其'：2，‘百分比'：2，‘增長'：4，‘是'：2，‘常量'：2，‘時'：1，‘這個'：1，‘就'：1，‘顯示'：1，‘出'：2，‘指數(shù)'：2，‘呈現(xiàn)'：1}

通過語料庫得到對應的詞頻向量：

D1=[1,3,2,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,0]

D2=[1,3,1,1,1,0,1,1,1,1,2,1,1,0,0,0,0,1,1,1]

其余弦相似度為：

=0.8876

根據(jù)余弦相似度便可確定S1與S2為相似度極大的數(shù)據(jù).

2 結果及分析

在算法測試中，本研究根據(jù)上述算法，設計出對重復與相似數(shù)據(jù)清洗的實驗，并通過比較余弦算法、N-Gram算法及改進余弦算法的運行速度和準確率對實驗結果進行了分析和解讀.

1)通過獲取國家工商行政管理總局商標評審委員會網(wǎng)站的數(shù)據(jù)并存入SQL數(shù)據(jù)庫中，具體數(shù)據(jù)如圖2所示(因篇幅有限，SQL數(shù)據(jù)庫中僅列出部分數(shù)據(jù)).

圖2部分實驗數(shù)據(jù)表格

2)準確率能較好地展示算法的可行性與可用性，是評價算法好壞的重要指標，其計算式為，正確識別的重復相似數(shù)據(jù)/(錯誤識別的重復相似數(shù)據(jù)+正確識別的重復相似數(shù)據(jù)).

3)實驗采用jieba庫的精準分詞，初始動態(tài)移動窗口大小為5，動態(tài)變化量選取3，且以窗口末端進行變化，改進余弦相似度算法設定0.8為重復相似數(shù)據(jù)閾值，并以每百條數(shù)據(jù)為1個記錄點.數(shù)據(jù)清洗一次得到的實驗結果如圖3所示.

圖3數(shù)據(jù)清洗準確率圖

由圖3可知，改進余弦相似度算法準確率明顯高于N-Gram算法，且隨著數(shù)據(jù)量的增加，其準確率也更加接近余弦相似度算法.

運行時間是評價算法實用性與復雜度的重要指標.數(shù)據(jù)量算法運行時間的變化如圖4所示.

圖4數(shù)據(jù)運行時間圖

由圖4可知，改進余弦相似度算法較余弦相似度算法更快地區(qū)分出重復與相似數(shù)據(jù)，且在數(shù)據(jù)量增加的情況下，其運行時間接近于運行較快的N-Gram算法.因此，改進余弦相似度算法擁有更好的實用性與較小的復雜度.

3 結 語

本研究通過對SQL數(shù)據(jù)庫(國家工商行政管理總局商標評審委員會網(wǎng)站)的數(shù)據(jù)進行測試.結果表明，改進余弦相似度算法在數(shù)據(jù)量越多的情況下?lián)碛懈叩臏蚀_率，相對于未改進的余弦相似度算法有著更低的運行時間，且在清洗大量重復與相似數(shù)據(jù)的過程中擁有更好的清洗結果.