一種用于中文數(shù)據(jù)清洗的近鄰排序算法

張培根 黃樹成

(江蘇科技大學(xué)計算機學(xué)院 江蘇 鎮(zhèn)江 212003)

0 引 言

數(shù)據(jù)挖掘中，數(shù)據(jù)往往都不可避免地存在著缺失數(shù)據(jù)、冗余數(shù)據(jù)、不確定數(shù)據(jù)和不一致數(shù)據(jù)等多種問題[1]。在各個領(lǐng)域中，重復(fù)數(shù)據(jù)這一問題都是不容忽視的。尤其是目前的數(shù)據(jù)收集工作，已漸漸從人工搜集轉(zhuǎn)變?yōu)闄C器搜集。并且，由于數(shù)據(jù)量的急速膨脹，導(dǎo)致各種數(shù)據(jù)質(zhì)量問題屢見不鮮，在這中間數(shù)據(jù)重復(fù)尤為常見。導(dǎo)致數(shù)據(jù)中存在大量重復(fù)的因素有許多，例如數(shù)據(jù)收集條件的制約、度量方法錯誤、人工錄入時出現(xiàn)錯誤和違反數(shù)據(jù)約束等[2]。在某些領(lǐng)域中的數(shù)據(jù)庫中重復(fù)值比例高達(dá)50%～60%[3]。這些不完整的數(shù)據(jù)不僅意味著信息空白，更重要的是它會影響后續(xù)數(shù)據(jù)挖掘抽取模式的正確性和導(dǎo)出規(guī)則的準(zhǔn)確性[4]。因此，如何處理重復(fù)數(shù)據(jù)已成為數(shù)據(jù)清洗及數(shù)據(jù)預(yù)處理領(lǐng)域研究的主要問題之一。

追溯到1959年，數(shù)據(jù)清洗首先出現(xiàn)在美國，被應(yīng)用于全美社會保險號的糾正。隨著美國商業(yè)和經(jīng)濟發(fā)展，數(shù)據(jù)清洗被大范圍地應(yīng)用，刺激了該方向的研究。雖然國外對中文數(shù)據(jù)清洗的研究并不突出，但是英文的數(shù)據(jù)清洗技術(shù)和相關(guān)理論已經(jīng)相當(dāng)完善[5]。由于中英文本身表達(dá)、語法和語義等存在的差異和國情差距，而且中文數(shù)據(jù)清洗技術(shù)的研究起步晚，現(xiàn)階段全世界對中文數(shù)據(jù)清洗的成果不是很充足[6]。國內(nèi)對數(shù)據(jù)清洗的研究主要在數(shù)據(jù)倉庫、決策支持、數(shù)據(jù)挖掘等方面，商業(yè)性的數(shù)據(jù)清洗主要存在于各個領(lǐng)域，沒有完整的理論性結(jié)論[7]。隨著國內(nèi)經(jīng)濟發(fā)展，中文數(shù)據(jù)清洗將取得眾多成果。

本文研究了近鄰排序算法(SNM)在中文重復(fù)值清洗中的應(yīng)用。近鄰排序算法在英文重復(fù)值清洗中的高效性取決于英文的語義和時態(tài)是基于單詞的。然而中文是以中文詞語為單位，并存在眾多近義詞成分，這是中英文重復(fù)值清洗研究存在巨大差異的根本原因[8]。因此，本文在傳統(tǒng)近鄰排序算法基礎(chǔ)上，設(shè)計了一種改進(jìn)的算法：基于編輯距離的近鄰排序算法。新算法首先對編輯距離求相似度的算法進(jìn)行引入，相比于現(xiàn)階段大多數(shù)相似度算法，編輯距離(從A字符串變?yōu)锽字符串需要最小的修改次數(shù))的概念更適合中文求相似度；其次，引入IKAnalyzer對中文語句進(jìn)行分詞，將分詞結(jié)果與中文近義詞庫進(jìn)行對比。如果原本字面不相同的詞語被判定為同義詞，則算法同樣認(rèn)為這兩個詞語是無需修改的，所以編輯代價為0。

1 改進(jìn)的基于編輯距離的近鄰排序算法

1.1 基于編輯距離的近鄰排序算法

相似重復(fù)記錄清洗算法主要有以下兩個評價標(biāo)準(zhǔn)：

標(biāo)準(zhǔn)1記憶率是識別出的相似重復(fù)記錄數(shù)占所有相似重復(fù)記錄數(shù)的百分比。

標(biāo)準(zhǔn)2準(zhǔn)確率是指在算法識別出的相似重復(fù)記錄里,那些真正的相似重復(fù)記錄所占的百分比[9]。

在常規(guī)的重復(fù)值清洗算法的研究中，重復(fù)值清洗最可靠的方法是嵌套循環(huán)法，具體而言就是對數(shù)據(jù)庫的數(shù)據(jù)進(jìn)行遍歷，但是時間復(fù)雜度太大，需要N(N-1)/2次比較,其中N是數(shù)據(jù)倉庫中記錄的總數(shù)[10]。排序合并方法是對數(shù)據(jù)集進(jìn)行排序，之后對相鄰記錄比較，該方法已經(jīng)成為現(xiàn)階段數(shù)據(jù)庫級重復(fù)值清洗的主流思想，也是眾多優(yōu)化算法的思想基礎(chǔ)[11]。

傳統(tǒng)近鄰排序算法思路為：依據(jù)數(shù)據(jù)集實際含義，選出最具有代表性的某一列為關(guān)鍵字，以該關(guān)鍵字為依據(jù)對整個數(shù)據(jù)集進(jìn)行排序，使大致相似的字段靠近；在排序后的數(shù)據(jù)集上加上大小為w的滑動窗口，每次對滑動窗口內(nèi)數(shù)據(jù)進(jìn)行遍歷檢查[12]。如圖1所示。

圖1 近鄰排序算法示意圖

滑動窗口包含w條記錄,每條新進(jìn)入窗口的記錄都要與先前進(jìn)入窗口的w-1條記錄依次對比是否為重復(fù)記錄,窗口往下移一位,再把新的w條記錄按照之前的方法迭代進(jìn)行,直到數(shù)據(jù)集的最后。在數(shù)據(jù)集數(shù)據(jù)條數(shù)過多的情況下采用滑動窗口技術(shù)，準(zhǔn)確率有所提高的基礎(chǔ)上，很大程度上減少運行次數(shù)，提高運行效率，但該算法依然存在兩點不足。(1) 太依賴于關(guān)鍵字的選取，關(guān)鍵字選擇的成功與否，很大程度上影響了該關(guān)鍵字是否反映現(xiàn)實對象特征，如果失敗，將無法使相似記錄聚集在一起而失去重復(fù)值清洗的意義[13]。(2) 合適的窗口大小很難選取，每個數(shù)據(jù)集大致相似記錄數(shù)量各異，窗口過大，則時間增加；窗口過小，容易漏掉相似記錄，影響匹配效率[14]。

高職課程學(xué)習(xí)效果評價指標(biāo)千差萬別，設(shè)計一套具有普適性且科學(xué)、合理，能充分激發(fā)學(xué)生學(xué)習(xí)興趣和潛能，便于實施的基于能力本位的評價體系非常必要。依據(jù)工學(xué)結(jié)合的教學(xué)模式和以就業(yè)為導(dǎo)向的培養(yǎng)目標(biāo)，通過梳理企業(yè)崗位能力，可以將高職課程學(xué)習(xí)效果評價指標(biāo)分解為專業(yè)核心能力、職業(yè)核心能力、職業(yè)素養(yǎng)三大部分[3]。專業(yè)核心能力是基礎(chǔ)、針對性強，職業(yè)核心能力和職業(yè)素養(yǎng)作為職業(yè)導(dǎo)向，具有普適性。

該算法采用滑動窗口技術(shù),減少了比較次數(shù),也能有基本滿意的記憶率和準(zhǔn)確率，但是該算法有兩點不足。(1) 對關(guān)鍵字依賴程度太大,若選取的關(guān)鍵詞本身錯誤嚴(yán)重或不能反映現(xiàn)實對象的特征,則真正重復(fù)的記錄不能聚集在一定范圍內(nèi)，失去匹配比較的機會。(2) 窗口大小w很難選取，窗口過大,則比較時間增加；窗口過小，則容易漏掉重復(fù)記錄。

近鄰排序算法的優(yōu)點顯而易見，但是針對缺點，后續(xù)產(chǎn)生了眾多優(yōu)秀的優(yōu)化算法，比如Hernandez等[15]提出了多趟近鄰排序算法MPN算法，利用多趟排序，來減少不恰當(dāng)?shù)年P(guān)鍵字對整個清洗結(jié)果的影響，同時可以考慮聯(lián)合關(guān)鍵字排序。并且承認(rèn)傳遞閉包關(guān)系，認(rèn)為記錄R1與R2互為重復(fù)記錄,R2與R3互為重復(fù)記錄,則R1與R3互為重復(fù)記錄。

1.2 改進(jìn)算法的策略

本文從以下幾個方面對近鄰排序清洗重復(fù)值算法進(jìn)行改進(jìn)。

(1) 語義方面，中英文有顯而易見的差異。首先英文語義基于單詞，而中文語義基于詞語[16]；其次，根據(jù)每個英文單詞語義，可以直接拼接出整個語句的語義，但是中文語句不存在明顯的語義分隔符，更無法根據(jù)單個文字語義拼接出整個語句的語義。在中英文表述方面，英語是形合語言，注重句法平面，而漢語是意合語言，注重語義平面[17]。

改進(jìn)算法思想：

傳統(tǒng)編輯距離算法應(yīng)用于中文相似度計算時，一般以字為單位計算字符串之間的編輯距離，但是此種方法的計算結(jié)果往往存在于字面本身并且與中文語句的實際語義出入較大，而且計算過程中，對每個字符的計算需要可考慮到語句長短對整個語句計算時間的影響。針對以上情況，本文考慮采用中文分詞的方法解決。即在此采用IKAnalyzer中文分詞模塊，隨后以詞語為單位進(jìn)行編輯距離的計算，從而在滿足相似度計算要求的同時，更符合中文的使用環(huán)境，計算速度和準(zhǔn)確率也會有相應(yīng)的提高。

(2) 英文的語義和時態(tài)直接反應(yīng)在英文語句的特定單詞中，而漢語有時需要讀者自己“體會”。再者，漢語中常見的同音詞、同義詞在英文中較少出現(xiàn)。最后，在中英文提取縮寫的過程中，英文語句本身存在自然分隔符，可以輕易通過首字母大寫提取出縮寫，而漢語是雙字節(jié)編碼，很難得到統(tǒng)一的縮寫方式[18]。綜合以上三點，這給將英文中成熟的重復(fù)值清洗算法應(yīng)用到中文分詞中帶來了巨大難度。

改進(jìn)算法思想：

采用分詞的思想來計算編輯距離，雖然以詞語為單位很大程度上提高了計算效率，但是與中文的實際應(yīng)用場景存在很多不符之處，尤其兩詞為同義詞時，實際一個意思，但會被傳統(tǒng)編輯距離算法認(rèn)為是不同意思。針對這些情況，考慮在進(jìn)行編輯距離的計算時采用以下方式：“計算編輯距離的過程中，如果兩詞條字面完全一樣，則編輯代價cost為0；如果兩詞條字面不一樣，則編輯代價cost為1；”利用同義詞庫變更為：“如果兩詞條相互同義，則編輯代價cost為0；如果兩詞條不互為同義詞，則編輯代價cost為1；”從而使計算結(jié)果更符合字符串詞語相似度計算的要求。

1.3 改進(jìn)算法的步驟

改進(jìn)的基于中文分詞和同義詞檢查的近鄰排序算法的具體描述如下：

輸入：含有m個對象的數(shù)據(jù)集D

輸出：被判定為重復(fù)值的對象以及相似對象的個數(shù)和數(shù)據(jù)集D對象的總個數(shù)

方法：

Step1選取關(guān)鍵列，依照該關(guān)鍵字對數(shù)據(jù)集D進(jìn)行排序，排序后的數(shù)據(jù)集為D′。

Step2設(shè)置大小為w的滑動窗口，在該窗口內(nèi)，以第w-1為基礎(chǔ)，依次對比從w-2到0的對象。

Step3在對比過程中采用優(yōu)化后的編輯距離算法，首先，通過IKAnalyzer進(jìn)行中文分詞；其次，引入同義詞庫，對分詞后的對象中每個相對應(yīng)詞語進(jìn)行同義詞對比，若判定為同義詞，則編輯代價為0。

Step4初始滑動窗口的大小一般為3，但是由于數(shù)據(jù)集的不同或者大致相似數(shù)據(jù)的多少的差異，窗口大小不能一概而論。在完成以上三步的基礎(chǔ)上，對窗口大小進(jìn)行縮放后重復(fù)以上三步，得出在窗口大小不同的情況下重復(fù)值清洗的差異。

Step5得到在不同數(shù)據(jù)集下相似度隨著w大小變化而產(chǎn)生的折線圖。

2 實驗結(jié)果

本實驗的數(shù)據(jù)集采用供應(yīng)商商品庫存數(shù)據(jù)集，該數(shù)據(jù)集具有6個屬性，1 044條數(shù)據(jù)。

本文采用正確率來衡量算法的清洗精度。實驗最終，將經(jīng)過算法清洗的數(shù)據(jù)集與原始數(shù)據(jù)集進(jìn)行比較，通過計算正確率來體現(xiàn)清洗算法的匹配程度。正確率計算方法如下：

式中：m是正確清洗出重復(fù)值的屬性個數(shù)，n為原始數(shù)據(jù)集中重復(fù)的屬性值個數(shù)，P為清洗算法的正確率。當(dāng)P值為0時，表示所有清洗結(jié)果都錯誤；相反，當(dāng)P值為1時，所有清洗結(jié)果都正確。

實驗結(jié)果及分析：

從圖2可以看出，對于原近鄰排序算法，并非w值越大重復(fù)值清洗效果就越好，而且w的取值沒有規(guī)律可循，當(dāng)與數(shù)據(jù)集的分類吻合時，其實驗結(jié)果較好。

圖2 基于近鄰排序算法不同w值下的精確度曲線

從圖3可以看出，重復(fù)較多的情況下，清洗的精確度普遍較高，當(dāng)重復(fù)值比例20%左右的時候，精確度降低。

圖3 不同算法不同重復(fù)比例下的精確度曲線

通過表1可以看出，雖然原近鄰排序算法正確率比較可觀，但是結(jié)合中文分詞和同義詞檢查之后，改進(jìn)后的近鄰排序算法更適合普遍中文文本的重復(fù)值清洗，正確率有顯著提高。

表1 不同清洗算法最優(yōu)正確率對比表

3 結(jié) 語

本文提出了一種基于中文分詞和同義詞檢查的近鄰排序優(yōu)化算法。首先，考慮到中英文的語義、時態(tài)、提取縮寫等方面本身存在的差異性，本文在沿用編輯距離的情況下，采用中文分詞和同義詞檢查的方法，對近鄰排序算法加以改進(jìn)。其次，在實驗過程中，合適的窗口大小、關(guān)鍵字的選擇等方面對算法的實際效果存在影響。本文通過在不同窗口大小下對同一個數(shù)據(jù)集的實驗，得出結(jié)論：若想得到最合適的結(jié)果，需多次試驗獲得最合適的窗口大小。綜上所述，在將近鄰排序算法應(yīng)用于中文重復(fù)值清洗的過程中，該優(yōu)化算法在取得預(yù)期清洗結(jié)果的同時，在一定程度上提升了效果。