大数据聚类算法与基于约束的遗传算法关联聚类问题的比较研究

B.Kranthi Kiran¹a . Vinaya博士先生²

印度泰伦加纳州卡里姆纳加尔市JNTUHCEJ计算机科学与工程系助理教授
印度泰伦加纳邦海得拉巴JNT大学计算机科学与工程系教授

摘要

聚类可以定义为将一组模式划分为互不关联且具有相同意义的组(称为集群)的过程。对分布式聚类算法日益增长的需求是由于现在普遍存在的数据库的巨大规模。以聚类规则的形式从大型数据库中提取知识的任务已经引起了相当多的关注。分布式聚类算法将计算与通信相结合，并探索分布式计算环境的所有方面。集成学习是多个模型(如分类器或专家)战略性地生成并组合以解决特定计算智能问题的过程。所提出的技术的一个重要特征是，即使对于非常高维的数据集，它也能够自动找到最优的聚类数量(即，簇的数量不必事先知道)，在这种情况下，跟踪聚类数量可能是非常不可能的。所提出的最优关联聚类算法使用遗传算法和贝叶斯因子的精度，能够在大多数基准数据集上以统计有意义的方式优于其他两种最先进的聚类算法。在两个多维数据集上，将所提出的最优关联聚类算法的结果与现有算法进行了比较。实验结果表明，与现有算法相比，该方法能够获得更好的聚类解决方案。

关键字

分布式聚类，集成学习，联想聚类，遗传算法，多维数据，海湾因子，列联表。

介绍

分布式计算和数据挖掘现在几乎无处不在[1,2]。作者提出了一种分布式数据挖掘的方法，即将局部分析模型(在分布式计算机系统的节点上并行构建)合并为全局分析模型，而无需构造分布式版本的数据挖掘算法。提出了不同的聚类和分类组合策略及其验证方法。数据挖掘是指从数据库中的海量数据中提取出隐藏的、以前未知的知识和对决策有潜在价值的规则[1,2]。关联规则挖掘是数据挖掘领域的一个主要研究领域，在实践中得到了广泛的应用。随着网络技术的发展和信息化水平的提高，分布式数据库被广泛应用。分布式数据挖掘是从分布在地理上的数据库中挖掘有利于管理和决策的全面知识。它已成为数据挖掘分析中的一个重要问题。分布式数据挖掘可以利用internet上不同站点的计算机来完成挖掘任务。它不仅可以提高挖掘效率，减少网络数据的传输量，而且有利于数据的安全性和隐私性。 Based on related theories and current research situation of data mining and distributed data mining, this thesis will focus on analysis on the structure of distributed mining system and distributed association rule mining algorithm[25,6].

聚类可以定义为将一组模式划分为互不关联且具有相同意义的组的过程，称为集群[1,2]。对分布式聚类算法的需求日益增长是由于现在普遍存在的庞大的数据库[6,26]。聚类是指“将一组对象划分为子集或集群，使一个集群内的对象之间的关系比分配给不同集群的对象更密切”，是数据挖掘的基本过程。特别是，聚类是知识获取的基础。它被应用于各个领域，包括数据挖掘、统计数据分析、压缩和矢量量化。聚类在社会科学中也有广泛的应用。

以聚类规则的形式从大型数据库中提取知识的任务已经引起了相当多的关注。各种组织收集、存储和检索大量数据的能力使得能够以聚类规则的形式提取知识的算法的开发成为必要。分布式聚类算法将计算与通信相结合，并探索分布式计算环境的所有方面。因此，分布式算法必须考虑到数据可能固有地分布到通过网络连接的不同松耦合站点。

近年来，大数据聚类在统计学、机器学习、模式识别、图像处理等领域得到了广泛的研究[13-15]。各地区对聚类技术的可扩展性和大数据聚类方法进行了大量的研究。为了克服大型数据库聚类中出现的问题，引入了不同的技术，包括通过聚类数据模型进行初始化，以及通过对完整数据集[7]进行初始化粗略划分。另一方面，最著名的代表是分区聚类技术，如CLARANS [11];层次聚类技术，如BIRCH [10];网格聚类技术，如STING[8]和WAVECLUSTER[9]。每种技术都有其优点和缺点。对于处理非常大的数据库，它们并不合适。大数据聚类算法很难同时获得较高的精度和胜任力。这两个目标在整个过程中都相互冲突。 The power of a single computer is not sufficient in order to process massive data sets. Parallel and allocated clustering is the key method. In a distributed environment, it will be extremely scalable and low cost to do clustering.

本文提出了一种基于关联约束的多维数据聚类算法。本文将贝叶斯因子应用于基于约束的数据聚类过程。此外，采用遗传算法获得最优聚类结果。我们在UCI机器学习库提供的两个真实世界的多维数据上评估了所提出的算法。本文的其余部分组织如下。第2节对相关工作进行了综述。第3节解释了关联聚类的基本概念。在第4节中，重点介绍了所提出的基于关联约束的最优聚类算法的有效实现。我们将在第5节中对我们的算法进行实验评估。最后，我们在第6节中进行总结。

相关工作回顾

在过去，聚类分析被广泛应用于医学、化学、社会研究等许多领域。主要目标是识别数据中存在的结构或集群。现有的聚类算法主要分为两大类:分层方法和划分方法。等级方法要么是聚集的，要么是分裂的。给定n个要聚类的对象，聚类方法从n个聚类开始。在每一步中，选择并合并两个集群。这个过程一直持续到生成n个集群。虽然分层方法已经成功地应用于许多生物学应用，但众所周知，它们有一个弱点，即它们永远无法撤消以前所做的事情。一旦一个聚合方法合并了两个对象，这些对象将永远不会重新组合到同一个集群中。

相比之下，给定要找到的分区数量k个，分区方法试图找到n个对象中最好的k个分区。通常情况下，通过分区方法发现的聚类比通过分层方法生成的k个聚类的质量更高。由于这种特性，划分方法的开发一直是聚类分析研究的重点之一。事实上，人们已经开发了许多划分方法，有的基于k-均值，有的基于k-中位数，有的基于模糊分析等。其中，我们选择k-medoid方法作为我们算法的基础，原因如下:首先，与许多其他划分方法不同，k-medoid方法对异常值具有很强的鲁棒性。其次，k-medoid方法发现的群集不依赖于检查对象的顺序。此外，它们对于数据点的平移和正交变换是不变的。最后但并非最不重要的是，实验表明，下面描述的k-medoid方法可以相当有效地处理非常大的数据集。现在我们代表两个最著名的k-medoid方法，所提出的算法是基于它们的。

答:帕姆

围绕方法划分是由考夫曼和卢梭提出的。PAM的方法是为每个簇总结一个有代表性的对象，以找到k个簇。这个有代表性的对象称为medoid，表示集群中位于最中心的对象。一旦中元体被选中，每个未被选中的中元体将与它最相似的中元体进行分组。更准确地说，如果Oj是一个未被选中的对象，Om是一个被选中的中星体，我们说Oj属于Om所代表的聚类，如果d (Oj, Om) = minO d (Oj, Om)，其中符号minO表示在所有中星体中Oe的最小值，符号d (O1, O2)表示O1和O2之间的不相似性或距离。所有的不相似值都作为PAM的输入。最后，通过一个对象与其聚类中间点之间的平均不相似度来衡量聚类质量。为了找到k个中间点，PAM从任意选择的k个对象开始。然后在每个步骤中，在选定对象Om和非选定对象Op之间进行交换，只要这样交换可以提高聚类的质量。PAM算法

i.任意选择k个代表性对象。

2计算所有Om, Op对象对的TCmp，其中Om当前被选中，Op未被选中。

3选择对应minOm, Op TCmp的对Om, Op。如果最小TCmp为负，则替换Om和Op，并返回步骤ii。

iv.否则，对于每个非选择对象，寻找最相似的代表性对象。

实验结果表明，该算法对小数据集的处理效果令人满意。但它在处理中型和大型数据集时效率不高。

b .克拉拉

由Kaufman和Rousseeuw引入，用于处理大型数据集，CLARA依赖于抽样。CLARA没有为整个数据集寻找代表性对象，而是绘制数据集的一个样本，对样本应用PAM，然后找到样本的中位数。重点是，如果样本是以足够随机的方式绘制的，样本的中位数将近似于整个数据集的中位数。为了得到更好的近似，CLARA抽取多个样本，并给出最佳的聚类结果作为输出。在这里，为了精确起见，聚类的质量是基于整个数据集中所有对象的平均不相似度来衡量的，而不仅仅是样本中的这些对象。

算法的克拉拉

i.对于i = 1 ~ 5，重复执行以下步骤。

2从整个数据集中随机抽取一个40+2k对象的样本，调用PAM算法求样本的k个中位数。

3对于整个数据集中的每个对象Oj，确定k个中位数中哪一个与Oj最相似。

iv.计算前几步得到的聚类的平均不相似度。如果该值小于当前最小值，则使用该值作为当前最小值，并保留步骤ii中找到的k个中位数作为迄今为止获得的最佳中位数。

v.返回步骤I，开始下一次迭代。

在某些技术状态下，会使用以下概念:

i. CLARANS的引入和发展，旨在使用随机搜索来促进大量对象的聚类;

2研究了三种不同的方法来评估两个多边形之间的精确分离距离的效率和有效性，一种是利用顶点之间的最小距离来高估精确距离的方法，另一种是利用多边形的等线矩形之间的分离距离来低估精确距离的方法。

A.整体学习

集成本身就是一种监督学习算法，因为它可以被训练，然后用于做出预测。因此，训练过的集合只代表一个假设。然而，这个假设不一定包含在构建它的模型的假设空间中。因此，集成可以在它们所能表示的函数中显示出更大的灵活性。集合将多个假设结合起来形成一个更好的假设(希望如此)。换句话说，集成是一种将许多弱学习器结合起来以产生一个强学习器的技术。术语集成通常用于使用相同的基础学习器生成多个假设的方法。集成学习主要用于提高(分类、预测、函数逼近等)模型的性能，或降低不幸选择一个差模型的可能性。集成学习的其他应用包括为模型做出的决策分配置信度，选择最优(或接近最优)特征，数据融合，增量学习，非平稳学习和纠错。

B.分布式数据挖掘算法

大多数DDM算法都是基于它们可以应用于给定分布式数据的潜在并行性而设计的。通常，相同的算法同时在每个分布式数据站点上操作，每个站点生成一个本地模型。随后，所有局部模型被聚合以生成最终模型。DDM算法的成功本质上在于聚合。每个局部模型表示局部一致的模式，但缺乏包含全局有意义知识所需的细节。由于这个原因，许多DDM算法需要集中本地数据的一个子集来补偿它。因此，最小的数据传输是成功的DDM算法的另一个关键属性。数据挖掘处理以可伸缩的方式分析数据的问题。DDM是数据挖掘的一个分支，它定义了一个框架来挖掘分布式数据，关注分布式数据和计算资源。近年来，在分布式数据集约束下工作良好的数据挖掘算法的开发受到了数据挖掘社区的极大关注。 Most distributed clustering algorithms have their foundations in parallel computing, and are thus applicable in homogeneous scenarios. They focus on applying centre-based clustering algorithms, such as K-Means, K-Harmonic Means and EM in a parallel fashion. Here we are discussing clustering algorithm called K-Means and will also try to focus partially on its distributed version clustering algorithm called DK-means. It is proved that this algorithm achieves same result as of K-means. We are trying to focus on the areas like, how this algorithm works, what king of results it will produce, what will be the limitations, which environment it will require, what will be the future scope and many more.

如图1所示，DDM的目标是基于分布式资源的类型和可用性进行数据挖掘操作。它可以选择将数据集下载到单个站点，并在中心位置执行数据挖掘操作。然而，DDM中的决定应该基于计算、存储和通信能力的特性。这与传统的集中式数据挖掘方法形成了对比，在分析之前在单一位置收集数据是一个不变的特征。

在DDM文献中，关于数据如何在站点间分布通常采用一两个假设:同质(水平分区)和异质(垂直分区)。这两种观点都采用了一个概念观点，即每个站点上的数据表都是单个全局表的分区。

•在同构情况下，全局表是水平分区的，每个站点上的表都是全局表的子集:它们具有完全相同的属性。

•在异构情况下，表是垂直分区的。每个站点包含一个集合或列(站点没有相同的属性)。但是，每个元组每个站点假定包含唯一标识符，以方便匹配。重要的是要强调全局表观点是严格的概念性的。不一定假定这样一个表是物理上实现的，并被划分成每个站点上的表。

近年来，在分布式数据集约束下工作良好的数据挖掘算法的开发受到了数据挖掘社区的极大关注。DDM领域已经成为一个活跃的研究领域。文献中的大部分DDM方法都是在一个抽象的架构上运行的，该架构包括多个具有独立计算能力和存储能力的站点。本地计算在每个站点上完成，中心站点与每个分布式站点通信以计算全局模型，或者使用点对点体系结构。在后一种情况下，单个节点可能与资源集中式节点通信，但它们通过通过异步网络传递消息与邻近节点通信来执行大部分任务。

为例。站点可以表示以特殊方式相互连接的独立传感器节点。适用DDM的分布式场景的一些特性如下。

1.该系统由多个独立的数据和计算站点组成，仅通过消息传递进行通信。

2.站点之间的通信是昂贵的。

3.站点有资源限制，例如电池电量。

4.网站存在隐私问题。

通常来说，沟通是一个瓶颈。由于假定通信仅通过消息传递来实现，因此文献中许多DDM方法的主要目标是最小化发送的消息数量。

有些方法还尝试跨站点进行负载平衡，以防止性能受到任何单个站点的时间和空间使用的影响。在许多应用程序中，“为了执行非分布式数据挖掘而构建单一数据库可能是不可行或根本不可能的”。传输大块数据的成本可能令人望而却步，并导致非常低效的实现。隐私在DDM中扮演着重要的角色，因为一些参与者可能不希望分享他们的数据，但仍然参与DDM。

数据聚类是一种数据探索技术，它允许将具有相似特征的对象分组在一起，以便于对其进行进一步处理。数据聚类技术在工程上有很多应用，包括用于元胞制造的零件族识别。聚类是将一组给定的模式划分或分组成互不关联的聚类的过程，这样一来，同一聚类中的模式是相似的，而属于两个不同聚类的模式是不同的。聚类已经在包括神经网络、人工智能和统计学在内的各种应用领域中被广泛研究。

以聚类规则的形式从大型数据库中提取知识的任务已经引起了相当多的关注。各种组织收集、存储和检索大量数据的能力使得能够以聚类规则形式提取知识的算法的开发成为必要。分布式聚类算法将计算与通信相结合，并探索分布式计算环境的所有方面。因此，分布式算法必须考虑到数据可能固有地分布到不同的松散耦合

通过网络连接的站点。在分布式计算环境中，数据集分布在许多不同的站点上。……米,

所以

此外，让我们假设有一个中心站点O将保存最终的聚类结果。

基于关联约束的最优聚类算法

本文提出的基于关联约束的最优聚类算法主要集中在基于约束的多维数据聚类上。约束有助于识别要聚类的正确数据，关于数据的知识也被视为约束，提高了聚类的准确性。结合聚类方法有助于根据约束值识别两个聚类之间的关系。

输入:多维数据D

中间过程:子集形成和基于最优关联约束的数据聚类

Dd =离散化数据

fmax→每个特征的最大值

F min→每个特征的最小值

N→维度

M, n→子集

I, j→子空间

I→区间

d→欧氏距离

L→为MTH子集选择的最短距离的第一个L no

P→高维数据空间中的点

→每k的偏差

开始

对所有

离散化

计算F的max, F的min归一化为:

叫Subset_formation

结束

Subset_formation

在空格中随机选择P

对于所有p

计算d

为m选择第一个l

重复

结束

在基于遗传算法的最优联想聚类算法中，使用一条染色体通过两组函数(维度选择和最优聚类生成)表示联想聚类任务或过程，并使用适应度函数对每条染色体进行单独评估。在进化循环中，选择一组个体进行进化交叉和突变。自适应地选择进化算子的可能性。交叉运算符将两个个体(双亲)通过连接双亲的各个部分转换为两个子代。现在，单点交叉用于转换两个个体。突变算子作用于单个个体，并通过突变该个体形成后代。在适应度函数的基础上，形成新一代，对最近产生的个体进行评估。每代都选择适应度值最好的染色体。这一过程在用户或程序本身经过若干代之后结束，此时获得的最佳染色体将被视为最佳解决方案。上一代的最佳字符串为我们的集群问题提供了解决方案。

结果与讨论

所提出的聚类算法在配置Intel (R) Core i5处理器、3.20 GHz、4gb RAM的windows机器上执行，操作系统平台为Microsoft winidow7 Professional。我们也使用了mat lab的最新版本(7.12)来实现。

4.1数据集描述

对于实验结果，从UCI机器学习数据库知识库[29]下载了两个真实世界的数据集，即成人和人口普查。

UCI成人数据:这是年收入数据，由48842个实例(连续和离散的混合)或45222个实例(如果除去未知值的实例)组成。它还包含6个连续属性，8个名义属性和1个类属性。这是从人口普查数据集中提取出来的。

UCI普查数据:人口普查数据有2,458,284条记录，包含68个分类属性，总计约352兆字节。它来源于uscensus1990原始数据集，该数据集是从(美国商务部)人口普查局网站上使用数据提取系统获得的。

结果表明，本文方法的准确率为76.4%，比现有算法在子集20中仅为71.33%的准确率高。可以看出，利用UCI普查数据，与现有的[23]算法相比，本文算法在聚类过程中所花费的时间最小。

•UCI成人数据的实验结果

•UCI人口普查数据的实验结果

结论

在本文中，我们提出了一种利用遗传算法进行高维聚类的有效方法。然后，通过bays因子计算过程，执行基于联想约束的聚类过程。并将遗传算法应用到优化过程中，发现最优聚类结果。基于约束的聚类算法有助于识别需要聚类的正确数据，并将考虑数据的知识作为约束，提高了聚类的精度。数据约束还有助于指示与群集任务相关的数据。我们的实验评估表明，提出的算法在两个多维数据集上优于现有的算法。实验结果表明，该聚类算法性能高、有效、灵活。

表格一览


表1	表1 b	表2一个	表2 b

数字一览

图1

参考文献

《数据挖掘导论》，见:数据库中知识发现的原理。CMPUT690，阿尔伯塔大学，加拿大，1999。

Kantardzic Mehmed。《数据挖掘:概念、模型、方法和算法》，John Wiley and Sons, 2003年。

E. Wainright Martin, Carol V. Brown, Daniel W. DeHayes, Jeffrey A. Hoffer和William C. Perkins，“管理信息技术”，Pearson Prentice-Hall 2005。

Andrew Kusiak和Matthew Smith，“产品和生产系统设计中的数据挖掘”，载于《控制年鉴》，第31卷，第1期。雷竞技苹果下载1，页147- 156,2007。

Mahesh Motwani, J.L. Rana和R.C Jain，“使用领域知识快速挖掘关联规则”，国际工程师和计算机科学家会议论文集，2009。

Souptik Datta Kanishka Bhaduri Chris Giannella Ran Wolff Hillol Kargupta，“点对点网络中的分布式数据挖掘”，互联网计算杂志，第10卷，第10期。4, pp.18-26。2006.

Ron Wehrens和Lutgarde M.C. Buydens，“基于模型的聚类图像分割和通过采样的大数据集”，分类杂志，第21卷，第231-253页，2004。

王伟，杨建民，王伟民，“一种基于统计信息网格的空间数据挖掘方法”，计算机工程，1997。

G. Sheikholeslami, S. Chatterjee，和A. Zhang，“波集群:非常大的空间数据库的多分辨率聚类方法”，VLDB，第428-439页，1998。

T. Zhang, R. Ramakrishnan和M. Livny，“BIRCH:一种非常大数据库的高效数据聚类方法”，《ACM SIGMOD国际数据管理会议论文集》，第103-114页，1996。

吴仁涛，韩俊:“空间数据挖掘的高效聚类方法”，第20届大型数据库国际会议论文集，pp.144-155, 1994。

Inderjit S. Dhillon和Dharmendra S. Modha，“分布式内存多处理器上的数据聚类算法”，KDD研讨会高性能知识发现论文集，第245- 260,1999。

M. Ester, H. Kriegel, J. Sander，和X. Xu，“一种基于密度的算法在有噪声的大型空间数据库中发现集群”，在SIGKDD，第226-231页，1996。

吴瑞涛、韩杰，“空间数据挖掘的高效聚类方法”，计算机工程，1994。

T. Zhang, R. Ramakrishnan, M. Livny。Birch，“一种用于超大型数据库的高效数据聚类方法”，载于《SIGMOD》，第103-114页，1996年。

周春光，季金超，韩晓，王哲，“一种基于模糊k-原型的混合数据聚类算法”，系统工程学报，vol. 30, pp. 129-135, 2012。

陈磊，陈春林，陆明，“一种多核模糊c均值算法在图像分割中的应用”，计算机工程学报，vol. 41, no. 1。5，第1263-74页，2011。

陈文彦，宋阳秋，白红杰，林志仁，“分布式系统中并行谱聚类的研究”，电子工程学报，Vol.33, No.3, pp. 568 - 586, 2011。

Eshref Januzaj, Hans-Peter Kriegel和Martin Pfeifle，“基于可扩展密度的分布式聚类”，第八届欧洲数据库知识发现原理与实践会议论文集，231- 2442004。

“分布式数据聚类中的推理”，人工智能工程应用，Vol.19, No.4, pp.363-369, 2005。

金若明，Anjan Goswami, Gagan Agrawal，“快速准确的核外分布式K-Means聚类”，《知识与信息系统学报》，2006年第10卷第1期，pp. 17-40。

姬根林，凌晓涵，“基于集成学习的分布式聚类研究”，《知识发现与数据挖掘》，Vol. 32, pp . 121 - 121, 2007。

Olivier Beaumont, Nicolas Bonichon, Philippe Duchon, Lionel Eyraud-Dubois和Hubert Larcheveque，“大规模平台中资源聚类的分布式算法”，分布式系统原理，Vol.5401, pp.564-567, 2008。

Samuel Kaski, Janne Nikkila¨，Janne Sinkkonen, Leo Lahti, Juha E.A. Knuuttila和Christophe Roos，“探索功能基因组数据集之间依赖关系的关联聚类”，IEEE/ACM计算生物学和生物信息学学报，第2卷，第3期，pp: 203-216, 2005。

姚玉辉，陈丽辉，王安基，“基于联想聚类神经网络的基因数据聚类”，第九届神经信息处理国际会议论文集，Vol.5, pp: 2228- 2232, 2002。

Hesam Izakian, Ajith Abraham, Vaclav Snasel，“使用混合模糊c均值和模糊粒子群优化的模糊聚类”，世界自然与生物计算大会(NaBIC 2009)，印度，IEEE出版社，第1690-1694页，2009。

Swagatam Das, Ajith Abraham, Amit Konar，“使用改进的差分进化算法的自动聚类”，IEEE系统，人类和控制论汇刊- A部分:系统和人类，第38卷，第1期，2008。

J.H.霍兰德，《自然和人工系统的适应》，麻省理工学院出版社，剑桥，马萨诸塞州，1992年。

I.J.好。，“On the Application of Symmetric Dirichlet Distributions and Their Mixtures to Contingency Tables,” Annals of Statistics, vol. 4, pp. 1159-1189, 1976.

UCI机器学习数据库库，加州大学欧文分校，信息和计算机科学系。