基于大数据的数据识别算法在文档搜索中的应用（设计模板）

下面是用 Java代码实现的节点结构

Class vexNode

{

int type;//表示节点类型，包括原始点、收缩点、未收缩无效点及已收缩无效点

Int simNum;//表示节点所处相似实体类的编号

ArrayListadjold//表示节点所邻接的原始节点的集合

ArrayListcontain//表示节点所包含的原始节点的集合

Mapprobability//表示邻接节点边的概率

}

为了验证其准确性，决定采用与其他同类型数据处理的算法进行对比，先让DRBB算法与将本文的识别结果与文献[11]中所提出的5种数据识别算法，同时以准确率（Precision,P）、召回率（Recall,R）及F1（准确率与召回率的折中）作为对比标准。文献［12］中的数据集及识别结果如图6所示：

图6 算法识别结果对比（数据集大小为2616）

又由下图图7所示，在将数据分别用这六个算法进行处理后，将每个算法处理后得到的结果进行对比，可以十分明显的看出DRBB算法得出的结果的精确性高于其他五个算法，可见DRBB算法的识别结果，其平均准确率高于对比的5个算法，召回率较其他两个算法低一点，在F1方面优势更加明显。这些数据都无疑证明了DRBB算法比其他算法更加稳定。

图7　算法精确度对比结果

在检验完算法的准确率后，现在从算法的执行时间方面入手检测在面对海量数据时DRBB算法的执行效率。现按照以下步骤执行该算法：采取两种实验方式，第一种是现将数据用Map-Reduce框架分别Map和Reduce处理52次。让后采用从网上自动提取数据的方式提取出0.98GB的数据，第二种是采用人工手动用数据生成器随机生产出数据量约为1.01G的数据同时每个数据都包含10个属性值。最后给每个属性定义权重值为0.1的权重。结论见表1，从表1中的结果可以看出：在处理数据量较大的情况时，DRBB算法具有执行时间短，算法的效率相当不错。

表1　DRBB算法执行效率

ＤａｔａＳｅｔ

Ｓｉｚｅ/条

空间/ＧＢ

Ｒｕｎｎｉｎｇ　Ｔｉｍｅ/ｓ

ＵＲＬ

18789004

0.98

1762

Ａｒｔｉｆｉｃｉａｌ

6836953

1.01

2833

现在开始测试自定义的参数λ对该算法执行过程中的影响，大致将从以下三个方面入手进行验证：数据集合大小、λ的大小和、Map-Reduce执行时所处理的任务个数。

先测试一下数据集合对算法执行完成的时间的影响。选取人工随机生成的数据进行试验，分别将该数据集合的数据集大小选取出10MB，20MB，50MB，100MB，200MB．测试后的结果如图8。

图8 算法时间和数据集大小关系

由此图可以看出用DRBB算法处理数据时，数据集的量越大，算法执行完的时间越短，相反面对数量集较小的情况时算法执行时间却较长，没有真正发挥出该算法的性能。这样十分直观的表示了该算法在处理大量数据时具备十分优良的执行效率。

DRBB算法在执行过程中会受到参数λ的影响，那么在λ大小不同时对算法执行的结果的准确度所产生的影响是需要检验的，现在获取数据大小为5KB的数据集。实验结束后的结果如图9所示，由此图可以看出：当λ越大时，算法执行后的结果准确度越高，因为λ越大时，洋相满足实体划分的那个标准，必须在划分时将数据属性值的相似度更高的数据划分到一起，而相反相似度较低的则更加不会被归为一类。顾名思义当每个分类中的数据属性相似度提高了，相应的准确度自然就提高了，与此同时召回率降必然随着准确度的提高而降低，另外F1在这次实验中没有随着λ的变化而出现较大波动，表现得十分稳定。

图9 划分参数λ大小对算法精确性的影响

这次将根据算法执行时Map-Reduce所处理的不同任务量来判断算法受其的影响程度，每一个Map-Reduce都是代表它正在处理一个进程，故而Map-Reduce的数量可以表示进程的数量。此次测试从算法执行时Map-Reduce的个数入手，验证算法的执行效率，集同样的选取两个不同大小的数量级：10MB和500MB。

图10　Map-Reduce数量对算法执行过程中的影响

由图10可以看出：Map-reduce的进程数对算法的执行时间影响是分两种情况的，当数据量较少时影响较小，相反当数据量较大时影响较大，数据量比较大时，进程数越大算法执行所需时间越短，效率越高。

根据上面的实验，可以看出，该算法的性能受到数据集合大小、λ的大小和、Map-Reduce执行时所处理的任务个数的影响颇大，但无论何种情况，DRBB算法都被证明了在面对数量集较大的情况时其算法才能充分发挥其性能。

由上述实验可知DRBB在面对海量数据时能够十分准确和高效的对数据进行识别，大大降低了冗余和重复的情况，现如今人们每天都将接收大量的信息，尤其是面对需要查询的问题时，如何从数之不尽的文档中找到自己想要到那一部分，是一个问题。而DRBB算法正好可以应用到文档搜索中来。举个例子：现在有人搜索地球离火星多远（How far is it from Earth to Mars?）,这个时候为了方便起见现在输入“from Earth to Mars”。查询结果会显示许多含有这些关键字的文档，而哪一个是自己想要的却无法直接找到，需要花大量的时间和精力一个一个看。现在利用DRBB算法，在构造的倒排索引表中进行初步聚类，然后通过算法中数据识别那一步中依次进行多轮Map-Reduce、阈值计算、图聚类后，自动在语料库中根据计算后的相似概率筛选出最佳的答案及其上下文显示给客户，通过算法处理后显示给用户的文档数量将大大降低，让用户可以十分迅速的找到所需要的文档数据。

图11　在文档搜索中DRBB搜索框架

当用户输入：“from Earth to Mars”后，经过DRBB算法筛选后的文档会显示这样一句话：“...the distance between Earth and Mars varies from 34 million miles to 249million miles”，其中from 34 million miles to 249million miles便是反馈给用户最准确的答案。

在处理大量数据时，不仅要面对异构数据和大量非结构化数据，数据在表示上也存在多样化，且数据多数来自不同的数据源，故而降低数据质量的主要原因是数据的冗余和数据集成自不同数据的源后的重名。本篇论文提出的大数据处理的数据识别算法DRBB，先抽样，将抽取的对象的属性值构造一个倒排索引表，在查找时大大减少了遍历时的工作量，有效的提高了数据识别结果的准确度。另外还采用了一种新奇的方法计算阈值，给出权值，使得划分数据类时更有效率，同时还将一维数组变换成二维数据集合，然后利用图聚类的方式划分数据相似对，十分有效的提高的算法的精确度。最后在实验验证过程中从自动录入数据和人工随机生成数据两个方面进行测试，多方面验证了DRBB算法的可行性，相信在以后需要处理海量数据进行数据识别时，随着该算法的日益完善，必会得到广泛的运用，发挥其价值所在。

参考文献

[1] 王鹏. 走近云计算[M]. 人民邮电出版社, 2009:75-78.

[2] 田秀霞,周耀君,毕忠勤等.基于Hadoop架构的分布式计算和存储技术及其应用[J]. 上海电力学院学报，2011(01).

[3] 查道贵,许彩芳,陈伟.云计算平台下数据挖掘算法研究[J]. 信阳农林学院学报，2017(01).

[4] 王宏志,樊文飞.复杂数据上的数据识别技术研究[J]. 计算机学报，2011(10).

[5] 江务学,张璟,王志明.MapReduce并行编程架构模型研究[J]. 微电子学与计算机，2011(06).

[6] 许艳茹,王玉珍.基于动态阈值的协同过滤算法研究[J]. 邵阳学院学报(自然科学版)，2017(05).

[7] Cohen w w, Richman J. 对学习和匹配集群高纬度数据集的数据集成的知识发现和数据挖掘.New York:ACM, 2002:475-480.

[8] 温程. 并行聚类算法在MapReduce上的实现[D]. 浙江大学，2016.

[9] 曹恒瑞,曹展硕.一种基于Hadoop平台的分布式数据检索系统[J]. 软件导刊，2017(4).

[10] Arasu A, ReC, Suciu D. Laege-scale deduplication withconstraints using dedupalog //Proc of the 25th IEEE Int Confon Data Engineering(ICDE:09). Piscataway, NJ:IEEE.

[11] 肖雪平,倪建成,曹博.基于Map-Reduce模型的BCkmeans并行聚类算法[J]. 电子技术, 2016(05).

[12] K pcke H, Thor A. Evaluation of entity resolution approaches on real-world match problems.Proceeding of the VLDB Endowment. 2014, 3(1/2):484-493.

致谢

本次毕业论文设计离不开董国钢老师的指导和帮助，他在忙碌的教学工作中抽出时间来审查、修改我的论文，对于我顺利完成这次毕业设计起到了关键性的作用，在此谨向董国钢老师致以诚挚的谢意和崇高的敬意，还有所有教过我的老师，他们严谨细致，他们循循善诱的教导和一丝不苟的思路给予我无限的启迪。

我还要感谢我的母校武汉生物工程学院，以及在大学四年的学习和生活中给予我关心和帮助的朋友、老师和同学们，感谢他们为我提出的建议和意见，正是因为他们的支持、鼓励和帮助，我才能充实的过完了四年的大学生活，他们让我成长了许多，教会了我专业的知识和做人的道理，让我更加成熟。

课程设计报告

（项目设计说明书）

课程：

题目：

学院：

专业班级：

设计小组：

成员名单：

（不超过8人）

指导教师：

时间：

设计小组及成员分工介绍

设计小组简介：

各成员基本情况及分工一览表：

学号

姓名

专业特长

在项目中的作用（或角色）

自评分/组长评分

摘　要 II

关键词 II

Abstract III

Key words III

1 系统需求分析 1

（可根据需要展开为二级乃至三级标题，格式如下，后同，此行在正式课程设计报告中不要）

1.1 1

1.2 1

1.2.1 2

1.2.2 3

2 系统功能分析与模块构成 *

展开的二级乃至三级标题，以实际的标题代替

3 系统文件组成 *

展开的二级乃至三级标题，以实际的标题代替

4 数据库分析与设计 *

展开的二级乃至三级标题，以实际的标题代替

5 主要功能模块的设计与实现

5.1 模块一 *

5.1.1 （前端）界面设计与实现 *

5.1.2 （后台）程序设计与实现 *

5.1.3 联调测试 *

5.1 模块二 *

5.2.1 （前端）界面设计与实现 *

5.2.2 （后台）程序设计与实现 *

5.2.3 联调测试 *

6 系统部署及使用注意事项

6.1 系统部署（上线发布） *

6.2 系统使用注意事项 *

7 结论*

参考文献 21

正文文字与段落格式示例（论文内容与此次设计无关，请忽略）：

基于大数据的数据识别算法在文档搜索中的应用

数据识别是筛选数据，对数据进行实时监测与鉴别的一项关键技术，能有效提高数据及反馈信息的质量，其目的在于识别出数据在表示时的多样性，以及对象映射数据的重复性。随着大数据应用的越发广泛，基于大数据的数据识别便应运而生。因此，在现阶段互联网发展的基础上，笔者给出了一个基于大数据的数据识别算法,该算法先是利用物体在数据库中的属性值进行比较和筛选，然后利用聚类算法进行数据归类和匹配，输出结果后在Hadoop平台上对真实数据集和人造数据集进行了比较，利用实验结果验证算法的可行性与有效性。最后，将该算法应用到文档搜索中，当需要搜索某个信息时，只需搜索某个关键词，利用该算法的特性自动匹配。

大数据；数据识别算法；文档搜索；应用

The Application of Data Recognition Algorithm Based on Big Data in Document Search

Data recognition is a key technique for screening data、real-time monitoring and identification data which can effectively improve the quality of data and feedback information,Its purpose is to identify the diversity of data in representation and the repeatability of object mapping data.with big data applications more widely, the data recognition based on big data then arises at the historic moment. Therefore, based on the current development of the Internet, a data recognition algorithm based on big data (map-reduce) is presented. The algorithm first compares and filters the attribute values of the objects in the database, and then uses the clustering algorithm to classify and match the data. After the output results were compared between the real data set and the artificial data set on the Hadoop platform, the feasibility and effectiveness of the algorithm were verified by experimental results.Finally, the algorithm is applied to document search. When you need to search for information, you only need to search for a keyword and use the characteristics of the algorithm to automatically match.

Data identification；Big data；hadoop；Map-Reduce

图1 初步聚类算法流程图

3.2.1 数据样本采集阶段

由于所面对的往往是海量数据，这些数据不仅大多是非结构化数据而且来自于不同的数据源，故而要想取得阈值必须先在数据库中抽出一部分数据作为样本获取阈值。获取样本可以定义这样一个方法：从一个十分庞大的元素集合中抽取一部分元素作为样本，假设集合中有N个元素，而抽取数量为k，现在规定k个元素中存在多对属性值十分接近的数据，设个数为m。由于所要处理的数据不断的实时更新且数量十分庞大，在进行抽样时无发做到一次性让数据进入内存中，但前面说到要保证抽取的元素中又要出现m个属性值相似的数据，因此必须采取一种可以做到实时抽样并自动识别数据有效性的抽样算法：将其取名为DESampling抽样算法，DESampling算法的原理是先构造一个可供抽样的抽样采样池SamplingPool，这样一来数据进入抽样采样池中，并且不断实时更新，这样一来可以在其中按照要求抽取样本。

图2 抽样算法流程图

① sim Pair=0;

② for each entity Ei∈E do for　each entity Ei∈E do

③ for each entity S,in SamplingPool do

④ if similarity(Ei,Sj)==true then

⑤ SamplingPool[Sj].setID.insert(Ei);

⑥ simPair +=SaPair+=SamplingPool[Sj].size;

⑦ for each entity Ck,inSamlingPool do

⑧ SamplingPool[Ck].jmp--;

⑨ end for;

⑩ go to②;

end if

end for

If SamplingPool.size==MAXSIZE then

D=min(SamplingPool.jmp);

SamplingPool.remove(D);

end if

for each entity Ft in SamplingPool do

SamplingPool[Ft].jmp--;

End for

SamplingPool.insert(Ei,null,MAXJMP);

if simPair

goto②;

Else

Break;

Endif

Endfor

Output SamplingPool;

由上述算法可以看出，第一步是构造了一个抽样采样池SamplingPool,进入池中的元素都会为其配备两个标记，其中一个用于表示它所归属的集合，另一个用了表示它在集合中出现的次数setID。最后一步在池中声明一个全局变量simpair记录池中相似度较高的数据对jmp，设其值为0．完成这些工作后，先将池中的元素进行遍历，找到两个属性值相似的数据，然后将它们纳入到一个数据集合中，然后更新池中的记录，然后把所有在池中的元素的jmp自减1,继续按照算法执行步骤往下执行。相反，若是没有找到属性值相似的数据对，则更新一遍数据采样池中的数据，另外若是采样池数据存储量达到了上限，则采用清除活跃度低的元素，然后重新收入新的数据，将那些相似个数少的元素清理掉，同时将池中原有所有元素的jmp自减减一，最后若是达成要求，则执行完所有步骤，不然回到算法第二步继续执行，最后输出结果。同时，该算法的时间复杂度为O(n),空间复杂度为O(m n)。

3.2.2 数据阈值比较聚类阶段

要想判断抽取出的样本属性值是否相似，可以比较其阈值，而要想得出样本数据的阈值，本文给出了一种计算阈值的方法：将数据的相似度划分为强相似（HL）和弱相似(LL)，然后求出两个类的界限区域的重复程度，可以用象限上的两个圆来表示两个类，圆的面积代表类中的数据集合，然后求出可以覆盖两个圆的的最小区域，这个区域就是其阈值THES。

定义1．覆盖区域。设象限中有一集合V，若有一个圆可以将这个集合所代表的圆覆盖住，同时有且只有一个这样的圆的半径最小，则若圆C为覆盖V中所有点的半径最小的圆，则称圆C为点集V的最小覆盖区。

图3 阈值计算流程图

由此可知，现在设计一个算法TMC：

算法2．TMC

输入：HL和LL；输出：THES

① for each value t in HL do

② P.x=t+rand();

③ P.y=t+rand();

④ H.insert(P);

⑤ Endfor

⑥ For each value s in LL do

⑦ Q.x=s+rand();

⑧ Q.y=s+rand();

⑨ L.insert(Q);

⑩ Endfor

=computer_mcc(H);

=computer_mcc(L);

If |PH-PL|>rH+rL then

R.x=PH.x+PL.y;

R.y=PH.y+PL.y;

THRES=(R.x+R.y)/2

Else

R=computer_inj(PH,RH,PL,rL);

THRES=(R.x+R.y)/2;

Endif

Return THRES;

Endif

Return THRES;

在算法前5步中，为的是将一维的的两个代表属性值现实程度的点设为二维的点，同时给出在此基础上预设的离散点，然后将他们两个分别归到HL和LL，在后面的步骤中提高Compute_mcc函数求出THRES，然后根据两个圆的位置分别求出最终的阈值：相交：THRES=相交弦与两个圆连线相交的点的坐标（x,y），然后x和y相加的和除以2，相离：两个圆的圆心的连线的中点坐标（x,y），若相切则取切点的坐标（x,y）,同样的求出x与y的和的二分之一。弃值便为所需的阈值。另外该算法的时间复杂度为O(n)。

图4 数据识别流程图

过程2．EntityCount

输入：倒排索引表SE；输出：数据出现的频率和相似对的频率。

① map部分

输入：>

处理：将SE中的的数据和数据对作为key,value=1,进行映射。

输出：,…,….

②Reduce部分

输入：,value=1>

处理：把输出的key进行聚合操作，然后记录数据出现的频率和相似对的频率。

输出：,…,

….

完成第一步过程后，还需要在进行两次重复上述的步骤，把输出的结果进行聚集。

过程3．EntityGather1

输入：EntityCount中最终输出的数据及其相似对的频次。

输出：首个数据及其数据对出现频次。

① map部分

输入：,value=Ti/Tij>

处理：将Ei作为key，value=<,Tij>，然后映射，此外单个的数据和频次直接输出。

输出：,…,

,Tij>>….

② Reduce部分

输入：,Tij>>/Tj>

处理：按key归类，把聚合后的结果依次输出，将数据结果中首个数据为Ei的数据作为输出标准。

处理：将聚集结果拆分后输出。

输出：,…,

,Tij>>>….

过程4．EntityGather2

输入：集合中首个数据及其数据对对出现频次。

输出：集合中出现的第二个数据及其数据对的频次。

① Map部分

输入：,Tij>>>；

处理：key=数据组中的第2个数据，value=Ei的频次和数据组Ei+Ej的频次，进行映射，单个的直接输出。

输出：,…,

,<,Tij>>….

②Reduce部分

输入：,Tij>>

处理：根据key来聚合，把所有输入的数据对判断其第二个数据是否为Ej,若是则输出其结果和频次，然后将其结果分步输出：

,,value=<,Tij>>…．

经过上述处理后，在此基础上进行三次同样的操作，得出准确的结果，此结果就是该对象属性下的数据组出现的频次。例如某个属性Am包含数据组的相似度Sm定义为：

式（1-1）

另外计算该属性的总体平均相似程度similarity(Ei,Ej)时，需要将每个数据的属性的值求出其加权平均，定义为：

式（1-2）

通过这些计算，得出的结果再进行一次Map-Reduce就可以得到最终的结果。该结果就是所需的整体相似度。

过程5．ComputeSimilarity

输入：THRES,权值和数据组

,>,value=<,Tij>>;

输出：属性值相似的数据组和其程度。

① map部分

输入：;

处理：key=Ei+Ej,value=Sm,映射。

输出：,value=Sm>,…,

,value=Sn>….

②Reduce部分

输入：,value=Sm>,…,

处理：按照key下的求出整体相似程度，然后输出其结果大于之前计算得出的阈值的结果。

输出：,value=similarity(Ei,Ej)>…。

在完成上述的处理之后，通过构造一个利用初步聚类创建的对象各个属性倒排索引表，然后在此基础上提供了一个EntitySim框架。以保证接下来工作的正常开展。

输入：SE，属性权重和阈值。

输出：数据相似对集合文件。

① for each Attribute Ai in A do

② set Wi;

③ EntityCount(Ai);

④ EntityGather 1(Ai);

⑤ EntityGather 2(Ai);

⑥ endfor

⑦ ComputeSimilarity();

在①～⑥中，每个数据的不同属性设置一个权重，然后在匹配时不用在对数据直接进行操作，然后再进行三次 Map-Reduce记录下结果中的数据组的频次，最终在此基础上在此进行一次Map-Reduce得出结果。

通过3.2阶段的操作后，可以看出将结果用集合的形式表示，故而更近一步可以将结果的集合表示成图聚类形式。为此给出了一个算法：GraphDivision，并且给出了比较详细的描述，在该算法中让N(V)为顶点V的相邻结点的集合,同时V∈N(V)。

图5 图聚类划分算法流程图

算法4：GraphDivision

输入：聚类图G=(V,E)，人为自定义参数λ

输出：划分后的结果D={G1，G2，....GN}

Gi={Ej|Ej为一个聚类中的元素}

① for each E=(a,b) do

② if |N(a)∩N(b)|≧λ|N(a)∪N(b)| then

③ merge(a,b);

④ update=true;

⑤ endif

⑥ if update=true then

⑦ goto②;

⑧ endif

⑨ endfor

⑩output G;

上述步骤中，通过反复执行图聚类的划分方式对划分的某个类图进行测试其准确性，通过上述的算法可以看出假设某条边(a,b),代入到|N(a)∩N(b)|≥λ|N(a)∪N(b)|中．若是符合这个标准，就将此边用一个顶点a’表示，设a’＝{a,b}{a,b}．然后对其他每条边都执行此次操作知道不符合这个条件为止，将结束后通过条件的点作为划分结果，一个点代表一个类。另外算法的时间复杂度为O(d×|E|)。

接下来，用采取了一个计算概率的方式，通过此方式可以计算出每个数据大概所所属的类别。在2.3中通过图聚类的方式知道了通过点与点可以得出数据在某个类中的可能性。设分类=Gi，图聚类的整体平均相似度=Pi，现有某一点A，SA-X为A的Pi，那么Ａ属于此数据分类的的概率为:

式（1-3）

然后提供一个概率计算的算法ComputePro。

算法5:ComputePro

输入：划分到同一类的数据组集合G={G1，G2，....GN};

输出：G的概率。

① for each Gi in G do

② Pi=Compute Average degree(Gi);

③ for rach A in Gi do

④ SA-x=Compute Average degree(A);

⑤ PA=SA-X/Pi

⑥ end for

⑦ endfor

算法5先计算出Gi的整体相似度均值，然后算出了点A和它相连接的边的相似度均值，最终得出了其概率。

在概率计算过程中对于顶点数量为n、边数量为m的划分，计算其中所有顶点概率的最坏时间复杂度为O(m2+mn)。

在上述的步骤中完成了数据识别的DRBB算法，现在需要对该算法的可行性进行测试。于是用Java写出该算法的具体步骤，然后在ubuntu12.04.1操作系统上的Hadoop运行。由于该算法的可行性还是未知状态，为了保险起见采用多种方式进行对比和测试，先是从网络上提取已有的海量数据进行测试，得出