一种基于数据垂直划分的分布式密度聚类算法  

An Efficient Density-Based Clustering Algorithm for Vertically Partitioned Distributed Datasets

作　　者：倪巍伟[1] 陈耿[2] 孙志挥[1] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]南京审计学院审计信息工程实验室,南京210029

出　　处：《计算机研究与发展》2007年第9期1612-1617,共6页Journal of Computer Research and Development

基　　金：江苏省自然科学基金项目(BK2006095);教育部高等学校博士学科点专项科研基金项目(20040286009)

摘　　要：聚类分析是数据挖掘领域的一项重要研究课题,对大数据集的聚类更以其数据量大、噪声数据多等而成为一个难点.针对数据垂直划分的情况,提出连通点集及局部噪声点集等概念.在分析局部噪声点集与全局噪声点集以及局部连通点集与全局连通点集关系的基础上,对全局噪声点进行有效过滤,进一步设计闭三角链表结构存储各个结点的聚类中间结果,提出了基于密度的分布式聚类算法DDB-SCAN.理论分析和实验结果表明,算法可以有效解决垂直划分的大数据集聚类问题,算法是有效可行的.Clustering is an important research in data mining. Clustering massive datasets has especially been a challenge for its large scale and too much noise data points. Distributed clustering is an effective method to solve these problems. Most of existing distributed clustering research aims at circumstances of horizontally partitioned dataset. In this paper, considering vertically partitioned distributed datasets, based on the analysis of relations between local noise datasets and the corresponding global one, an efficient filtering is applied to the global noise, which can efficiently eliminate the negative affection of noise data and reduce the scale of dataset to be dealt on the center node. Furthermore, an effect storage structure CTL （closed triangle list） is designed to store the intermediate clustering results of each node, which can efficiently reduce communication costs among distributed computer nodes during the clustering process and is helpful to conveniently generate global clustering model with high space utilization ratio and complete clustering information. Thus, a distributed density-based clustering algorithm DDBSCAN is proposed. Theoretical analysis and experimental results testify that DDBSCAN can effectively solve the problem of clustering massive vertically partitioned datasets, and the algorithm is effective and efficient.

关 键 词：分布式数据挖掘 数据垂直划分 连通点集 局部噪声点集 闭三角链表 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]