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

張培根 黃樹成

(江蘇科技大學(xué)計(jì)算機(jī)學(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(jī)器搜集。并且，由于數(shù)據(jù)量的急速膨脹，導(dǎo)致各種數(shù)據(jù)質(zhì)量問題屢見不鮮，在這中間數(shù)據(jù)重復(fù)尤為常見。導(dǎo)致數(shù)據(jù)中存在大量重復(fù)的因素有許多，例如數(shù)據(jù)收集條件的制約、度量方法錯誤、人工錄入時(shí)出現(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)用于全美社會保險(xiǎn)號的糾正。隨著美國商業(yè)和經(jīng)濟(jì)發(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)濟(jì)發(fā)展，中文數(shù)據(jù)清洗將取得眾多成果。

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

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

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

相似重復(fù)記錄清洗算法主要有以下兩個評價(jià)標(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)行遍歷，但是時(shí)間復(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ù)集實(shí)際含義，選出最具有代表性的某一列為關(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ǔ)上，很大程度上減少運(yùn)行次數(shù)，提高運(yùn)行效率，但該算法依然存在兩點(diǎn)不足。(1) 太依賴于關(guān)鍵字的選取，關(guān)鍵字選擇的成功與否，很大程度上影響了該關(guān)鍵字是否反映現(xiàn)實(shí)對象特征，如果失敗，將無法使相似記錄聚集在一起而失去重復(fù)值清洗的意義[13]。(2) 合適的窗口大小很難選取，每個數(shù)據(jù)集大致相似記錄數(shù)量各異，窗口過大，則時(shí)間增加；窗口過小，容易漏掉相似記錄，影響匹配效率[14]。

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

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

近鄰排序算法的優(yōu)點(diǎn)顯而易見，但是針對缺點(diǎn)，后續(xù)產(chǎn)生了眾多優(yōu)秀的優(yōu)化算法，比如Hernandez等[15]提出了多趟近鄰排序算法MPN算法，利用多趟排序，來減少不恰當(dāng)?shù)年P(guān)鍵字對整個清洗結(jié)果的影響，同時(shí)可以考慮聯(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)用于中文相似度計(jì)算時(shí)，一般以字為單位計(jì)算字符串之間的編輯距離，但是此種方法的計(jì)算結(jié)果往往存在于字面本身并且與中文語句的實(shí)際語義出入較大，而且計(jì)算過程中，對每個字符的計(jì)算需要可考慮到語句長短對整個語句計(jì)算時(shí)間的影響。針對以上情況，本文考慮采用中文分詞的方法解決。即在此采用IKAnalyzer中文分詞模塊，隨后以詞語為單位進(jìn)行編輯距離的計(jì)算，從而在滿足相似度計(jì)算要求的同時(shí)，更符合中文的使用環(huán)境，計(jì)算速度和準(zhǔn)確率也會有相應(yīng)的提高。

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

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

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

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)行同義詞對比，若判定為同義詞，則編輯代價(jià)為0。

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

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

2 實(shí)驗(yàn)結(jié)果

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

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

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

實(shí)驗(yàn)結(jié)果及分析：

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

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

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

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

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

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

3 結(jié) 語

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