面向大数据实体识别的超图分割算法

Hypergraph Partitioning for Entity Identification in Big Data

当前信息系统中存在海量复杂异构数据,极大地降低了数据可用性.为有效地"清洗"数据、提高数据实体同一性,借助云计算平台Hadoop设计并实现了基于超图模型的实体识别算法.算法共分为数据预处理、构造超图模型和实体识别三个阶段:在预处理阶段,通过建立属性-值倒排索引表、挖掘频繁项集来对数据进行初步处理;在构造超图模型阶段,改进超边权重的定义,建立超边带权重的超图模型,将所有数据转化为超图模式;在实体识别阶段,改进超图分割算法并基于云平台来完成对同一实体的识别.在Hadoop平台上对真实数据集的实验结果表明该算法在实体识别方面具有良好的准确性和高效性.

In view of the current information system,there is a huge amount of complex data which seriously reduces the data availability.To ＂ clean＂ data efficiently and improve the quality of data,based on hypergraph model,this paper proposes an entity identification algorithm utilizing Hadoop cluster. The algorithm is divided into three stages： data preprocessing,constructing hypergraph model and entity identification. In the data preprocessing stage,it processes the data via creating property-value inverted index tables and mining the frequent itemsets; Then it establishes a weighted hypergraph model and transforms all data into the hypergraph in the stage of constructing hypergraph model; Moreover,in the stage of entity identification,it completes the entity identification using an improved hypergraph partitioning algorithm. The experiments on real data sets based on Hadoop cluster indicate that the algorithm is efficient,with great accuracy.