基于N-Gram和動(dòng)態(tài)滑動(dòng)窗口的改進(jìn)余弦相似度算法研究

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

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

0 引 言

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

1 算法與改進(jìn)

1.1 N-Gram算法

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

1)對(duì)目標(biāo)數(shù)據(jù)進(jìn)行預(yù)處理，刪除其中的特殊字符與標(biāo)點(diǎn)符號(hào)，并對(duì)數(shù)據(jù)進(jìn)行分詞處理.

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

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

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

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

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

S1=我 剛剛 去Starbucks買了 1杯 Vanilla Latta 和 4塊Oatmeal Raisin Cookie 搭配 起來(lái) 還 挺不錯(cuò) 的

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

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

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

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

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

S2={“Tom Robyn"，“Robyn對(duì)"，“對(duì) 剛剛"，“剛剛 發(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ù)中的詞密切相關(guān)，而數(shù)據(jù)中某詞出現(xiàn)的概率與其前面的詞息息相關(guān).利用馬爾科夫概率計(jì)算公式，

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為對(duì)應(yīng)的詞.顯然可見(jiàn)，當(dāng)數(shù)據(jù)的詞量越大時(shí)，cn-1cn-2…c1等計(jì)算量越大，模型也更加冗雜.

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

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

(2)

實(shí)際計(jì)算式為，

(3)

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

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

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

1.2 余弦相似度算法

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

1.3 改進(jìn)余弦相似度算法

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

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

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

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

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

(4)

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

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

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

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

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

(5)

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

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

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

本研究計(jì)算每個(gè)詞出現(xiàn)的次數(shù)，構(gòu)成對(duì)應(yīng)的字典，即為語(yǔ)料庫(kù)：

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

通過(guò)語(yǔ)料庫(kù)得到對(duì)應(yīng)的詞頻向量：

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 結(jié)果及分析

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

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

圖2部分實(shí)驗(yàn)數(shù)據(jù)表格

2)準(zhǔn)確率能較好地展示算法的可行性與可用性，是評(píng)價(jià)算法好壞的重要指標(biāo)，其計(jì)算式為，正確識(shí)別的重復(fù)相似數(shù)據(jù)/(錯(cuò)誤識(shí)別的重復(fù)相似數(shù)據(jù)+正確識(shí)別的重復(fù)相似數(shù)據(jù)).

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

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

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

運(yùn)行時(shí)間是評(píng)價(jià)算法實(shí)用性與復(fù)雜度的重要指標(biāo).數(shù)據(jù)量算法運(yùn)行時(shí)間的變化如圖4所示.

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

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

3 結(jié) 語(yǔ)

本研究通過(guò)對(duì)SQL數(shù)據(jù)庫(kù)(國(guó)家工商行政管理總局商標(biāo)評(píng)審委員會(huì)網(wǎng)站)的數(shù)據(jù)進(jìn)行測(cè)試.結(jié)果表明，改進(jìn)余弦相似度算法在數(shù)據(jù)量越多的情況下?lián)碛懈叩臏?zhǔn)確率，相對(duì)于未改進(jìn)的余弦相似度算法有著更低的運(yùn)行時(shí)間，且在清洗大量重復(fù)與相似數(shù)據(jù)的過(guò)程中擁有更好的清洗結(jié)果.