分布式数据流聚类算法及其基于Storm的实现

为了提高数据流聚类算法的效率,设计并提出了基于质心距离和密度网格的数据流聚类算法—CDD-Stream,并通过对其中网格结构的更新实施了并行化策略,进而设计并提出了一种分布式数据流聚类算法—DCD-Stream(Distributed Centroid Distance D-Stream)。该算法分为在线和离线两个部分,在线部分实时接收数据流,利用局部节点和全局节点实现了网格结构更新的并行化,完成了整体网格结构的增量更新;离线部分基于网格结构的更新结果进行全局聚类,并存储网格帧,供用户查询历史簇。充分利用Storm快速实时处理数据流并显著提高数据流挖掘算法性能的优势,设计并实现了基于Storm的DCD-Stream算法实现方案。该方案通过内存数据库Redis和消息中间件Kafka的应用对DCD-Stream算法的拓扑进行了合理部署与实现。对比验证实验结果表明,相对于其他算法,DCD-Stream算法在数据流对象上有相当高的聚类精度和更好的时效性,基于Storm的DCD-Stream算法实现方案是可行且有效的。

基于质心距离和密度网格的数据流聚类算法

针对基于密度网格的数据流聚类算法D-Stream存在的缺陷,提出了基于质心距离和密度网格的数据流聚类算法CDD-Stream。该算法分为在线、离线以及历史簇查询3个部分。在线部分通过各网格单元的数据量、密度以及存在的网格数来计算加权平均密度,基于加权平均密度动态设置网格单元的密度阈值和时间间隔gap;采用新的簇边界判定方法,依据稀疏网格与其邻接稠密网格的质心距离,将稀疏网格归并到相应的簇中,在一定程度上避免了簇边界的误删,提高了聚类精度。离线部分使用金字塔时间模型存储网格帧,供用户查询历史簇,查询结果可以为用户进行簇演化分析提供依据。与D-Stream算法和NDD-Stream算法的对比实验结果表明,CDD-Stream算法在数据流对象上有更好的聚类时效性和更高的聚类精度。

基于结构与属性的社区划分方法

目前通行的社区划分方法大多基于结构,但单纯基于结构的划分不能挖掘出社区对象的潜在关系,因而不能发现社区的变化趋势。为此,提出了基于结构的社区划分算法(Community Division based on Structure,CDS)。该算法利用度和节点欧氏距离对社会网络进行结构划分;同时针对经典K-means算法在社区划分中所存在的随机选取初始中心点以及k值选取不合理所导致的聚类结果不佳问题,提出了一种基于社区结构的非人为设定k值的K-means算法—NPCluster(Non Presetting Cluster)算法。该算法基于由CDS算法所提到的社区结构,依次选取度最大的节点作为聚类中心点,以小于平均特征欧氏距离为基准合并簇集,反复迭代直至聚类完成。理论分析和对比实验结果表明,CDS算法能够有效划分出社区结构;相对于K-means算法,NPCluster算法在已划分的社区结构上具有更高的聚类精度和更好的时效性;结构与属性相结合的社区划分方法是有效可行的。

分布式数据流挖掘技术综述

网络信息技术的高速发展产生了新的数据模型,即数据流模型,并且越来越多的领域出现了对数据流实时处理的需求,庞大且高速的数据以及应用场景的实时性需求均推进了数据流挖掘技术的发展。首先介绍了常见的数据流模型;然后根据数据流模型的特点总结数据流挖掘的支撑技术;最后,分析了分布式数据流挖掘的重要性和有效性,给出了算法并行化的数学模型,并介绍了几种具有代表性的分布式数据流处理系统。