李碧秋，王佳斌

基于Mahout的相似重復(fù)數(shù)據(jù)清洗策略研究＊

李碧秋，王佳斌

（華僑大學(xué) 工學(xué)院，福建 泉州 362021）

針對(duì)在海量日志記錄中無(wú)法有效抽取高價(jià)值的數(shù)據(jù)問(wèn)題，提出一種基于Mahout的k-means短文本聚類清洗算法，利用開(kāi)源機(jī)器學(xué)習(xí)算法庫(kù)Mahout，將文本聚類與數(shù)據(jù)清洗相結(jié)合，通過(guò)聚類檢測(cè)相似重復(fù)記錄，有效提升重復(fù)數(shù)據(jù)清洗速率。實(shí)驗(yàn)結(jié)果表明，該方法在保證較高查全率與查準(zhǔn)率的同時(shí)，比傳統(tǒng)相似重復(fù)數(shù)據(jù)清洗算法更具有擴(kuò)展性，這對(duì)大數(shù)據(jù)的處理有較強(qiáng)的實(shí)用意義。

數(shù)據(jù)清洗；k-means；相似重復(fù)記錄；文本聚類

1 引言

在信息爆炸的大數(shù)據(jù)時(shí)代，大數(shù)據(jù)系統(tǒng)已被許多領(lǐng)域廣泛采用，提供有效的數(shù)據(jù)解決方案。大數(shù)據(jù)系統(tǒng)產(chǎn)生大量的非結(jié)構(gòu)化日志，其中隱藏了許多有價(jià)值的信息。但是僅注意數(shù)據(jù)分析而不重視數(shù)據(jù)質(zhì)量問(wèn)題可能會(huì)使研究或分析變得毫無(wú)意義，甚至導(dǎo)致災(zāi)難性的后果。因此，對(duì)于大數(shù)據(jù)分析和挖掘，數(shù)據(jù)質(zhì)量起著關(guān)鍵作用，數(shù)據(jù)清理是保證數(shù)據(jù)質(zhì)量的強(qiáng)大工具。目前，對(duì)大數(shù)據(jù)的數(shù)據(jù)清理包括保證數(shù)據(jù)一致性和完整性、實(shí)體標(biāo)識(shí)、數(shù)據(jù)預(yù)處理等，其中針對(duì)冗余數(shù)據(jù)的檢測(cè)與刪除具有顯著的優(yōu)勢(shì)，可以減少冗余數(shù)據(jù)的存儲(chǔ)與不必要的網(wǎng)絡(luò)帶寬，提高系統(tǒng)的可伸縮性。傳統(tǒng)的重復(fù)數(shù)據(jù)清洗主要是針對(duì)結(jié)構(gòu)化數(shù)據(jù)在本地處理，這種方法已經(jīng)不能滿足海量待處理數(shù)據(jù)的需求，而Hadoop作為一種著名的開(kāi)源大數(shù)據(jù)編程框架，為人們提供了分布式存儲(chǔ)和分布式計(jì)算技術(shù)，已經(jīng)被應(yīng)用于谷歌、Facebook、騰訊、阿里巴巴等大型互聯(lián)網(wǎng)公司。其生態(tài)圈的組件之一Mahout集成了多種聚類、分類等算法，為人們更好地處理大數(shù)據(jù)提供了可能。

2 相關(guān)知識(shí)介紹

2.1 Mahout介紹

Apache Mahout是Apache Software Foundation（ASF）旗下的一個(gè)開(kāi)源項(xiàng)目，針對(duì)大規(guī)模數(shù)據(jù)集提供了一些可伸縮的機(jī)器學(xué)習(xí)領(lǐng)域經(jīng)典算法的實(shí)現(xiàn)，Apache Mahout的算法通常運(yùn)行在Apache Hadoop平臺(tái)下，它通過(guò)MapReduce模式實(shí)現(xiàn)。MapReduce計(jì)算框架如圖1所示。

圖1 MapReduce計(jì)算框架

Mahout集成的算法包括聚類、分類、推薦過(guò)濾、頻繁子項(xiàng)挖掘等，也提供了很多處理數(shù)據(jù)、提取特征、訓(xùn)練算法模型的類和方法在具體的項(xiàng)目中，用戶根據(jù)實(shí)際需求在Mahout源代碼基礎(chǔ)上進(jìn)行二次開(kāi)發(fā)以滿足具體的實(shí)際應(yīng)用情況。Mahout腳本通過(guò)調(diào)用Hadoop在分布式平臺(tái)運(yùn)行或調(diào)用jre在本地運(yùn)行，然后調(diào)用Mahout工程的總?cè)肟趏rg.apache.mahout.driver.MahoutDriver類。Mahout啟動(dòng)的總?cè)肟诹鞒倘鐖D2所示。

以k-means聚類算法為例，Mahout利用Hadoop實(shí)現(xiàn)數(shù)據(jù)挖掘算法并行化實(shí)驗(yàn)框架，如圖3所示。

圖2 Mahout啟動(dòng)流程

圖3 k-means的Mahout實(shí)現(xiàn)框架

2.2 相似重復(fù)數(shù)據(jù)清洗概述

數(shù)據(jù)清洗是識(shí)別和消除數(shù)據(jù)噪聲的過(guò)程，數(shù)據(jù)清洗關(guān)注數(shù)據(jù)實(shí)例層面的問(wèn)題，主要集中在幾個(gè)方面：相似重復(fù)記錄消除、缺失數(shù)據(jù)處理、異常數(shù)據(jù)處理、不一致數(shù)據(jù)處理等[1]。

傳統(tǒng)的相似重復(fù)數(shù)據(jù)清洗主要是針對(duì)結(jié)構(gòu)化數(shù)據(jù)，有以下幾種經(jīng)典算法：基于排序合并的近鄰排序算法SNM、多趟近鄰排序算法MPN、R樹(shù)建索引、機(jī)器學(xué)習(xí)等。

隨著處理數(shù)據(jù)的種類逐漸多樣化，針對(duì)web文本的相似重復(fù)記錄檢測(cè)研究很快發(fā)展起來(lái)：文獻(xiàn)[2]提出了一種用于估計(jì)文檔之間相似程度的技術(shù)[2]，這種技術(shù)稱為“帶狀拼寫”，它不依賴于任何語(yǔ)言知識(shí)，而是具有將文檔標(biāo)記成單詞列表的能力，也就是說(shuō)，它僅僅是句法上的。文獻(xiàn)[3]提出了一種對(duì)Web文檔執(zhí)行復(fù)制檢測(cè)的新方法確定相似的Web文檔，以圖形方式捕獲任意兩個(gè)Web文檔中的相似的句子[3]。除了處理范圍廣泛的文檔外，這種復(fù)制檢測(cè)方法還適用于不同主題領(lǐng)域的Web文檔，因?yàn)樗恍枰o態(tài)單詞列表。上述學(xué)者對(duì)特定領(lǐng)域的大數(shù)據(jù)清洗方法進(jìn)行了研究，但仍然缺乏通用的大數(shù)據(jù)清洗方法。

當(dāng)已知淺部地層剖面、地震數(shù)據(jù)及測(cè)井資料時(shí)，可通過(guò)地層剖面大致確定淺層氣的范圍及深度，提取地震屬性來(lái)對(duì)淺水流進(jìn)行識(shí)別，結(jié)合測(cè)井資料進(jìn)行驗(yàn)證及校核。某深水井測(cè)井曲線見(jiàn)圖3。

2.3 k-means聚類算法與canopy聚類算法

k均值聚類算法是由STEINHAUS在1955年、LIOYED在1957年、BALL和HALL在1965年在各自的科學(xué)領(lǐng)域獨(dú)立提出的[4]。k-means是一種最簡(jiǎn)單的無(wú)監(jiān)督學(xué)習(xí)方法，是求解聚類問(wèn)題的一種簡(jiǎn)單迭代方法，可以找到局部最優(yōu)解。在分區(qū)聚類中，k-means算法的主要目標(biāo)是確定每個(gè)聚類的最合適的中心。

k-means聚類算法的主要步驟如圖4所示。

圖4 k-means算法流程

canopy聚類算法是一種粗聚類算法，不能準(zhǔn)確地對(duì)給定數(shù)據(jù)集中的每個(gè)數(shù)據(jù)對(duì)象進(jìn)行分類。該算法使用一種簡(jiǎn)單、快捷的距離計(jì)算方法將數(shù)據(jù)集分為若干可重疊的子集canopy，這種算法不需要指定值，但精度較低。canopy算法流程如圖5所示。

依賴聚類思想實(shí)現(xiàn)相似重復(fù)數(shù)據(jù)清洗，主要是將數(shù)據(jù)集中由于多源異構(gòu)數(shù)據(jù)庫(kù)集成導(dǎo)致的不一致記錄識(shí)別出來(lái)，并清洗掉多余記錄，如華僑大學(xué)與華大，傳統(tǒng)算法認(rèn)為這是兩條不相同的記錄，但是利用k-means聚類，可以將其識(shí)別為標(biāo)識(shí)同一個(gè)地址的相似記錄并聚類到一個(gè)簇中，從而檢測(cè)冗余并刪除重復(fù)的一項(xiàng)，以使存儲(chǔ)空間擁有最大有效利用率。

圖5 canopy算法流程

3 基于mahout的相似重復(fù)記錄清洗算法

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)搭建的Hadoop集群由3個(gè)節(jié)點(diǎn)組成，其中有1個(gè)Master節(jié)點(diǎn)，2個(gè)Slave節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)采用的服務(wù)器配置如下：芯片型號(hào)為Intel （R） Xeon （R） CPU E5-2407@2.20 GHz，內(nèi)核個(gè)數(shù)為4，運(yùn)行內(nèi)存大小為8 GB，硬盤大小為12 TB，操作系統(tǒng)采用CentOS 7.5，Hadoop版本使用Hadoop2.6。

3.2 實(shí)驗(yàn)過(guò)程

本實(shí)驗(yàn)的數(shù)據(jù)來(lái)源是某仿真程序的運(yùn)行日志記錄，一個(gè)日志文件包含14萬(wàn)條記錄，總共10個(gè)日志文件，140萬(wàn)條記錄。

前文已經(jīng)提到，即使k-means算法的復(fù)雜度呈線性，適合大數(shù)據(jù)的處理，但是該算法仍然受到初始值的個(gè)數(shù)與位置的影響，不同的的取值會(huì)得到不同的聚類結(jié)果。而且在大數(shù)據(jù)背景下，很難知道聚類的個(gè)數(shù)。對(duì)于該類問(wèn)題通常有兩種解決辦法，一種是在所給的數(shù)據(jù)集里取樣，隨機(jī)選擇小數(shù)據(jù)量，在小數(shù)據(jù)量范圍內(nèi)預(yù)估類簇?cái)?shù)的值，這種方法簡(jiǎn)單，但是會(huì)受到取樣方法的影響，不能覆蓋全部數(shù)據(jù)類型的取樣數(shù)據(jù)預(yù)估的值會(huì)嚴(yán)重偏離真實(shí)值，從而影響整體聚類效果?；诖?，本文先利用canopy得到個(gè)聚類中心，之后基于Mahout執(zhí)行k-means聚類時(shí)不再人為指定的個(gè)數(shù)，而是直接選用canopy的結(jié)果，這就避免了主觀判斷的失誤，大大提高了聚類精度。實(shí)驗(yàn)流程如圖6所示。詳細(xì)步驟如下。

預(yù)處理過(guò)程將獲取到的日志文件編碼通過(guò)iconv -f gbk -t utf8 20200628.log命令改為L(zhǎng)inux系統(tǒng)可處理的utf-8形式，將每個(gè)文件中的每行日志分割成一個(gè)小文件，暫存至本地。

圖6 實(shí)驗(yàn)流程

使用內(nèi)置的seqdirectory命令，完成文本目錄到SequenceFile的轉(zhuǎn)換過(guò)程。mahout seqdirectory -i 輸入文件路徑 -o 輸出文件路徑 -c utf-8 -chunk 64 -xm sequential，轉(zhuǎn)化后的文件類型變成二進(jìn)制文件。

將序列文件轉(zhuǎn)化為向量文件，mahout seq2sparse -i /user/root/20200705-seq -o /user/root/20200705-sparse -ow --weight tfidf --maxDFPercent 85 –namedVector。

該過(guò)程完成文本分詞、抽取特征、生成字典，利用詞頻逆文檔頻率計(jì)算特征權(quán)重，生成文檔詞矩陣。這個(gè)過(guò)程會(huì)生成7個(gè)文件，分別是df-count、dictionary.file-0、frequency.file-0、tf-vectors、tfidf-vectors、tokenized-document、wordcount。

接下來(lái)，進(jìn)行相似重復(fù)數(shù)據(jù)聚類的實(shí)現(xiàn)：①執(zhí)行canopy算法。mahout canopy -i /user/root/clean3-ck/log-sparse/tfidf- vectors -o /user/root/clean3-ck/canopy-output-0.76-0.38 -dm org.apache.mahout.common.distance.CosineDistanceMeasure -t1 0.76 -t2 0.38 -ow，其中-i為輸入數(shù)據(jù)路徑，-o為輸出數(shù)據(jù)路徑，-dm為算法采用的距離計(jì)算公式，-t1取t2*2，-t2取所有文檔之間的平均距離，-ow為重寫之前的結(jié)果。②執(zhí)行k-means算法。mahout kmeans -i /user/root/clean3-ck/log- sparse/tfidf-vectors -c /user/clean3-ck/canopy-output-0.76-0.38/ clusters-0-final -o /user/coder4/reuters-kmeans-dmorg.apache. mahout.common.distance.CosineDistanceMeasure -x 200 -ow --clustering，其中-i為輸入數(shù)據(jù)路徑，-o為輸出數(shù)據(jù)路徑，-c為聚類中心，-dm為算法采用的距離計(jì)算公式，-x為最大迭代次數(shù)，--clustering為以map-reduce模式運(yùn)行。

執(zhí)行結(jié)束會(huì)生成聚類中心clusterdPoints以及聚類結(jié)果clusters-k-final，文檔被聚到的類簇，如圖7所示。mahout seqdumper -i /user/root/cleans/output/clusteredPoints/。

從圖7可以發(fā)現(xiàn)，100000.txt、100001.txt、100002.txt、100003.txt、100004.txt都被聚類到4419號(hào)類里。原文本內(nèi)容如圖8所示，可以發(fā)現(xiàn)上述聚類結(jié)果正確率為100%。

4 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)分別從查準(zhǔn)率、查全率、1值說(shuō)明本實(shí)驗(yàn)的實(shí)驗(yàn)效果。

假設(shè)（true positive）代表實(shí)際上是重復(fù)的記錄同時(shí)也被預(yù)測(cè)為重復(fù)記錄；（false positive）代表實(shí)際上是非重復(fù)記錄但被預(yù)測(cè)為重復(fù)記錄；（true negative）代表實(shí)際上是非重復(fù)記錄，同時(shí)也被預(yù)測(cè)為非重復(fù)記錄；（false negative）代表實(shí)際上是重復(fù)記錄，但被預(yù)測(cè)為非重復(fù)記錄，+++=測(cè)試數(shù)據(jù)總數(shù)。

圖7 聚類結(jié)果

圖8 4419號(hào)類簇?cái)?shù)據(jù)集

4.1 查準(zhǔn)率

查準(zhǔn)率（Precision）指預(yù)測(cè)為重復(fù)的樣例中有多少是真正的重復(fù)樣例，計(jì)算公式為：

對(duì)隨機(jī)選擇的10 000、20 000、40 000、80 000、100 000、120 000條記錄的實(shí)驗(yàn)結(jié)果進(jìn)行分析，結(jié)果如表1所示。

4.2 查全率

查全率（Recall）指樣本中的重復(fù)記錄有多少被檢測(cè)出來(lái)，計(jì)算公式為：

結(jié)果如表2所示。

表1 查準(zhǔn)率結(jié)果

記錄數(shù)10 00020 00040 00080 000100 000120 000 查準(zhǔn)率74.1%79.32%81.76%81.99%83.1%85%

表2 查全率結(jié)果

記錄數(shù)10 00020 00040 00080 000100 000120 000 查全率89.09%90.7%90.1%90.98%92.01%94%

從上述結(jié)果可以看出，本實(shí)驗(yàn)有較好的查全率，但是查準(zhǔn)率略有不足，這是因?yàn)椴槿屎筒闇?zhǔn)率是一對(duì)矛盾的度量，為了獲取更高的查全率，相似度的閾值會(huì)降低，以便將所有可能相似的記錄都檢測(cè)出來(lái)，只有這樣，才有更大把握得到真正的重復(fù)記錄。同理，若想得到很高的查準(zhǔn)率，那么可能會(huì)漏掉許多相似度不那么高的記錄，從而查全率降低。通常情況下，用1度量尋找兩者之間的平衡，1度量是加權(quán)調(diào)和平均，計(jì)算公式為：

該值在查全率與查準(zhǔn)率上給予了相同的權(quán)重，它在一定程度上表征了算法在查全率與查準(zhǔn)率上同時(shí)取得最優(yōu)值的比例。通過(guò)計(jì)算得知1值，如表3所示。

表3 值

記錄數(shù)10 00020 00040 00080 000100 000120 000 F10.8090.8460.8570.8630.8730.893

以上結(jié)果說(shuō)明該實(shí)驗(yàn)有相對(duì)較好的相似重復(fù)數(shù)據(jù)檢測(cè)效率。

5 結(jié)語(yǔ)

本文闡述了數(shù)據(jù)清洗在數(shù)據(jù)應(yīng)用方面的重要地位，介紹了大數(shù)據(jù)背景下的分布式存儲(chǔ)與分布式計(jì)算框架，詳細(xì)描述了基于mahout的聚類算法檢測(cè)相似重復(fù)數(shù)據(jù)的實(shí)驗(yàn)過(guò)程，該實(shí)驗(yàn)結(jié)果表明，聚類算法可以有效地檢測(cè)相似重復(fù)記錄，

為大量非結(jié)構(gòu)化的文本數(shù)據(jù)清洗提供了解決方案，為后續(xù)數(shù)據(jù)挖掘奠定了重要基礎(chǔ)。

［1］郭志懋，周傲英.數(shù)據(jù)質(zhì)量和數(shù)據(jù)清洗研究綜述［J］.軟件學(xué)報(bào)，2002（11）：2076-2082.

［2］KHADER M，HADI A，AI-NAYMAT G.HDFS file operation fingerprints for forensic investigations［J］. Digital Investigation，2018（5）：50-61.

［3］SVEC P，CHYLO L，F(xiàn)ILIPIK J.Web Log data preprocessing using raspberry pi cluster and hadoop cluster DIVAI 2018［C］//12th International Scientific Conference on Distance Learning in Applied Informatics，2018.

［4］Bigdata-based anomaly detection technology in web services environment［J］.Asia-pacific Journal of Multimedia Services Convergent with Art，Humanities，and Sociology，2018，4（8）：231-250.

2095－6835（2020）20－0015－04

TP311.13

A

10.15913/j.cnki.kjycx.2020.20.005

李碧秋（1996—），女，山西朔州人，華僑大學(xué)碩士研究生，研究方向?yàn)榇髷?shù)據(jù)。王佳斌（1974—），男，副教授，研究生導(dǎo)師，研究方向?yàn)榍度胧较到y(tǒng)、物聯(lián)網(wǎng)、云計(jì)算、大數(shù)據(jù)、軟計(jì)算及其應(yīng)用。

華僑大學(xué)研究生科研創(chuàng)新基金資助項(xiàng)目（編號(hào)：18014084003）

〔編輯：嚴(yán)麗琴〕