ModEx和Seed-Detective: 两种聚类技术的性能比较及其在数据集上的表现

Journalof King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.comModEx和Seed-Detective：通过在K-MeansMd Anisur Rahman，Md Zahidul Islam*，Terry Bossomaier澳大利亚查尔斯特大学计算与数学学院复杂系统研究中心接收日期：2013年11月19日;修订日期：2014年2月21日;接受日期：2014年2015年3月23日在线发布摘要在本文中，我们提出了两种聚类技术，称为ModEx和种子侦探。ModEx是一种称为Ex-Detective的现有聚类技术的修改版本。它解决了前侦探的一些限制。Seed-Detective是ModEx和Simple K-Means的组合。Seed-Detective使用ModEx生成一组高质量的初始种子，然后将其作为K-Means的输入，用于生成最终聚类。高质量的初始种子被期望通过K-Means产生高质量的聚类。将Seed-Detective和ModEx的性能与Ex-Detective，PAM，简单K均值（SK），基本法拉第点启发式（BFPH）和新法拉第点启发式（NFPH）的性能进行了比较。我们使用三个聚类评估标准，即F-测度，熵和纯度以及我们从UCI机器学习库中获得的四个自然数据集。在数据集上，我们提出的技术在F-测度、熵和纯度方面比现有技术表现得更好。符号测试结果表明，Seed-Detective（和ModEx）优于现有技术具有统计学意义。2015作者。制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍*通讯作者。联系电话：+61 2 63384214;传真：+61 2 63384649.电子邮件地址：arahman@csu.edu.au（硕士）Rahman），csu.edu.au（M.Z.Islam），tbossomaier@csu.edu.au（T.Bossomaier）。网址：http://csusap.csu.edu.au/~zislam/（M.Z.伊斯兰教）。沙特国王大学负责同行审查。聚类是将相似的记录划分到一个簇中，将不相似的记录划分到不同的簇中的过程。它通过从大量数据中提取隐藏模式来帮助决策过程因此，从数据集中产生高质量的聚类是很重要的。K-Means是一种非常常用的聚类算法。它需要用户输入聚类数。然后，它随机选择与用户定义的聚类数量相同数量的初始种子（即，表示聚类中心的记录）（Ahmad和Dey，2007; Bai等人，2011;Huang，1997; Khan，2012; Tan等人， 2005年）。每个记录http://dx.doi.org/10.1016/j.jksuci.2014.04.0021319-1578年，作者。制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词聚类;分类;K均值;聚类评价;数据挖掘114M.A. Rahman等人然后分配给与记录具有最小距离的初始种子因此，记录最初被划分为多个组。一旦记录被分配给种子，则再次计算每个分区的新中心点使用新的中心点，记录再次被分割。计算新中心点和记录划分的过程继续，直到满足终止条件。由于K-Means的简单性，它是一种常用的聚类技术。然而，对于用户来说，很难猜测并提供数据集的正确聚类数（ChuanTan等人，2011; Jain，2010）。此外，由于初始种子选择中使用的随机性，K均值可能选择质量差的初始种子，从而导致从数据集产生的质量差的聚类（Bagirov，2008; Bai等人，2011; Maitra等人， 2010年）。因此，在本研究中，我们提出了一种聚类技术称为种子检测，它自动获得聚类的数量和一组高质量的初始种子，通过使用一个确定性的过程。然后将高质量的种子作为K-Means的初始种子输入，以产生数据集的最终聚类。高质量的初始种子被期望通过K-Means产生高质量的聚类。由于Seed-Detective使用确定性的初始种子，因此也避免了K均值的随机性。此外，我们注意到，种子侦探发现高质量的初始种子，通过使用另一种聚类技术称为ModEx，这也是本文提出的。ModEx是现有聚类技术Ex-Detective（Islam ，2008;Islam and Brankovic，2011）的改进版本。ModEx解决了前侦探的一些限制。虽然ModEx提高了Ex-Detective的聚类质量，但在为Seed-Detective 寻找高质量初始种子时应用ModEx提高了Seed-Detective实现的聚类质量。我 们 将 种 子 检 测 的 性 能 与 ModEx 、 PAM （ Han 和Kamber，2006）、简单K均值（Huang，1997; Tan等人，2005）、基本法拉第点启发式（BFPH）（He，2006）和新法拉第点启发式（NFPH）（He，2006）。我们通过三个聚类评估标准，即F-度量，熵和纯度，使用我们从UCI机 器 学 习 存 储 库 获 得 的 四 个 自 然 数 据 集 （ Bache 和Lichman，2013）来比较这些技术的性能。还将ModEx的性 能 与 Ex-Detective 、 PAM （ Han 和 Kamber ， 2006 ） 、Simple K-Means （ SK ） （ Huang ， 1997; Tan 等 人 ，2005）、基本法拉第点启发式（BFPH）（He，2006）和新法拉第点启发式（NFPH）（He，2006）。请注意，决策树（像许多其他算法，如ANN）通常用于分类任务，其中数据集的记录根据数据集的类属性（也称为标签或类值）的值进行分类（Han和Kamber，2006;Islam，2012）。应用分类器（如决策树（DT））的数据集需要具有class属性。类属性的示例可以是患者数据集中关于“疾病诊断”的属性。但是，应用聚类算法的数据集不需要具有class属性。聚类算法的目标是将记录分组到簇中。在聚类之后，类值通常被分配给记录。一旦将类值分配给记录，可以从记录中构建分类器，以便学习模式（例如逻辑规则）并预测没有标签的未来记录虽然决策树通常用于分类任务，但一些称为Detective和Ex- Detective（Islam和Brankovic，2011）的现有技术使用决策树进行聚类。例如，Detective使用决策树查找分类属性值之间的相似性，而Ex-Detective使用决策树查找相似记录。根据现有的方法，我们提出的技术也使用决策树进行聚类。图1显示了一个决策树（DT），它将决策树由许多节点（图1中的矩形）和叶子（图中的椭圆形）组成，其中节点测试属性并根据节点处测试的属性值将数据集划分为相互排斥的水平段（Islam，2012; Quinlan，1993，1996）。例 如 ， 图 1 中 的 树 在 根 节 点 （ 0 级 节 点 ） 测 试 属 性Qualification，并将数据集划分为多个段。在最左边的段中，所有记录都将PhD作为Qualification属性的值。叶子表示一组记录（即水平段），其中所有记录理想地具有相同的类值。如果一个叶子的所有记录都有相同的类值，那么这个叶子被称为例如，叶1是一个异构叶，其中总共有四个记录，其中三个记录的类值为“Acad”（Academics的缩写形式），其余一个每个叶子都有一个逻辑规则，显示属于规则的前提条件和记录的分类，即满足规则的前提条件。例如，叶1的逻辑规则是如果资格=博士职业=学术（4：1）。本文的主要贡献如下。我们提出了一些修改现有的聚类技术称为前侦探。我们将修改后的版本称为ModEx。我们还提出了另一种称为Seed-Detective的聚类技术，该技术使用ModEx来找到一组高质量的初始种子，然后将它们馈送到传统的K-Means中，以发现高质量的聚类。我们还实现了我们提出的技术和一些现有的技术。0级1级2级3级图1将职业视为类属性的DT。博学士硕士叶子1：学术= 3叶片2 ： 物理=4学>35岁<=35人叶三：工程师=结婚单个第4页：第5页：学术= 2工程师=2资格Acad=学术工程师=工程师Phys=医师婚姻状况年龄两种新的高质量聚类技术1150级1级2级G在四个数据集上的实验结果表明，我们的技术明显优于现有的技术。本文的结构如下。在第2节中，我们讨论了一些与我们提出的技术相关的背景研究。在第3节中，我们提出了我们提出的技术ModEx和Seed-Detective。实验结果和讨论在第4节中给出。论文的结论见第5节。2. 背景研究在这项研究中，我们讨论了数据集的一些基本属性。我们还讨论了Ex-Detective，因为它用于我们提出的一种称为ModEx的技术。2.1. 数据集的描述我们认为一个数据集D有n个记录D^fR1;R2。. ;Rng，和m数的属性A¼ fA1;A2.. . ;Am.数据集的属性可以是分类的和/或数值的。我们在表1中展示了一个玩具数据集，有15个记录和五个属性“年龄”，“婚姻状况”，“资格”，“职业”和“职业培训”。“年龄”是数值属性，其他是分类属性。“婚姻状况”、“资格”、“职业”和“职业培训”的域值分别为{单身、已婚}、{博士、硕士、学士}、{学术、工程师、医师}和{是、否}。数值属性“年龄”的上限值和下限值分别为65和30。因此，“年龄”的域是[30，65]。Ri表示数据集的第i条记录，Rij表示第i条记录的第j个属性值。例如，R5 ， 3 表 示 PhD ， PhD 是 第5 个 记录 R5 的 第 3 个 属性 （ 即Qualification）的值。2.2. 饰演Ex-DetectiveEx-Detective是一种基于决策树的聚类技术（Islam，2008;Islam and Brankovic，2011）。这是一个扩展侦探的版本（伊斯兰，2008年;伊斯兰和Brankovic，2005年）。前侦探的主要步骤如下。步骤1：为每个分类属性构建决策树。第二步：找到叶子的交点步骤3：执行K均值。2.2.1. 步骤1：为每个分类属性构建决策树Ex-Detective分别为每个分类属性构建决策树（DT），将每个分类属性视为类属性。它使用现有的决策树算法（如C4.5）来构建决策树（Quinlan，1993，1996）。为了演示这一步骤，我们在图1和图2中展示了两棵决策树，分别将职业和资格视为类属性。决策树的深度在图1中，记录集{R1 ， R5 ， R7 ， R11}， {R4 ，R6 ，R8 ， R13 ， R14} ，{R3 ，R10}，{R12，R15}和{R2，R9}分别属于叶1、叶2、叶3、叶4和叶5。同 样 ，在图。 2、成套记录{R4，R6，R8，R14}，{R2，R3，R9，R10，R11}，{R1，R5，R7}和{R12，R13，R15}分别属于叶6，叶7，叶8和叶9。在Ex-Detective中，数据挖掘机可以为不同的分类属性分配不同的权重（重要性级别），而不是将所有分类属性视为同等重要。0级1级2级图2一个将Qualification视为class属性的DT。表1玩具数据集。记录年龄婚姻状况资质认证占领专业R165结婚博士学术没有R230单个硕士工程师没有R345结婚硕士工程师没有R430单个学士医师是的R555结婚博士学术没有R635单个学士医师是的R760结婚博士学术没有R845单个学士医师是的R935单个硕士工程师是的R1042结婚硕士工程师没有R1132单个博士工程师没有R1235结婚硕士学术没有R1345单个学士学术是的R1435结婚学士医师没有R1535结婚硕士学术是的医师工程师学术LLeeaff66：：叶 7 ：硕士=4 博<=45人>45岁LLeeaff88：：第第第999页：：BBCC===111MS=2MS=2MS=2占领年龄BC=学士MS=硕士116M.A. Rahman等人12M有li个叶子，那么我们总共得到我J博学士硕士第十叶：学术= 3第11页： 物理学=4第十二页：学术=2Acad=学术工程师=工程师Phys=医师资格聚类分类属性Ai的权重用于修剪将属性Ai视为类属性的决策树Ti如果分类属性的权重是w i，决策树T i的深度是t i，则修剪树T 0 i的深度（t0i）是t0i<$iωwi。重量wi可以变化从0到1。如果分类属性Ai的权重Wi为1，则不存在Ti的修剪，即决策树Ti保持原样。然而，如果分类属性A的权重w我我为零，则Ex-Detective对Ti执行最大修剪，其中Ti仅包含一个叶节点。在这种情况下，数据集的所有记录都将属于叶节点。现在我们用例子来解释前侦探的修剪过程。假设一个数据挖掘器分别为属性Qualification（表1中的第3个属性）和Occupation（表1中的第4个属性）分配权重w3=0.6和w4=图中所示的树。 1是T4和图中所示的树。 2是T3。深处树 T4 和 T3 的 平 均 值 分 别 为 t4=4 和 t3¼ 修剪后的深度分 别 为t04<$$>t4ωw4<$4ω0：5<$$>2和t03<$$>t3ωw3<$3ω0：6<$1：8<$2。图1显示了T4的修剪树T04. 3.第三章。类似地，图3中示出了T3的修剪树T03。 四、 图 3记录集{R1，R5，R7，R11}，{R4，R6，R8，R13，R14}和{R2，R3，R9，R10，R12、R15}分别属于叶10、叶11和叶12。类似地，在图4中，记录集合{R4，R6，R8，R14}，{R2，R3，R9，R10，R11}和{R1，R5，R7，R7，R12，R13，R15}属于叶13、叶14和叶15。前侦探建立和修剪一组决策树considering每个类别属性作为类属性一个接一个。让我们考虑一下属性集的第一个z图4在Qualification属性上修剪的树。我们现在解释前侦探与T04和T03的交集过程。 属于T04的叶10的记录（见图3）可以与属于T0 3的叶13、叶14和叶15的记录相交（见图3）。 4）. 路口在属于叶10和叶15的记录之间产生一组新的记录，如叶10\叶15= {R1，R5，R7}所示。Ex-Detective将由两个叶子的交集产生的记录集视为初步聚类。例如，记录集{R1，R5，R7}被认为是一个初步的集群。属于叶11的记录可以与属于叶13、叶14和叶15的记录相交。类似地，属于叶12的记录可以与属于叶13、叶14和叶15的记录相交。在属于所有决策树的叶子的所有记录之间进行交集运算，以产生一组初步聚类。例如，如果我们有z个修剪的树T0c/fT01;T02;。 . . 其中树T0i但A¼fA;A. . . Ag是范畴属性，Qz其余的属性是数值的。也就是说，一组-cal attributes is A c¼ fA1;A2;. 一个zg。对于z个类别属性Ac/fA1;A2;.. . 一个zg，前侦探建立z。 决策树的 数 量 T c^fT1;T2. T ZG，在 哪里决策树Ti被构建为将Ai考虑为类属性。如果权重对的分类属性w c¼ fw1;w2;.. . wzg，前侦探基于wc中的权重修剪Tc中的所有树。修剪过程生成z个修剪的树T01;T02;. .T0zg。2.2.2. 第二步：找到叶子的交点Ex-Detective接下来在属于决策树叶子如果p是数字，而q是T0时的叶数我可能的交叉点。每个交叉点内的记录被认为是一个初步聚类。Ex-Detective接下来对每个初步聚类应用K-Means以产生最终聚类。2.2.3. 步骤3：执行K均值如果数据集中存在任何数值属性，则Ex-Detective执行K-Means（Huang，1997; Tan等人，2005）对属于在步骤2. 在应用K均值时，仅考虑数值属性值。然而，最初的研究（Islam，2008; Islam和Brankovic，2011）没有明确讨论定义集群数量的过程I j将是从树T0和dT0 的 p ω q 个 交 叉 点。对于K-Means应用于Prelimi的记录nary集群例如，从T04（见图 3）和T03（见图。 4）是9，因为每棵树的叶子数等于3。图3Occupation属性上的修剪树。K-Means一直持续到满足终止条件。K-Means中有两个终止条件。第一个终止条件是K-Means的两次连续迭代中目标函数值之间的绝对差小于用户定义的阈值（e）。用户定义的最大迭代次数被认为是第二终止条件。3. 我们提出的聚类技术3.1. Modified Ex-Detective（ModEx）我们现在讨论一些与前侦探有关的问题，然后提出一些修改如下。医师工程师学术第十三页：第14页：硕士=4博第十五页：博士=3BC = 1占领BC=学士MS=硕士li数量两种新的高质量聚类技术117ð Þ ð Þ83.1.1. 前侦探的局限性在最初的研究中（Islam，2008年; Islam和Brankovic，2011年），数值属性值在应用K-Means之前没有归一化。数字的标准化如下每个属性的标准化进行considering其最小值和最大值。两个不同的属性使用两对不同的最小值和最大值来规范属于属性的值cal属性值在K均值中具有很大的影响（Kim等人，R0¼Rij-minIJð1Þ2006年; Visalakshi和Thangavel，2009年）。 让我们解释一下如表2所示，使用三个记录（R1、R2和R3）和两个数值属性（Salary和Age）进行归一化的效果。在R1和R2中，Salary的值相同（50，000），但在R2中，Age的值是R1中Age值的两倍。此外，在R1和R3中，的年龄等于（25），在R3中，Salary的值略大于R1的Salary的值。R1 和 R2 之 间 的 城 市 街 区 距 离 （ Malik 和 Baharudin ，2013）为25，R1和R3之间的距离为1000。请注意，虽然R2中的Age值是R1中Age值的两倍，但它们之间的距离小于R1和R3之间的距离。这是由于Salary和Age两个属性的域大小不同。由于Salary的域大小非常大，因此属性的微小变化会导致巨大的距离，而年龄的大变化不会导致大的距离。因 此 ， 重要 的 是 在 应用 K-Means （ Kim 等 人 ， 2006 年 ;Visalakshi和Thangavel，2009年）。我们还观察到，在交叉过程后，前侦探可以产生大量的小尺寸的集群。属于小规模集群的记录可能没有足够的支持来被认为是重要的集群，并且可能不会向数据挖掘器揭示感兴趣的模式。属于小规模集群的记录也具有与其他合适集群合并的趋势（Maqbool和Babri，2006; Noordam等人，2002），表明它们在揭示有趣模式方面的局限性。最初的研究（Islam，2008; Islam和Brankovic，2011）也没有明确讨论定义K均值聚类数量的过程，该过程应用于初步聚类的记录。然而，这是聚类技术的操作3.1.2. 现代化设施为了解决前侦探的局限性，我们提出了以下三个修改。3.1.2.1. 修改1：数值属性的标准化。我们建议属于属性的数值属性值应在0-1的范围内规范化。规范化的目的是给予相同的强调每个数值属性，而不管他们的实际域大小。在对数值型属性应用K-Means算法之前，需要进行归一化。如果R ij是第i条记录的第j个属性值，min和max是第j个属性的最小和最大域值;则归一化值R0ij 被计算为最大值-最小值3.1.2.2. 修改2：合并。我们意识到，前侦探可能会产生一些非常小的初步集群。因此，我们建议将一个小规模的初步聚类（在第2.2节的步骤2中获得）的记录与其他合适的聚类合并。对于合并，首先我们从步骤2中产生的所有初步聚类的集合中找到最小的聚类。如果最小集群中的记录数小于用户定义的阈值h，则我们将最小集群的所有记录与其他合适的集群合并，如下所示。属于最小聚类Ci的记录Ri与另一个聚类Ck合并，其中Ri与Ck的种子Sk具有最小距离。设Ri是最小聚类的记录，Sk是第k个聚类（Ck）的种子/中心，然后我们合并Ri与C k，如果dist Ri;S k7叶子1：一个一一叶子2：一名叶三：a11C1C2C3第35页年龄的值然后被分成6个相等大小的类别; 30的不同的类别可以具有不同数量的记录。当类属性最初是数值属性时，分类仅用于构建决策树。所有其他非类数值属性都以其原始数值形式考虑。如果一个数据集有m个属性AA1;A2.. . Am然后种子侦探建立m个决策树T1;T2. 其中，决策树Ti是将属性Ai考虑为类属性而构建的。 如果属性的权重是w^fwi;w2... 树的深度是t1;t2. 然后，种子检测器修剪T中的所有树，并产生T01/4，T02;. . 去吧。修剪后的树T0i的深度定义为t0itiωwi，其中wi是权重i是树的深度。属性Ai的权重wi可以在0到1之间变化。如果权重w i如 果 属性A i的值为1，则不存在T i的修剪，即修剪后的树T0i与Ti相同。但是，如果属性的权重wi但Ai为零，则种子侦探执行最大Ti 的 剪 枝，即修剪后的树T0i只有一个叶节点，它包含数据集的所有记录。在决策树建立之后，Seed-Detective接下来在属于树的叶子的记录之间执行交集操作，并产生一组初步聚类。Seed-Detective中的交集操作与ModEx中的操作相同。为了演示交集运算，我们使用了一个具有五个属性A1，A2，A3，A4和A5的数据集。属性A1、A2和A3是分类的，而属性A4和A5是数值的。域图6属性A1上的DT。属于叶1，叶2和叶3分别形成集群C1，C2和C3。聚类C1、C2和C3如图7所示，其中的点表示记录。 注意，在图7中，记录是在二维空间中显示的，这只是为了演示的目的，在这种情况下，实际的维度（属性的数量）是5。此外，用于将记录划分为不同聚类的曲线是不真实的。它们也仅用于演示目的。类似地，我们构建另一个决策树，将属性A2视为类属性，如图所示在图8中。属于叶4、叶5和叶6的记录形成我们在图9中呈现的簇C4、C5和C6。然后，我们以与ModEx相同的方式将图7的聚类C1、C2和C3与图9的聚类C4、C5和C6交集运算产生另一组初步的簇C，C，C，C得双曲余切值.得双曲余切值.和C3，如图10所示。属性A1、A2和A3的值是7 8 910 11 12 1a11;a12;a13;a21;a22;a23和a31;a32。让我们假设我们建立一个决策树考虑属性如图6所示，将A1作为类属性。这棵树有三片叶子，叶子1，叶子2和叶子3。树的每个叶包含一组具有相同（在同构叶的情况下）或相似（在异构叶的情况下）类值的记录。具有相同/相似类值的记录由于类值的代表能力而被认为是相似的。通常，类值比任何其他非类值都更有能力表示记录。例如，如果我们将一旦我们知道病人的类值是癌症，我们就得到了病人的图像。类似地，通过知道另一个病人的类值为Fever，我们也得到了病人的图像。然而，如果我们得知这两名患者的另一个属性值，比如由于属于叶子的记录具有相同/相似的类值，因此它们可以被认为是相似的，从而导致聚类。属于叶的记录也共享从根到叶的路径中测试的所有分类属性的相同值。这些记录还共享路径中测试的所有数值属性的相似数值（落在同一范围内）。这使得记录的相似性论证更加有力。例如，图6中属于叶2的记录被认为是一个簇，因为它们具有相同的类值a13、A467和A3 1/4a31。让我们假设，我们 观察 的 的 路口 操作 种子-侦探可能会产生太多的小集群。例如，图10中的C12。似乎是一个小规模的集群。在第3.1.1节中讨论了此类小集群的局限性。因此，在Seed-Detective中，我们将属于一个小集群的记录与其他合适的集群合并。属于小集群的记录通过使用ModEx的修改2中讨论的过程与其他合适的集群合并。在合并操作中，我们需要计算一个小簇的记录与其他簇的种子之间的距离。在距离计算中，我们使用数值属性的归一化值。我们通过使用ModEx的Modification 1中讨论的过程来规范化属于0-1范围内的属性的数值属性值。然而，对于一个分类属性，在距离计算过程中，如果属于两个记录的两个分类值（属性）不同，则两个记录之间的属性距离被认为是1，否则为0（Huang，1997）。正常化的主要目的是图7基于属性A1的聚类.120M.A. Rahman等人JJXXXXð ÞJ JJ我异黄酮一j;ai;aj;ai;aa¼1a¼jArj1因此，很明显，为了最小化H，我们需要最大化类值q 1的比例。当H等于0时，叶子的所有记录都具有相同的类值。因此，初始聚类的种子对于重要属性也具有相同或相似的值，因为所有重要属性都被逐一视为类属性。由于我们对一个数值重要属性进行分类，因此属于一个簇的所有记录都具有属于相同或相似类别的值（对于该属性）。图8属性A上的DT2.数值属性是对所有属性给予同等重视，如ModEx的修改1中所讨论的3.2.2.2. 步骤2：计算初始聚类的种子。在步骤2中计算初步聚类的种子。种子中的数值属性的值是属于初步聚类的所有记录的属性的平均对于分类属性，在初步聚类的记录中具有最大频率的值被认为是分类属性的种子值初始种子选择的目的是最小化初始聚类的初始种子与属于初始聚类的记录之间的距离的平方误差（SSE）之和。3.2.2.3. 步骤3：将种子提供给K-Means以产生最终聚类。在步骤3中，我们首先使用ModEx的Modification 1中讨论的过程对数据集进行归一化。然后，我们将初步聚类的种子作为初始种子提供给K-Means以产生最终聚类。对于K-Means，我们认为聚类的数量等于初始种子的数量。K-Means一直持续到满足终止条件。在K均值中有两个终止条件.第一个终止条件是K-Means的两次连续迭代中目标函数值之间的绝对差小于用户定义的阈值（e）。用户定义的最大迭代次数被认为是第二终止条件。 如果k是簇的数目;Ri是第i个簇的第j个记录（Ci）和Si是第i个聚类的种子，则K均值的目标函数如下。KjCij相同的初始集群。因此，我们计算种子通过取一个数值的平均值，属性和具有类别的最高频率的值。上海证券交易所<$XX区;上海证券交易所2002年4月联系我们滑稽的属性K-Means也以同样的方式计算聚类的种子。在我们的方法中，种子选择的目的类似于K-Means中使用的目标函数。设Ci是第i个聚类，Si是第i个聚类的种子，k是聚类的数量，Ri是属于第i个聚类的第j个记录，并且dist（Ri，Si）是Ri和Si之间的距离。客观在应用K-Means的过程中，可以通过两种不同的方式之一来计算记录和聚类种子之间的距离。第一种方法是传统的方法，其中距离是基于所有属性计算的。 在第二种方式中，距离可以仅基于显著属性使用其显著性水平计算，如下所示：J JK-Means的函数如下。如下jArjmKjCij2JXwjR-Sjapanxdisturbance ;S联系我们在Seed-Detective中，我们首先构建一个决策树（如步骤1所述）。由于决策树算法，分布Rj;SiMWaa 1/4ð5ÞC4.5旨在最小化叶子中类值的熵，它试图增加属于叶子的所有记录中具有相同类值的可能性。设H是叶中类值的熵，|Q|是类属性的域大小，p q l是叶子中第l个类值的概率。H可以表示如下。jqjH¼ -p ql log2 p ql3l¼1这里，Rj;a是第j条记录的第a个属性值，Si;a是第j条记录的第a个属性值。a第i个簇的种子中的第i个属性，wa是用户定义的第th个属性的权重（显著性水平），Ar是数值属性的数量，m是数据集中属性的总数。因此，在K-Means过程中将忽略权重为零的属性。此外，具有高权重的属性在距离计算中比具有低权重的属性具有更大的影响力。请注意，C4C5C6C8颈7C9C12C10C11C13图9基于A2的聚类.图10基于A1和A2的初步聚类。>10<=10个一31一32第六叶：一名叶子4：一名叶五：一名22A3一个5上海证券交易所ð2Þ两种新的高质量聚类技术121在Eq. （5）可以与初始种子选择中使用的属性权重不同。对于初始种子选择，用户可能希望在低数量的属性上分配非零权重，以便在获得高质量种子的同时降低复杂度。然而，出于距离计算的目的，用户可能想要在许多重要属性上分配非零权重。我们认为在这种方法中，用户知道他的数据集，因此，可以识别重要的属性和猜测适当的权重。如果用户不知道重要的属性，他/她可以尝试不同的权重集并 探 索 结 果 ， 或 者 对 所 有 属 性 使 用 权 重 1 。 在 Seed-Detective中，在应用K-Means后，我们获得数据集的最终聚类。然后，我们去规范化属于一个集群的记录，以获得在一个集群中的原始记录。对于属于一个簇的记录，我们找到记录的索引（记录在数据集中的位置）。基于记录的索引，我们然后收集记录从原始数据集。为了更好地理解种子检测算法，我们在图1中给出了一个种子检测算法。 十一岁3.3. ModEx和Seed-Detective在ModEx中，属于初始聚类的记录没有任何机会移动到另一个初始聚类，即使它更适合另一个聚类。每个prelimi-nary集群只得到分为子集群由于appli-阳离子在每个集群分别。然而，在Seed-Detective中，初步聚类仅用于获得K-Means的初始种子，因此记录可以根据记录与聚类种子之间的距离移动到任何聚类中。例如，如果记录Rj与聚类Ci的种子Si具有最小距离，则该记录将被分配给聚类Ci。在K均值的各种迭代期间，Rj可以图11Seed-Detective的算法122M.A. Rahman等人如果Rj与另一个簇的种子具有最小距离，则改变其簇。预期其将产生较佳质量的最终群集。与ModEx不同，Seed-Detective没有任何随机性，因为它使用确定性的初始种子进行K均值操作。ModEx中的K-Means在每个初步聚类中使用随机初始种子。ModEx 和 Seed-Detective 之 间的 另一 个 重要 区 别是 ，Seed-Detective首先对数值属性进行分类，然后构建将分类的数值属性视为类属性的决策树，而ModEx不会对数值属性进行分类（离散化），也不会为数值属性构建决策树。因此，对于只有数值属性的数据集，ModEx的行为与K-Means相同。也就是说，ModEx的初始种子将被随机选择，与K均值相同。