基于MapReduce的分布式近邻传播聚类算法

随着信息技术迅速发展,数据规模急剧增长,大规模数据处理非常具有挑战性.许多并行算法已被提出,如基于MapReduce的分布式K平均聚类算法、分布式谱聚类算法等.近邻传播(affinity propagation,AP)聚类能克服K平均聚类算法的局限性,但是处理海量数据性能不高.为有效实现海量数据聚类,提出基于MapReduce的分布式近邻传播聚类算法——DisAP.该算法先将数据点随机划分为规模相近的子集,并行地用AP聚类算法稀疏化各子集,然后融合各子集稀疏化后的数据再次进行AP聚类,由此产生的聚类代表作为所有数据点的聚类中心.在人工合成数据、人脸图像数据、IRIS数据以及大规模数据集上的实验表明:DisAP算法对数据规模有很好的适应性,在保持AP聚类效果的同时可有效缩减聚类时间.     

多层自动确定类别的谱聚类算法

自动确定聚类数和海量数据的处理是谱聚类的关键问题。在自动确定聚类数谱聚类算法的基础上,提出了一种能处理大规模数据集的多层算法。该算法的核心思想是把大规模数据集根据一定的相关性逐级进行合并,使之成为小数据集,再对分组后的小数据集用自动确定类别的谱聚类算法聚类,最后逐层进行拆分并微调, 完成全部数据的聚类。实验证明该算法的聚类效果很好。     

社团挖掘的并行化AP聚类方法

采用AP聚类算法进行复杂网络社团挖掘,提高了社团挖掘的精度,但在处理海量数据时算法速率明显下降,其中一个重要原因是单台计算机的计算性能无法满足海量数据的计算需求。为了提高社团挖掘AP聚类在处理海量数据时的速率,设计出一种在Hadoop框架下进行的社团挖掘的并行化AP聚类方法;将传统单机模式下的社团挖掘AP聚类算法在分布式平台上分布进行并行化。实验表明,社团挖掘的并行化AP聚类方法在社团挖掘精度不下降的情况下提高了海量数据的社团挖掘速率。     

一种改进的多视图聚类集成算法

近年来,针对大数据的数据挖掘技术和机器学习算法研究变得日趋重要。在聚类领域,随着多视图数据的大量出现,多视图聚类已经成为了一类重要的聚类方法。然而,大多数现有的多视图聚类算法受算法参数设置、数据样本等影响,具有聚类结果不稳定、参数需要反复调节等缺点。基于多视图K-means算法和聚类集成技术,提出了一种改进的多视图聚类集成算法,其提高了聚类的准确性、鲁棒性和稳定性。其次,由于单机环境下的多视图聚类算法难以对海量的数据进行处理,结合分布式处理技术,实现了一种分布式的多视图并行聚类算法。实验证明,并行算法在处理大数据时的时间效率有很大提升,适合于大数据环境下的多视图聚类分析。     

基于密度的分布式聚类算法研究

大量复杂异构数据分布于各个网络站点上,分布式聚类是海量数据处理的一个重要应用。该文针对基于密度的分布式聚类(DBDC)算法提出一种改进算法,利用局部聚类获取更佳的代表对象,将代表对象集附带相关信息传送至主站点,用增强的基于密度的聚类算法进行全局聚类,并更新子站点聚类。理论分析和实验结果表明,该算法在聚类质量和算法效率方面优于DBDC算法。     

基于三角不等式原理的TTSAS聚类加速算法

顺序聚类算法是一种非常直接和快速的算法，并且不需要提前确定聚类个数。但是当处理海量数据时，时间效率仍然有待提高。TTSAS算法是两个阈值的顺序聚类算法，在此基础上，该文应用三角不等式原理提出了TI_TTSAS算法，该算法避免了冗余的距离计算，实验结果证明，相对于TTSAS算法，TI_TTSAS在速度上有很大程度的提高，数据规模越大，改进效果越明显。并且聚类效果保持了TTSAS算法的准确性。     

不确定数据聚类的U-PAM算法和UM-PAM算法的研究

UK-means算法在处理不确定数据时对孤立点非常敏感,而且事先必须已知不确定数据的分布函数或概率密度,然而这在实际中往往很难获得。因此,针对UK-means在处理不确定测量数据时的不足,首先提出了基于区间数的PAM不确定聚类算法——U-PAM,该算法用区间数和标准差合理地描述了不确定测量数据的不确定性,进而完成有效的聚类;其次,针对海量不确定测量数据难以聚类的问题,基于U-PAM聚类算法,采用抽样技术提出了处理海量不确定测量数据的算法——UM-PAM算法,该算法先抽样,对样本数据聚类,然后再总体聚类;最后,基于U-PAM算法和CH聚类的有效性指标函数对聚类结果进行分析,以确定最佳聚类数。实验理论表明,所提算法聚类效果明显。     

ABC_Kmeans聚类算法的MapReduce并行化研究

随着数据的海量增长,数据聚类算法的研究面临着海量数据挖掘和处理的挑战;针对K-means聚类算法对初始聚类中心的依赖性太强、全局搜索能力也差等缺点,将一种改进的人工蜂群算法与K-means算法相结合,提出了ABC_Kmeans聚类算法,以提高聚类的性能;为了提高聚类算法处理海量数据的能力,采用MapReduce模型对ABC_Kmeans进行并行化处理,分别设计了Map、Combine和Reduce函数;通过在多个海量数据集上进行实验,表明ABC_Kmeans算法的并行化设计具有良好的加速比和扩展性,适用于当今海量数据的挖掘和处理。     

基于改进的分布式K-Means特征聚类的海量场景图像检索

针对传统的图像检索方法在处理海量数据时面临的问题,提出一种基于改进的分布式K-Means特征聚类的海量场景图像检索方法。对分布式K-Means算法进行改进,优化了初始聚类中心的选择和迭代过程,并将其应用与场景图像的特征聚类中;充分利用Hadoop分布式平台的海量存储能力和强大并行计算能力,提出了海量场景图像的存储和检索方案,设计了场景图像特征提取、特征聚类以及图像检索三个阶段分布式并行处理的Map和Reduce任务。多组实验表明,提出的方法数据伸缩率曲线平缓,取得了优良的加速比,效率大于0.6,检索的平均准确率达到了88%左右,适合海量场景图像数据的检索。     

多代表点特征树与空间聚类算法

空间数据具有海量、复杂、连续、空间自相关、存在缺损与误差等的特点，要求空间聚类算法具有高效率，能处理各种复杂形状的簇，聚类结果与数据空间分布顺序无关，并且对离群点是健壮的等性能，已有的算法难以同时满足要求。本文提出了一个适合处理海量复杂空间数据的数据结构一多代表点特征树。基于多代表点特征树提出了适合挖掘海量复杂空间数据聚类算法CAMFT，该算法利用多代表点特征树对海量的数据进行压缩，结合随机采样的方法进一步增强算法处理海量数据的能力；同时，多代表点特征树能够保存复杂形状的聚类特征，适合处理复杂空间数据。实验表明了算法CAMFT能够快速处理带有离群点的复杂形状聚类的空间数据，结果与对象空间分布顺序无关，并且效率优于已有的同类聚类算法BLRCH与CURE。     

分布式环境中聚类问题算法研究综述

传统的集中式聚类是对集中存放在单个站点的数据集进行聚类,但不能解决数据分布存储环境下的聚类问题,而分布式聚类算法是从分布存储的数据集中提取分类模式,因此能满足此需求。针对分布式聚类算法进行综述和分析。首先对现有的分布式聚类算法进行了分类,然后对每类算法的基本思想和优缺点进行了比较,最后采用Iris和Wine两个数据集对几种分布式聚类算法从聚类精度和聚类时间两方面进行了比较。     

基于Hadoop的改进聚类算法在图像修复上的应用

针对模糊聚类算法在运算大数据量时性能差的问题,提出基于Hadoop分布式平台的改进算法进行图像修复。对于受损图像信息,首先将Canopy算法和模糊聚类相结合在Hadoop平台上进行并行化,然后进行字典训练获得修复图像。实验结果表明,该算法在均方误差和峰值信噪比上均优于改进前的图像修复算法,提高了图像修复质量并且减少了算法的运行时间,适合修复海量图像。     

基于节点数据密度的分布式K-means聚类算法研究*

P2P(peer-to-peer)网络分布式聚类算法是利用P2P网络上各个节点的计算、存储能力以及网络的带宽,将算法的时间复杂度和空间复杂度平摊到各个节点,使处理和分析海量分布式数据成为可能,从而克服传统基于单个服务器的集中式聚类算法在数据处理能力等方面的限制。提出一种基于节点置信半径的分布式K-means聚类算法,该算法通过计算节点上数据分布的密度,找到同一类数据在节点的稠密和稀疏分布,从而确定聚类置信半径并指导下一步的聚类。实验表明,该算法能够有效地减少迭代次数,节省网络带宽;同时聚类结果也接近集中式聚类算法的结果。     

基于隐含变量的聚类集成模型

聚类集成能成为机器学习活跃的研究热点,是因为聚类集成能够保护私有信息、分布式处理数据和对知识进行重用,此外,噪声和孤立点对结果的影响较小.主要工作包括:第一,分析了把每一个基聚类器看成是原数据的一个属性这种处理方式的优越性,发现按此方法建立起来的聚类集成算法就具有良好的扩展性和灵活性;第二,在此基础之上,建立了latent variable cluster ensemble(LVCE)概率模型进行聚类集成,并且给出了LVCE 模型的Markovchain Monte Carlo(MCMC)算法.实验结果表明,LVCE 模型的MCMC 算法能够进行聚类集成并且达到良好的效果,同时可以体现数据聚类的紧密程度.     

基于链接划分的分布式WEB信息检索

分布式信息检索是面向海量WEB信息检索的一种有效手段.本文采用一种基于链接的聚类方法(LIBCA)来对网页数据进行划分,并采用BloomFilter优化LIBCA算法的计算效率,在检索过程中采用CORI集合选择算法和OKAPI BM25检索算法.基于最近3年的TREC WEB实验数据集,对比集中式检索、基于随机划分的分布式检索,实验结果表明,本文方法在P@10的指标上可达到甚至超过集中式检索的效果.效率方面的实验表明利用BloomFilter的LIBCA算法具有较高的划分效率,适合海量数据的处理.     

基于MapReduce的K_means并行算法及改进

针对传统k_means聚类算法在处理海量数据时所面临的内存不足、运算速度慢等问题,提出了一种基于MapReduce的K_means并行算法,同时为了改善k_means算法在初始值确定方面的盲目性,采用canopy算法进行改进。实验结果表明,基于MapReduce的K_means并行算法和改进后的算法均能产生良好的聚类效果,不仅提高了聚类质量,而且在处理大数据集方面,改进后的算法的还能够得到趋近于线性的加速比。     

DK-Means——分布式聚类算法K-Dmeans的改进

随着网络的广泛应用,大量的数据将分布存在.由于网络带宽、站点存储量等一系列限制,分布式聚类分析成为具有挑战性的研究课题.人们已经提出了若干分布式聚类方法,但这些方法效率低下.对分布式聚类算法k-Dmeans进行改进,提出了分布式聚类算法Dk-means. 该算法只传送各站点的聚簇信息,有效降低了分布式聚类过程中的数据通信量.理论分析和实验结果表明,算法Dk-means的效率优于k-Dmeans,并且可达到与k-means等效的聚类质量.     

图像数据库的保局聚类

面对日益增长的图像数据库,为用户提供一个简洁高效的搜索和浏览解决方案成为一个紧迫而且充满挑战的问题．图像聚类技术可以在许多方面为此提供帮助,例如图像数据预处理、用户界面设计．以及对搜索结果的聚类等．在众多聚类算法中,谱聚类（spectral clustering）方法由于能够解决复杂分布数据的聚类问题,以及接近全局最优的性能,成为近年来广受关注的一种方法．然而,目前存在的谱聚类方法,譬如normalized cut在处理新增数据点的聚类时,计算复杂度很高．提出了一种新的聚类算法——保局聚类．保局聚类在拥有许多非线性谱聚类方法优点的同时,又具有独特的数学特性——能提供显式的映射函数．这为在原数据集和新增数据集上进行高效的聚类提供了可能．实验结果显示,保局聚类比K均值聚类和主成分分析后的K均值聚类效果要好．实验同样显示,保局聚类与normalized cut效果可比,而前者更加高效．     

关键节点选择的快速图聚类算法

在众多聚类算法中,谱聚类作为一种代表性的图聚类算法,由于其对复杂数据分布的适应性强、聚类效果好等优点而受到人们的广泛关注.然而,由于其高计算时间复杂度难以应用于处理大规模数据.为提高谱聚类算法在大规模数据集上的可用性,提出关键节点选择的快速图聚类算法.该算法包含三个重要步骤:第一,提出一种充分考虑抱团性和分离性的快速节...     

基于数据预处理的并行分层聚类算法*

分层聚类技术在图像处理、入侵检测和生物信息学等方面有着极为重要的应用,是数据挖掘领域的研究热点之一。针对目前基于SIMD模型的并行分层聚类算法处理海量数据时效果不理想的问题,提出一种基于数据预处理的自适应并行分层聚类算法,在O((λn)2/p)的时间内对n个输入数据点进行聚类。其中1≤p≤n/log n,0.1≤λ≤0.3。将提出的算法与现有文献结论进行的性能对比分析表明,本算法明显改进了现有文献的研究结果。