基于Mahout的相似重复数据清洗策略研究＊

李碧秋，王佳斌

基于Mahout的相似重复数据清洗策略研究＊

李碧秋，王佳斌

（华侨大学 工学院，福建 泉州 362021）

针对在海量日志记录中无法有效抽取高价值的数据问题，提出一种基于Mahout的k-means短文本聚类清洗算法，利用开源机器学习算法库Mahout，将文本聚类与数据清洗相结合，通过聚类检测相似重复记录，有效提升重复数据清洗速率。实验结果表明，该方法在保证较高查全率与查准率的同时，比传统相似重复数据清洗算法更具有扩展性，这对大数据的处理有较强的实用意义。

数据清洗；k-means；相似重复记录；文本聚类

1 引言

在信息爆炸的大数据时代，大数据系统已被许多领域广泛采用，提供有效的数据解决方案。大数据系统产生大量的非结构化日志，其中隐藏了许多有价值的信息。但是仅注意数据分析而不重视数据质量问题可能会使研究或分析变得毫无意义，甚至导致灾难性的后果。因此，对于大数据分析和挖掘，数据质量起着关键作用，数据清理是保证数据质量的强大工具。目前，对大数据的数据清理包括保证数据一致性和完整性、实体标识、数据预处理等，其中针对冗余数据的检测与删除具有显著的优势，可以减少冗余数据的存储与不必要的网络带宽，提高系统的可伸缩性。传统的重复数据清洗主要是针对结构化数据在本地处理，这种方法已经不能满足海量待处理数据的需求，而Hadoop作为一种著名的开源大数据编程框架，为人们提供了分布式存储和分布式计算技术，已经被应用于谷歌、Facebook、腾讯、阿里巴巴等大型互联网公司。其生态圈的组件之一Mahout集成了多种聚类、分类等算法，为人们更好地处理大数据提供了可能。

2 相关知识介绍

2.1 Mahout介绍

Apache Mahout是Apache Software Foundation（ASF）旗下的一个开源项目，针对大规模数据集提供了一些可伸缩的机器学习领域经典算法的实现，Apache Mahout的算法通常运行在Apache Hadoop平台下，它通过MapReduce模式实现。MapReduce计算框架如图1所示。

图1 MapReduce计算框架

Mahout集成的算法包括聚类、分类、推荐过滤、频繁子项挖掘等，也提供了很多处理数据、提取特征、训练算法模型的类和方法在具体的项目中，用户根据实际需求在Mahout源代码基础上进行二次开发以满足具体的实际应用情况。Mahout脚本通过调用Hadoop在分布式平台运行或调用jre在本地运行，然后调用Mahout工程的总入口org.apache.mahout.driver.MahoutDriver类。Mahout启动的总入口流程如图2所示。

以k-means聚类算法为例，Mahout利用Hadoop实现数据挖掘算法并行化实验框架，如图3所示。

图2 Mahout启动流程

图3 k-means的Mahout实现框架

2.2 相似重复数据清洗概述

数据清洗是识别和消除数据噪声的过程，数据清洗关注数据实例层面的问题，主要集中在几个方面：相似重复记录消除、缺失数据处理、异常数据处理、不一致数据处理等[1]。

传统的相似重复数据清洗主要是针对结构化数据，有以下几种经典算法：基于排序合并的近邻排序算法SNM、多趟近邻排序算法MPN、R树建索引、机器学习等。

随着处理数据的种类逐渐多样化，针对web文本的相似重复记录检测研究很快发展起来：文献[2]提出了一种用于估计文档之间相似程度的技术[2]，这种技术称为“带状拼写”，它不依赖于任何语言知识，而是具有将文档标记成单词列表的能力，也就是说，它仅仅是句法上的。文献[3]提出了一种对Web文档执行复制检测的新方法确定相似的Web文档，以图形方式捕获任意两个Web文档中的相似的句子[3]。除了处理范围广泛的文档外，这种复制检测方法还适用于不同主题领域的Web文档，因为它不需要静态单词列表。上述学者对特定领域的大数据清洗方法进行了研究，但仍然缺乏通用的大数据清洗方法。

当已知浅部地层剖面、地震数据及测井资料时，可通过地层剖面大致确定浅层气的范围及深度，提取地震属性来对浅水流进行识别，结合测井资料进行验证及校核。某深水井测井曲线见图3。

2.3 k-means聚类算法与canopy聚类算法

k均值聚类算法是由STEINHAUS在1955年、LIOYED在1957年、BALL和HALL在1965年在各自的科学领域独立提出的[4]。k-means是一种最简单的无监督学习方法，是求解聚类问题的一种简单迭代方法，可以找到局部最优解。在分区聚类中，k-means算法的主要目标是确定每个聚类的最合适的中心。

k-means聚类算法的主要步骤如图4所示。

图4 k-means算法流程

canopy聚类算法是一种粗聚类算法，不能准确地对给定数据集中的每个数据对象进行分类。该算法使用一种简单、快捷的距离计算方法将数据集分为若干可重叠的子集canopy，这种算法不需要指定值，但精度较低。canopy算法流程如图5所示。

依赖聚类思想实现相似重复数据清洗，主要是将数据集中由于多源异构数据库集成导致的不一致记录识别出来，并清洗掉多余记录，如华侨大学与华大，传统算法认为这是两条不相同的记录，但是利用k-means聚类，可以将其识别为标识同一个地址的相似记录并聚类到一个簇中，从而检测冗余并删除重复的一项，以使存储空间拥有最大有效利用率。

图5 canopy算法流程

3 基于mahout的相似重复记录清洗算法

3.1 实验环境

本实验搭建的Hadoop集群由3个节点组成，其中有1个Master节点，2个Slave节点，每个节点采用的服务器配置如下：芯片型号为Intel （R） Xeon （R） CPU E5-2407@2.20 GHz，内核个数为4，运行内存大小为8 GB，硬盘大小为12 TB，操作系统采用CentOS 7.5，Hadoop版本使用Hadoop2.6。

3.2 实验过程

本实验的数据来源是某仿真程序的运行日志记录，一个日志文件包含14万条记录，总共10个日志文件，140万条记录。

前文已经提到，即使k-means算法的复杂度呈线性，适合大数据的处理，但是该算法仍然受到初始值的个数与位置的影响，不同的的取值会得到不同的聚类结果。而且在大数据背景下，很难知道聚类的个数。对于该类问题通常有两种解决办法，一种是在所给的数据集里取样，随机选择小数据量，在小数据量范围内预估类簇数的值，这种方法简单，但是会受到取样方法的影响，不能覆盖全部数据类型的取样数据预估的值会严重偏离真实值，从而影响整体聚类效果。基于此，本文先利用canopy得到个聚类中心，之后基于Mahout执行k-means聚类时不再人为指定的个数，而是直接选用canopy的结果，这就避免了主观判断的失误，大大提高了聚类精度。实验流程如图6所示。详细步骤如下。

预处理过程将获取到的日志文件编码通过iconv -f gbk -t utf8 20200628.log命令改为Linux系统可处理的utf-8形式，将每个文件中的每行日志分割成一个小文件，暂存至本地。

图6 实验流程

使用内置的seqdirectory命令，完成文本目录到SequenceFile的转换过程。mahout seqdirectory -i 输入文件路径 -o 输出文件路径 -c utf-8 -chunk 64 -xm sequential，转化后的文件类型变成二进制文件。

将序列文件转化为向量文件，mahout seq2sparse -i /user/root/20200705-seq -o /user/root/20200705-sparse -ow --weight tfidf --maxDFPercent 85 –namedVector。

该过程完成文本分词、抽取特征、生成字典，利用词频逆文档频率计算特征权重，生成文档词矩阵。这个过程会生成7个文件，分别是df-count、dictionary.file-0、frequency.file-0、tf-vectors、tfidf-vectors、tokenized-document、wordcount。

接下来，进行相似重复数据聚类的实现：①执行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为输入数据路径，-o为输出数据路径，-dm为算法采用的距离计算公式，-t1取t2*2，-t2取所有文档之间的平均距离，-ow为重写之前的结果。②执行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为输入数据路径，-o为输出数据路径，-c为聚类中心，-dm为算法采用的距离计算公式，-x为最大迭代次数，--clustering为以map-reduce模式运行。

执行结束会生成聚类中心clusterdPoints以及聚类结果clusters-k-final，文档被聚到的类簇，如图7所示。mahout seqdumper -i /user/root/cleans/output/clusteredPoints/。

从图7可以发现，100000.txt、100001.txt、100002.txt、100003.txt、100004.txt都被聚类到4419号类里。原文本内容如图8所示，可以发现上述聚类结果正确率为100%。

4 实验结果与分析

本实验分别从查准率、查全率、1值说明本实验的实验效果。

假设（true positive）代表实际上是重复的记录同时也被预测为重复记录；（false positive）代表实际上是非重复记录但被预测为重复记录；（true negative）代表实际上是非重复记录，同时也被预测为非重复记录；（false negative）代表实际上是重复记录，但被预测为非重复记录，+++=测试数据总数。

图7 聚类结果

图8 4419号类簇数据集

4.1 查准率

查准率（Precision）指预测为重复的样例中有多少是真正的重复样例，计算公式为：

对随机选择的10 000、20 000、40 000、80 000、100 000、120 000条记录的实验结果进行分析，结果如表1所示。

4.2 查全率

查全率（Recall）指样本中的重复记录有多少被检测出来，计算公式为：

结果如表2所示。

表1 查准率结果

记录数10 00020 00040 00080 000100 000120 000 查准率74.1%79.32%81.76%81.99%83.1%85%

表2 查全率结果

记录数10 00020 00040 00080 000100 000120 000 查全率89.09%90.7%90.1%90.98%92.01%94%

从上述结果可以看出，本实验有较好的查全率，但是查准率略有不足，这是因为查全率和查准率是一对矛盾的度量，为了获取更高的查全率，相似度的阈值会降低，以便将所有可能相似的记录都检测出来，只有这样，才有更大把握得到真正的重复记录。同理，若想得到很高的查准率，那么可能会漏掉许多相似度不那么高的记录，从而查全率降低。通常情况下，用1度量寻找两者之间的平衡，1度量是加权调和平均，计算公式为：

该值在查全率与查准率上给予了相同的权重，它在一定程度上表征了算法在查全率与查准率上同时取得最优值的比例。通过计算得知1值，如表3所示。

表3 值

记录数10 00020 00040 00080 000100 000120 000 F10.8090.8460.8570.8630.8730.893

以上结果说明该实验有相对较好的相似重复数据检测效率。

5 结语

本文阐述了数据清洗在数据应用方面的重要地位，介绍了大数据背景下的分布式存储与分布式计算框架，详细描述了基于mahout的聚类算法检测相似重复数据的实验过程，该实验结果表明，聚类算法可以有效地检测相似重复记录，

为大量非结构化的文本数据清洗提供了解决方案，为后续数据挖掘奠定了重要基础。

［1］郭志懋，周傲英.数据质量和数据清洗研究综述［J］.软件学报，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，FILIPIK 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—），女，山西朔州人，华侨大学硕士研究生，研究方向为大数据。王佳斌（1974—），男，副教授，研究生导师，研究方向为嵌入式系统、物联网、云计算、大数据、软计算及其应用。

华侨大学研究生科研创新基金资助项目（编号：18014084003）

〔编辑：严丽琴〕