基于SNM算法的大數據量中文商品清洗方法?

張苗苗 蘇 勇

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

近些年，龐大數據量和其中隱藏的規律，帶動數據挖掘技術日新月異的發展［4］。數據挖掘的成功與否主要取決于數據源的質量高低和數據挖掘技術是否合適，而影響數據源質量的一個重要因素就是臟數據的存在［5］。不一致或陳舊的數據、不精確的數據以及人為造成的錯誤數據等是臟數據形成的原因［6］。目前，國內外的相關研究人員已經開展了一些關于數據的研究，誠然如此，相當一部分的成果所針對的語言僅僅是英文，由于中文數據之間存在空格間隔，所以對于中文的數據清洗還沒有充分研究，這對識別造成一定的困難［7～8］。目前中文數據清洗在國內研究還很少，取得的效果也并不多。所以，數據清洗的研究存在很大的發展空間，具備很好的應用遠景和理論價值。本文將介紹數據清洗，并將側重基于SNM算法對中文數據清洗的應用，通過介紹傳統的SNM算法理論［9］，論述其算法的缺陷，針對缺陷進項改進，并提出實際上的應用場景。

2SNM算法

數據清洗從理論上說就是先分析“臟數據”產生原因和存在形式，再利用現有的方式和技術去清洗臟數據，從而將它們轉為滿足要求的數據，以此來提高數據集的質量［10］。Hemandez等于20世紀90年代中期提出了鄰近排序算法（Sorted-Neighborhood Method，SNM算法）。SNM是數據清洗過程中的經典算法，該算法的基本思想是：

1）對數據集產生關鍵屬性；

2）將所有數據按照第一步產生的關鍵屬性進行排序；

3）根據排序好的數據集，設置固定大小為W的滑動窗口，窗口中的第一條數據和其余W-1條數據比較，若符合相似性判斷準則，則刪除此數據。窗口內最后一條數據的下一條數據可以進入窗口，第一條數據滑出窗口，如圖1所示。

圖1 滑動窗口掃描排序數據集

SNM算法采用滑動窗口的方式［11］，通過比較窗口中的W條記錄，這樣只需要比較W×N次，而W比N小的多，明顯提高了字符的匹配效率。但是，SNM 方法存在以下缺陷［12～13］：

1）嚴重依賴匹配關鍵字是否排序；

2）很難實現滑動窗口大小W的精確控制。

3SNM算法的改進

針對SNM算法過于依賴關鍵字的選擇［14］，本文將采取對關鍵字進行標準化來處理。標準化分為兩種情況補全和分割，使SNM算法在相同運算環境下對中文數據清洗在執行時間上有明顯的改進。其基本思想是：

1）補全（補充特征字）：運營商的每個商品應該由品牌、商品名稱和型號3部分組成，如牙刷，從字面看屬于重復記錄，但從品牌來分，就可分為不同，如A、B、C，A為三笑牌，B、C為佳潔士牌，則A與B、C不屬于重復記錄，但B、C從型號上分也可不同，如B為大刷頭，C為小刷頭（B、C型號不同）。則B、C也不屬于重復記錄。因此，在數據清洗前可將每個商品進行補全操作，實現“品牌+商品名稱+型號”的標準化形式。

2）分割排序（調整特征字排序）：如“50ml牛奶A”和“牛奶A 50ml”兩個字段，按照傳統SNM算法排序兩個字段會相距很遠，但這兩個字段屬于重復記錄。因此，在數據清洗前可將每個商品進行分割排序操作，將“50ml”和“牛奶A”兩個字段分開，再進行排序，再添加品牌特征字，實現“品牌+商品名稱+型號”的標準化形式。

4 實驗結果與性能分析

為驗證本文提出方法的有效性，將改進方法與SNM方法進行對比實驗。實驗環境：實驗軟件平臺為Windows10系統，數據庫為MySQL，程序用Java語言編寫，計算機硬件環境為Intel? Core?i5-5200UCPU@2.20GHz，4GB內存。

一般衡量重復數據與孤立數據的標準用召回率（Recall）與查準率（Precision）［15］：

當這兩個判斷準則都較高時，那么算法的有效性就越高。

針對運營商的543010條商品數據集，首先隨機取1000個數據，隨機排列，運用商品名name作為關鍵屬性，對其進行分詞，然后設置窗口寬度為4，再以此實驗五次。

分別帶入改進的SNM算法與傳統的SNM算法進行對比，圖2為準確率的圖像對比。

圖2 重復數據查詢準確率分析圖

經過對比發現，改進后的SNM算法在查全率與查準率上達到80%與90%的水平，可以認為準確率較高，比原有的算法有所改進。

5 結語

從數據清洗基本原理的根本上進行分析，論述中文數據清洗技術。先從國內外兩方面分析中文數據清洗的研究情況及研究熱點，提出當前數據清洗研究的方向。再粗略介紹數據清洗的原理及方法。在其根本上分析和研究基于SNM算法的大數據量中文商品清洗方法，概述算法的優缺點及適用范圍。最后，指出中文數據重復清洗技術研究的不足之處，目前，中文數據清洗的研究在國內研究的還很少，以致獲得的成果也并不多。所以，中文數據清洗的研究的空間很大，具備很好的應用遠景與理論價值。但在這種情況下，中文數據重復清洗算法的研究還存在許多不足的地方，例如：

1）對中文數據重復清洗工具的開發及研究：到目前為止，數據清洗主要應用于英文，因為中英文的語言存在差別，以致大多數英文數據清洗算法不適用于中文上。

2）在中文重復數據記錄檢測算法需要改進：即便此刻已有很多相關算法被提出，但由于識別效率低、識別精度不高，仍需要在已有的算法基礎上進行。

3）中文數據清洗工具之間的互操作性：中文數據清洗工具較少，并且這些工具基本上都是通過已有的語言并根據自身的需要經過擴展實現的，不能很好地滿足中文數據清洗中大致匹配的需要，不具備互操作性。

4）中文數據清理方案的通用性：中文特定領域的數據清洗問題依然是研究和應用重點，但較通用的清洗方案會受到越來越多的關注。