基于划分的模糊和非模糊聚类方法在数据聚类中的比较研究

Egyptian Informatics Journal（2016）17，183开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章模糊与非模糊分类方法B. Simhachalama，*， G. 格涅桑湾a印度安得拉邦维萨卡帕特南GITAM大学数学系，邮编：530045b印度安得拉邦Rajahmundry Adikavi Nannaya大学数学系533296接收日期2015年7月27日;修订日期2015年9月23日;接受日期2015年10月30日2015年11月29日在线发布摘要在数据聚类中，基于划分的聚类算法是一种应用广泛的聚类算法。在各种划分算法中，模糊算法、模糊c-均值（FCM）、Gustafson-Kessel（GK）和非模糊算法、k-均值（KM）是最流行的方法。k-means和Fuzzyc-Means使用标准的欧几里得距离度量，在这项工作中，这些算法与不同的著名的现实世界的数据集，肝脏疾病和葡萄酒从UCI仓库的比较研究。基于聚类输出准则分析了三种算法的性能将结果与从储存库获得的结果进行了比较结果表明，此外，实验结果表明，k-means优于模糊c-Means和因此，k-means算法的效率优于模糊c-Means算法和©2015制作和主办由Elsevier B.V.代表计算机与信息学院开罗大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍许多组织在其数据库中生成并存储大量数据从数据库中提取最有用的知识的方法被称为数据挖掘或*通讯作者。联系电话：+91 9866118074。电子邮件地址：drbschalam@gmail.com（B.Simhachalam），prof. ganesan@yahoo.com（G. Ganesan）。开罗大学计算机和信息系负责同行审查。数据库知识发现（KDD）。数据挖掘是一个分析过程，发现数据集之间有效的，未被怀疑的关系，并将数据转换为用户可以理解和有用的结构。数据分析包含几种用于处理数据的技术和工具。分类或聚类是数据分析中它是一种多变量分析技术，将数据集划分为数据集中的组（类或簇），使得最不可辨别的对象属于同一组，而可辨别的对象属于不同的组。聚类方法被用作许多领域中的常用技术，例如模式识别、机器学习、图像分割、医学诊断和生物信息学[5]。http://dx.doi.org/10.1016/j.eij.2015.10.0041110-8665© 2015制作和主办Elsevier B. V.代表开罗大学计算机和信息学院这是一个在CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词模糊c-均值算法;Gustafson–Kessel;基于划分的聚类184B. Simhachalam，G.Ganesan×ðÞ四分之二]2XX聚类的两个重要特征是基于划分的聚类和基于层次的聚类。基于分区的聚类算法能够通过使用适当的目标函数来发现聚类的底层结构[15]。k-means（KM）算法、模糊c-Means（FCM）算法和Gustafson-Kessel（GK）聚类算法是广泛使用的基于划分的聚类算法。在欧氏距离测度的基础上提出了k均值和模糊c均值算法，并在Gustafson-Kessel（GK）聚类算法中提出了一种自适应的距离测度。Jaindong，Hongzan，Jaiwen，Qiyong[16]分析了k-means和Fuzzy c-Means算法的性能，并报告说k-means方法优于FCM使用临床和模拟数据进行动脉输入功能（AIF）检测。Velmurugun[14]使用不同形状的任意分布数据点比较了k-means和模糊c-均值算法的聚类性能，并报告说k-means的性能优于FCM。Simhachalam和Ganesan[12]分析了医学诊断系统上模糊c均值和Gustafson-Kessel算法的性能，并报告GK方法的性能优于FCM方法。Wang和Gar- ibaldi[17]比较了k均值和模糊c均值算法对从辅助淋巴结组织切片收集的红外光谱的性能。Mousumi Gupta[8]提出了Gustafson-Kessel算法中的数据缩放方法，用于缩放数据上的目标检测，并与FCM方法进行了比较。Neha和Seema[9]使用聚类有效性测量检查了FCM和GK之间的性能。Dibya Joyti和Anilkumar Gupta[3]基于时间复杂度评估了k-means和模糊c-Means算法之间的性能。Soumi Gosh和Sanjay KumarDubey[13]根据聚类输出的效率和计算时间评估了k-means和模糊c-Means算法Bharati和Gohokar[1]比较了彩色图像分割性能，k-means和Fuzzy c-Means算法。本 文 的 工 作 旨 在 比 较 三 种 聚 类 技 术 ， k 均 值（ KM ） ， 模 糊 c 均 值 （ FCM ） 和 Gustafson-Kessel（GK）的性能最流行的现实世界的数据集，如肝脏疾病和葡萄酒被应用到测试这些算法的性能和比较分析，在这项工作中。本工作的其余部分组织如下：在第2节中，简要介绍了数据集和三种算法的细节。在第3节中，给出了结果和讨论，结论见第4节。2. 材料和方法聚类是一种无监督的数据分析，用于将一组记录或对象划分为具有相似特征的簇或类分区是以这样一种方式完成的，即大多数相似（或相关）的对象放在一起，而不相似（或不相关）的对象放在不同的类或组中聚类方法的理想特性是能够处理不同类型的属性，维度、用最少的知识有效处理离群值和噪声、发现数据的潜在形状和结构的能力、可扩展性、可用性和可聚类方法分为五种：划分方法、层次方法、基于数据密度的方法、基于网格的方法和基于模型或软计算的方法。在这五种方法中，基于划分的k-means（KM）聚类算法、模糊c-Means（FCM）聚类算法和2.1. 数据集肝 脏 疾 病 和 葡 萄 酒 的 真 实 世 界 数 据 集 分 别 来 自Richard[11]和Forina[4]捐赠的UCI机器学习库。肝脏数据集包含341个样本，每个样本有6个属性或血液检测。这些血液检查能够检测可能因过度饮酒而引起的肝脏疾病。属性是血液检查的测量值，即平均红细胞体积（mcv）、碱性磷酸酶（alkphos）、丙氨酸氨基转移酶（sgpt）、天冬氨酸氨基转移酶（sgot）、γ-谷氨酰转肽酶（gammagt）和每天饮用的半品脱酒精饮料当量（饮料）的数量。根据肝脏疾病将341个样本聚类为两个不同的类别：第1类包含142个样本，第2类包含199个样本。葡萄酒数据集包含178个样本，每个样本具有来自三个不同品种但生长在意大利同一地区的葡萄酒的13个属性或化学分析。根据品种的不同，将样品分为三类：品种1含59个样品，品种2含71个样品，品种3含48个样品。这些属性是酒精度、苹果酸、灰分、灰分碱度、镁、总酚、黄酮、非黄酮类酚、原花青素、颜色强度、色调、稀释葡萄酒的OD280/OD 315和脯氨酸的化学分析值2.2. k-means聚类MacQueen[7]在1967年引入了K-Means或Hard C-Means算 法 。 它 是 一 种 划 分 算 法 ， 用 于 将 数 据 分 类 为c16c6N类，每个对象（观察）在任何时候只能属于一个类。考虑一个具有N个观测值的数据集Z。每个观测值都是一个n维的行向量，zkzk1;zk2;. zknn;ffin数据集Z表示为N n矩阵。Z的行表示样本（观测值），列是这些样本（对象）的测量值k-means模型通过迭代优化其目标函数（平方误差函数）来实现其分区，该目标函数如下所示：CNJVkzk-vik21i<$1k <$1其中kzk-vik2是计算的第k个物体zk和第i个质心vi之间的欧几里得距离。该算法包括以下基本步骤：模糊和非模糊分类方法1852TminXM2我MTPPPN拉斯X2不¨¨我我我一其中，第i个聚类-1（未知的）集群原型（中心）的tor原型，ikAKIAK我K我我XXXMð2步骤2通过增加步长值k。步骤1：初始化所需的聚类数c。步骤2：放置c簇质心。第三步：将每个样本分配到一个聚类，样本和质心之间的最近距离Ci1/1第2步：使用Uk 确定质心向量V½v1;v2;.. . ;vc]通过使用等式（4）、 步骤3：通过使用等式1更新Uk;Uk1。（五）、步骤4：如果-Uk1-Uke，则停止，否则重复从第四步：更新的集群质心使用vi¼1Pcizi，其中，ci是第i个聚类中的对象的数量步骤5：确定物体和质心之间的最近距离。第六步：更新聚类中的样本。第7步：从第3步开始重复，直到满足停止标准k-means算法是一种迭代方法。该算法可以多次运行，以减少初始随机选择质心所造成的敏感性。2.3. 模糊c-均值聚类模糊c均值算法（FCM）是最常用的模糊聚类方法之一。模糊C均值算法是基于模糊理论发展起来的。该方法利用隶属度函数进行赋值每个对象的隶属度值范围为0到1的虽然FCM是一种流行的聚类方法，但它也有一些缺点。例如，当该方法应用于划分两个聚类时，它会产生噪声点，其中对象与两个聚类中心的距离相等。FCM使用标准的欧几里德距离范数。2.4. Gustafson–Kessel另一种模糊迭代算法GK（扩展FCM）最初由Gustafson和 Kessel[2] 提 出 ， 后 来 由 Babuska 等 人 [10] 改 进 。Babuska等人引入了自适应距离范数，以便在协方差矩阵Fi由于矩阵Ai的选择而不能是非奇异的时检测一个数据集中的聚类的不同几何形状。该算法中的距离度量由下式给出：FCM的特点是每个对象属于具有不同隶属度值的每个聚类。将数据集Z划分为c个簇是用模糊划分表示的2ikAi <$kzk-vikA<$zk-viAizk-vi;16i6c;16k6N矩阵U1/2li k]c×N。Z的模糊划分空间是GK算法目标泛函定义为：集合ik（Xc）XNminM2）的方式Mfc¼（U2ffic×N=lC2½0;1];8i;k;勒伊克N¼1;8k; 0<1ik;8i）|U{;zV} JZ;U;V;fAig¼i<$1k<$1 likð8Þ1/1k¼1ð2Þ为了获得可行解，范数诱导矩阵为约束为jAj ^q; q> 0; 8i.模糊c均值模型通过迭代优化其目标函数，Ai的表达式定义为：|{z}U;VCNJZ;U;Vli<$1k<$1（kzk-vik）其中U2MfcAi½qidetFi]n-1个 F-1;16i6cð3Þ这里，m2½1;1 π是确定12C我Fi¼½/i1. . . /in]diagki1.. . ki n . /in]PNlNMik关于10模糊度，V/4/2v;v;。 . . 其中，V2ffin是向量。Fi¼k¼1ik;16i6c;的会员功能和的距离度量是计算的Eqs。（3）Fi1-cFicdetF01=nI并且特征值和特征向量被设置为kij^ maxj kij= bvi¼Nk¼1利格Mð4Þ对于所有j，其中maxj kij= kij> b。该算法包括以下基本步骤：klik..02！-1第一步：随机初始化U=0;c，终止容限-lik¼Cj1DikADjkAM-1ð5Þ实例e> 0，群集体积q i> 0（通常为1），b1/2 0;1，以及加权参数c2/20;1]。步骤2：通过使用等式2来（4）、Dkz-vkz-vAz-v6步骤3：计算聚类协方差矩阵F 通过使用其中16i6c，16k6N。当目标函数收敛到局部最小值时，迭代终止。Bezdek等人[6]提出了具体的算法。该算法包括以下基本步骤：步骤1：随机初始化U_（0）;c;m，终止容限e> 0。当量（十）、步骤4：通过使用等式2获得距离。（七）、步骤5：通过使用等式2更新Uk;Uk1。（4）、6.如果Uk1-Uk

下载后可阅读完整内容，剩余1页未读，立即下载