第２７卷第１２期 计算机应用研究 Ｖｏ１．２７ Ｎｏ．１２ ２０１０年１２月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｄｅｃ．２０１０ 一种高 效的Ｋ－ｍｅｄｏｉｄｓ聚类算法 夏宁霞 ，苏一丹 ，覃希 （１．广西大学计算机与电子信息学院，南宁５３０００４；２．广西工学院计算机工程系，广西柳州５４５００６） 摘要：针对Ｋ—ｍｅｄｏｉｄｓ算法初始中心点选择敏感、大数据集聚类应用中性能低下等缺点，提出一个基于初始中 心微调与增量中心候选集的改进Ｋ．ｍｅｄｏｉｄｓ算法。新算法以微调方式优化初始中心，以中心候选集逐步扩展的 方式来降低中心轮换的计算复杂性。实验结果表明，相对于传统的Ｋ—ｍｅｄｏｉｄｓ算法，新算法可以提高聚类质量， 有效缩短计算时间。 关键词：聚类；Ｋ—ｍｅｄｏｉｄｓ算法；中心微调；增量候选 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１０）１２－４５１７—０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１０．１２．０３５ Ｅｆｆｉｃｉｅｎｔ Ｋ—ｍｅｄｏｉｄｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＸＩＡ Ｎｉｎｇ－ｘｉａ ．ＳＵ Ｙｉ—ｄａｎ ．ＱＩＮ Ｘｉ ， （１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ＆Ｅｌｅｃｔｒｏｎｉｃ Ｉｎｆｏｒｍａｔｉｏｎ，Ｇ∞， Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ ５３０００４，Ｃｈｉｎａ；２．Ｄｅｐｔ．ｏｆ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｌｉｕｚｈｏｕ Ｇｕａｎｇｘｉ ５４５００６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄｕｅ ｔｏ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｓｅｎｓｉｔｉｖｉｔｙ ｔｏ ｔｈｅ ｉｎｉｔｉａｌ ｓｅｌｅｃｔｉｏｎ ｏｆ ｔｈｅ ｍｅｄｏｉｄｓ ａｎｄ ｐｏｏｒ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｌａｒｇｅ ｄａｔａ ｓｅｔ ｐｒｏｃｅｓｓｉｎｇ ｉｎ ｔｈｅ Ｋ—ｍｅｄｏｉｄｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａｎ ｉｍｐｒｏｖｅｄ Ｋ—ｍｅｄｏｉｄｓ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａ ｆｉｎｅ—ｔｕｎｅｄ ｏｆ ｉｎｉｔｉａｌ ｍｅｄｏｉｄｓ ａｎｄ ａｎ ｉｎｃｒｅｍｅｎｔｌａ ｃａｎｄｉｄａｔｅ ｓｅｔ ｏｆ ｍｅｄｏｉｄｓ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚｅｄ ｉｎｉｔｉａｌ ｍｅｄｏｉｄｓ ｂｙ ｆｉｎｅ—ｔｕ— ｎｉｎｇ ａｎｄ ｒｅｄｕｃｅｄ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｍｅｄｏｉｄｓ ｓｕｂｓｔｉｔｕｔｉｏｎ ｔｈｒｏｕｇｈ ｅｘｐａｎｄｉｎｇ ｍｅｄｏｉｄｓ ｃａｎｄｉｄａｔｅ ｓｅｔ ｇｒａｄｕａｌｌｙ．Ｅｘｐｅｎ－ ｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ ｃａｎ ｉｍｐｒｏｖｅ ｃｌｕｓｔｅｒｉｎｇ ｑｕａｌｉｔｙ ａｎｄ ｓｉｇｎｉｉｆｃａｎｔｌｙ ｓｈｏ￣ｅｎ ｔｈｅ ｔｉｍｅ ｉｎ ｃａｌｃｕｌａｔｉｏｎ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ Ｋ—ｍｅｄｏｉｄｓ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；Ｋ・ｍｅｄｏｉｄｓ ａｌｇｏｒｉｔｈｍ；ｍｅｄｏｉｄ ｆｉｎｅ—ｔｕｎｉｎｇ；ｉｎｃｒｅｍｅｎｔａｌ ｃａｎｄｉｄａｔｅ 因此，针对Ｋ．ｍｅｄｏｉｄｓ算法在应用过程中存在的问题，结 ０引言 合目前对该算法的研究现状，本文提出了一个基于初始中心微 Ｋ—ｍｅｄｏｉｄｓ算法是一种基于划分的聚类算法，具有较强的 调与增量中心候选集的改进Ｋ—ｍｅｄｏｉｄｓ算法。它将在随机选 鲁棒性和较高的准确性，且相对于Ｋ．ｍｅａｎｓ算法有着明显的优 择初始中心并进行首次划分后在簇内进行中心调整，然后以中 势：ａ）在Ｋ．ｍｅａｎｓ算法中，用质心来代表簇，导致其对噪声和孤 心候选集逐一扩大的方式进行中心轮换，直至收敛。该算法不 立点数据非常敏感，而Ｋ—ｍｅｄｏｉｄｓ算法用簇中最靠近中心的一 仅延续了原始Ｋ—ｍｅｄｏｉｄｓ算法的优势，保证了聚类效果的优越 个对象（即中心点）来代表该簇，可以有效地消除这种影 性与稳定性，同时算法效率也取得了较大程度的提高。 响 ．２ Ｊ。ｂ）Ｋ—ｍｅａｎｓ算法只有在簇的平均值被定义的情况下才 能使用 。然而，Ｋ－ｍｅｄｏｉｄｓ算法也存在一些缺点：一方面与 １改进的Ｋ—ｍｅｄｏｉｄｓ算法 Ｋ—ｍｅａｎｓ算法一样，它存在初始化敏感、聚类结果多样化的问 １．１ Ｋ—ｍｅｄｏｉｄｓ算法介绍与分析 题 ．４ ；另一方面，该算法在进行中心轮换时需遍历所有非中 心点，执行代价较高。鉴于此，目前对该算法的研究主要从优 Ｋ－ｍｅｄｏｉｄｓ算法有多种形式，其中ＰＡＭ（ｐａｒｔｉｔｉｏｎｉｎｇ ａｒｏｕｎｄ 化初始中心及中心替换策略两方面来进行改进。文献［５］通 ｍｅｄｏｉｄｓ，围绕中心点的划分）是最早提出的Ｋ一中心点算法之 一…过计算各对象的距离关系选择初始中心，并将中心替换的范围 。传统的Ｋ—ｍｅｄｏｉｄｓ算法（以ＰＡＭ为代表）的基本思 局限于簇内，其提高了算法的效率，但聚类效果却下降了。文 想¨ 是：首先为每个簇随意选择一个代表对象，剩余的对象 献［６］通过计算对象的密度信息来产生初始中心，然后执行传 根据其与代表对象的距离分配给最近的一个簇；然后反复地用 统的Ｋ－ｍｅｄｏｉｄｓ算法，取得了较好的聚类效果，但是其基于传 非代表对象来替代代表对象，以改进聚类的质量聚类结果的质 统算法的搜索策略使得该算法仍存在效率低的缺陷。其他的 量用一个代价函数来估算，该函数度量对象与其参照对象之问 改进方法如基于ＣＦ ｔｒｅｅ（ｃｌｕｓｔｅｒｉｎｇ ｆｅａｔｕｒｅ ｔｒｅｅ） 、基于ＭＡＭ 的平均相异度。 （ｍｅｔｉｒｃ ａｃｃｅｓｓ ｍｅｔｈｏｄｓ）［８ ３等，在改进算法性能的同时却因额外 聚类的目标是使簇内差异尽可能小，所以，为了判定一个 组件增加了算法的复杂性。 非代表对象ｏ 是否是当前一个代表对象Ｏ 的好的替代，对 收稿日期：２０１０—０５—２５；修回日期：２０１０—０６—２８ 作者简介：夏宁霞（１９８３ ），女，江西九江人，硕士研究生，主要研究方向为数据挖掘、Ｗｅｂ个性化标签推荐（ｋｌｘｎｘ＠１６３．ｃｏｍ）；苏一丹（１９６２一）， 男，教授，硕导，博士，主要研究方向为电子商务、Ｗｅｂ个性化挖掘、信息安全；覃希（１９８３一），女（壮族），广西南宁人，助教，硕士研究生，主要研究方 向为Ｗｅｂ标签挖掘． ・４５１８・ 计算机应用研究 第２７卷 于每一个非中心点对象Ｐ，每当重新分配发生时，平方一误差 ｋ Ｅ＝∑∑Ｉｐ—ｏ Ｉ 所产生的差别对代价函数有影响。替换的 ｉＰ ０ 总代价是所有非中心点对象所产生的代价之和。如果总代价 是负的，那么实际的平方一误差将会减小，即表明替换后的簇 内差异变小了，Ｏ；可以被ｏ 替代。如果总代价总是正的或 为零，表明算法不能产生一个有效的替换了，即此时算法收敛。 Ｋ—ｍｅｄｏｉｄｓ算法是基于使聚类准则函数最优的原则，采用 最接近于聚类中心的数据点作为类的中心以增强算法的鲁棒 输出：ｋ个簇，使得所有对象与其最近中心点的相异度总和最小。 １．选择、优化初始中心点并作初步划分 １．１．在ｎ个对象中随意选择ｋ个对象作为初始的中心点； １．２．以当前中心点对其他对象进行初始划分； １．３．在划分得的各簇中对中心点进行微调（按改进思路（ａ））； １．４．以当前中心点对其他对象进行划分； ２．执行增量中心候选集Ｋ－ｍｅｄｏｉｄｓ算法 令ｉ＝１； ｗｈｉｌｅ ＜＝ｋ ２．１．轮换中心并计算代价 ｒｅｐｅａｔ 性，对小的数据集合非常有效。但其在处理过程中还存在着以 下问题： ａ）传统的Ｋ—ｍｅｄｏｉｄｓ算法对初始中心是随机选择的，从而 导致聚类结果会随着初始点选择的变化而发生改变，即其对初 始中心敏感，且容易陷入局部最优解。所以要想获得较好的聚 类结果，可以从初始中心的选择上进行改进，降低随机性，以达 到优化的目的。 选择一个未选择过的中心点０； 生成替换０的候选集Ｃ（Ｃ由距０最近的ｉ个簇的所有非 中心对象构成）； ２．１．１．替换当前中心 ｒｅｐｅａｔ 在Ｃ中选择一个未选择过的非中心点Ｐ，计算用Ｐ代替 ０的代价并记录在Ｓ中； ｕｎｔｉｌｌ Ｃ中所有的非中心点都被选择过； ｂ）在中心替换策略上，原始的Ｋ—ｍｅｄｏｉｄｓ算法采取全局搜 ｕｎｔｉｌｌ所有的中心点都被选择过； ２．２．实施中心替换 ｉｆ ａｒｉｎ（Ｓ）＜０（设ｍｉｎ（Ｓ）表示代价集Ｓ中最小值） ２．２．１．用ｍｉｎ（Ｓ）对应的非中心点与中心点进行中心替 换，形成一个新的ｋ个中点的集合； ２．２．２．指派ｎ—ｋ个剩余的对象给离它最近的中心点所代 表的簇； ２．２．３．重新从２．１开始执行； ｅｌｓｅ ｉ＝ｉ＋１ 索的策略，即在中心替换时，考虑所有的非代表对象，根据相异 度函数重新划分，保证了聚类精度，但搜索效率却很低。然而， 针对这个问题，Ｐａｒｋ等人 提出将替换范围限制在簇内，具有 较高的搜索效率，但会遗漏一些可能的更优替换点，从而使聚 类精度得不到保证。因此，若需保证聚类精度的同时提高搜索 效率，可以结合它们的优势，先从簇内开始查找，采用逐步递增 的方式，最终将搜索范围扩大至所有非代表对象，以寻找最优 替换对象，保证聚类质量。 由上面的分析可知，改进的算法可从优化初始中心与改进 中心替换策略两方面进行，以此来提高聚类质量与算法的运行 效率。 ｅｎｄ ｉｆ ｅｎｄ ｗｈｉｌｅ ３．算法结束 对于本文改进的新算法，通过初始中心的调整，使得更多 的中心点极有可能就是最后聚类结果对应的中心点，可减少算 法迭代的次数，提高算法的执行效率。然而通过整体的调整， １．２新算法的改进思路 针对传统的Ｋ・ｍｅｄｏｉｄｓ算法存在的一系列问题，改进算法 将得到相对较优的初始中心，从一定程度上可提高聚类质量。 另外，从时间复杂度上分析，起决定作用的是算法流程２， 在这个阶段，新算法进行ｋ次搜索范围不同的中心轮换过程。 对一般情况，设聚类的数据点分布均匀，即每次对数据进行划 分后各簇中数据点的数量相当，约为（ｎ—ｋ）／ｋ。根据算法流 程，在进行第ｉ（ｉ＝１，２，…， ）轮替换时，将以ｉ个最近的簇组 成中心候选集，此时该候选集中数据点的数量为ｉ×（ｎ—ｋ）／ 。的具体改进思路如下： ａ）初始中心微调。在随机产生初始中心并将所有对象进 行首次划分后，对各初始中心在簇内进行微调，使之向较优的 中心偏移。具体方法为：以簇内各对象轮换为此簇中心，计算 该中心与其他所有对象的距离和，选取距离和最小的对象为此 簇微调后的中心。 在算法的２．１．１中，当一一以该候选集中的一个点替换当 前中心点，并对剩余的ｎ—ｋ个非中心点进行簇划分时，算法的 时间复杂度为０（ｉ×（１１，一ｋ） ／ｋ）。所以，对所有的ｋ个中心点 进行替换与验证（算法流程２．１）的时间复杂度为０（ｉ（ｎ— ｂ）采用基于增量中心候选集的中心替换策略。对于一个 中心点，若要对其进行替换，一些较优的候选点最有可能出现 在该中心点附近，如同一簇内或其附近簇中的点。因此在搜索 新的中心点时可以只在这些范围内进行。具体替换方法为：中 心点替换分ｋ（ｋ为目标聚类数目，下同）次进行，每次进行替 ｋ） ）。而根据算法流程２，上述整个替换过程需进行ｋ次，则 ｋ 总的时间复杂度为Ｄ（∑ｉ（ｎ一 ） ），即０（ｋ（Ｊｉ｝＋１）（ｎ一后） ／ 换前首先生成中心候选集，候选集在迭代过程中不断扩大。设 当前为第ｉ次，在对上一次的ｋ个中心点进行替换时，其搜索 的范围设定为离该中心最近的ｉ个簇（包含被替换中心对应 簇）内的所有非中心对象。这样新中心的候选集就从１，２，…， ｋ个簇不断增大，形成增量中心的候选集，其最后的搜索范围 将扩大到所有的非中心点集，与原始算法相一致。 １．３新算法描述 ２）。根据文献［１］的比较准则，需计算每轮迭代的时间复杂 度，即平均时间复杂度。改进算法一共进行ｋ轮，则其平均时 间复杂度为０（（ｋ＋１）（ｎ—ｋ） ／２）。与传统算法的平均时间 复杂度０（ｋ（ｎ—ｋ） ）［１１比较，尽管没有数量级上的降低，但其 拥有更小的系数，因此其必然能节省执行时间，后面的实验将 对此进行验证。 ２实验 ２．１ 实验设计 根据改进思路，设计了一个新的Ｋ－ｍｅｄｏｉｄｓ算法，其算法 流程描述如下： 输入：结果簇的数目ｋ，包含ｎ个对象的数据库。 为了检验该算法的有效性，实验采用传统的Ｋ—ｍｅｄｏｉｄｓ算 第１２期 夏宁霞，等：一种高效的Ｋ—ｍｅｄｏｉｄｓ聚类算法 ・４５１９・ 法（简称ＫＭ）与本文改进的Ｋ—ｍｅｄｏｉｄｓ算法（简称ＩＫＭ）进行 对比实验，且在聚类性能和算法运行时间两方面进行比较。该 据集都能减少一半左右的运行时间。对于不同的数据集其算 法效率会受数据集类别数与样本数的影响，随着分类数与样本 数的增加，聚类所耗费的时间也大幅度增加，上面的实验对比 实验是在配置２．６９ ＧｔＩｚ Ｐｅｎｔｉｕｍ＠Ｅ５４００ ＣＰＵ、２ ＧＢ内存的Ｐｃ 机上进行，操作系统为Ｗｉｎｄｏｗｓ ＸＰ，程序用ＭＡＴＬＡＢ编写。 实验中聚类性能将采用ｆ－ｍｅａｓｕｒｅ值来衡量。ｆ－ｍｅａｓｕｒｅ组 合了信息检索中查准率（ｐｒｅｃｉｓｉｏｎ）与查全率（ｒｅｃａｌ１）的思想。 一情况可以对此验证。表３的实验结果与上文对算法时间复杂 度的分析相吻合，从另一个角度说明了ＩＫＭ的性能的稳定性。 表３算法效率的对比情况 个聚类 相对分类ｉ的ｐｒｅｃｉｓｉｏｎ和ｒｅｃａｌ１分别定义为Ｐ＝ｐｒｅ— ｃｉｓｉｏｎ（ｉ√）＝ ＩＬｔ ，Ｒ＝ｒｅｃａｌｌ（ｉ， ）＝ ＩＬ 。其中： 是在聚类 中 分类ｉ的数据；ｒｔ 是分类ｉ中所有对象的数目； 是聚类 中所 ●ＤＤ 有对象的数目。分类 的 ｍｅａｓｕｒｅ值定义为Ｆ 。对 分类ｉ而言，ｆ－ｍｅａｓｕｒｅ值最高的聚类用来表示分类ｉ的映射， 即该ｆ－ｍｅａｓｕｒｅ值表示分类ｉ的评判分值。就聚类结果而言，最 终的ｆ－ｍｅａｓｕｒｅ值由分类ｉ的加权平均／－ｍｅａｓｕｒｅ值得到：Ｆ＝ ∑（ｆｉＩ ｘＦ（ｉ）） ＿Ｌ— 。其中Ｉｉｌ为分类 中所有对象的数目。由此 可知，ｆ－ｍｅａｓｕｒｅ值越大，代表聚类结果越好，所获得的簇与原 类别越吻合。 ２．２实验结果与分析 实验的数据集采用ＵＣＩ公共数据库提供的四个数据 集¨ ，对于每个数据集合将数据标度到［一１，１］的范围内，所 有结果皆取１０次实验的平均值。测试的四个数据集如表１所示。 表１ 实验数据集基本情况 在四个数据集中，ｓｏｙｂｅａｎ与ＺＯＯ的数据类型包括二元变 量与分类变量，用海明距离…表示其数据对象进行相异度； ｗｉｎｅ与ｂｒｅａｓｔ ｃａｎｃｅｒ（ＢＣ）的数据类型为区间标度变量，用欧 几里德距离…度量数据库中对象之间的相异度。 表２是传统Ｋ．ｍｅｄｏｉｄｓ算法与本文算法在聚类效果上的 实验对比情况。 表２ ｆ－ｍｅａｓｕｒｅ值对比情况 由表２可知，新算法所获得的聚类结果的ｆ－ｍｅａｓｕｒｅ比原 始算法有所提升，表明改进后的算法不仅能够保证聚类的性 能，并能获得更好的聚类效果。特别针对类别数与属性个性相 对较多的ＺＯＯ数据集，其改进效果更加明显，而对于ｂｒｅａｓｔ ｃａｎｃｅｒ这种聚类效果较好的数据集能够维持原来的精度，验证 了新算法在聚类效果上的稳定性。 表３为两算法在运行时间上的对比情况。从表３可知，与 ＫＭ比较，ＩＫＭ在运行时间上表现出了明显的优势，对每一数 综上所述，改进的新算法在同样的实验环境下，既能保证 聚类性能又能大幅度提高算法效率。上述实验结果验证了新 算法的可行性与有效性。 ３结束语 在原始的Ｋ—ｍｅｄｏｉｄｓ算法进行聚类时，会遇到初始中心敏 感、聚类结果不稳定、执行效率低下等问题，为此本文提出了一 种高效的Ｋ—ｍｅｄｏｉｄｓ改进聚类算法。该算法通过调整初始中 心，并在中心替换操作过程中采用增量式思想逐步扩大搜索范 围。与原始聚类算法相比，本文算法不仅能改进聚类精度而且 能提高算法的效率，这对促进Ｋ—ｍｅｄｏｉｄｓ算法的发展与应用具 有积极的意义。 参考文献： ［１］ＨＡＮ Ｊｉａ—ｗｅｉ，ＫＡＭＢＥＲ Ｍ．数据挖掘概念与技术［Ｍ］．２版．北 京：机械工业出版社．２００８：２６３—２６６． ［２］ＣＨＥＮ Ｘｉｎ—ｑｕａｎ，ＰＥＮＧ Ｈａｎｇ，ＨＵ Ｊｉｎｇ—ｓｏｎｇ．Ｋ—ｍｅｄｏｉｄｓ ｓｕｂｓｔｉｔｕ— ｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ａｎｄ ａ ｎｅｗ ｃｌｕｓｔｅｒｉｎｇ ｖａｌｉｄｉｔｙ ｉｎｄｅｘ ｍｅｔｈｏｄ ［Ｃ］／／Ｐｍｃ ｏｆ ｔｈｅ ６ｔｈ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏ— ｍａｔｉｏｎ．２００６：５８９６—５９００． ［３］ＨＥ Ｚｅｎｇ—ｙｏｕ．Ｆａ￣ｈｅｓｔ—ｐｏｉｎｔ ｈｅｕｒｉｓｔｉｃ ｂａｓｅｄ ｉｎｉｔｉａｌｉｚａｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ Ｋ—ｍｏｄｅｓ ｃｌｕｓｔｅｒｉｎｇ［ＥＢ／ＯＬ］．（２００６—１０—１０）．ｈｔｔｐ：／／ａｒｘｉｖ．ｏｒｇ／ｆｔｐ／ ｃｓ／ｐａｐｅｒｓ／０６１０／０６１００４３．ｐｄｆ． ［４］宗瑜，金萍．ＢＫ－ｍｅａｎｓ：骨架初始解Ｋ—ｍ￣ａｆｌｓ［Ｊ］．计算机工程与 应用，２００９，４５（１４）：４９—５２． ［５］ＰＡＲＫ Ｈ Ｓ，ＪＵＮ Ｃ Ｈ．Ａ ｓｉｍｐｌｅ ａｎｄ ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｋ—ｍｅｄｏｉｄｓ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｅｘｐｅ￣Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２００９，３６（２）： ３３３６—３３４１． ［６］ＰＡＲＤＥＳＨＩ Ｂ，ＴＯＳＨＮＩＷＡＬ Ｄ．Ｉｍｐｒｏｖｅｄ Ｋ—ｍｅｄｏｉｄｓ ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｃｌｕｓｔｅｒ ｖａｌｉｄｉｔｙ ｉｎｄｅｘ ａｎｄ ｏｂｊｅｃｔ ｄｅｎｓｉｔｙ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｎｄ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ａｄｖａｎｃｅ Ｃｏｍｐｕｔｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ．２０１０：３７９— ３８４． ［７］ＧＡＯ Ｄａｎ—ｙａｎｇ，ＹＡＮＧ Ｂｉｎｇ—ｒｕ．Ａｎ ｉｍｐｒｏｖｅｄ Ｋ・ｍｅｄｏｉｄｓ ｃｌｕｓｔｅｒｉｎｇ ｌａｇｏｒｉｔｈｍ［Ｃ］／／Ｐｒｏｅ ｏｆ ｔｈｅ ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ａｕｔｏｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ（ＩＣＣＡＥ）．２０１０：１３２－１３５． ［８］ＢＡＲＩＯＮＩ Ｃ Ｎ Ｍ，ＲＡＺＥＮＴＥ Ｈ Ｌ，ＴＲＡＩＮＡ Ａ Ｊ Ｍ，ｅｔ ａ１．Ａｃｃｅｌｅｒａ— ｔｉｎｇ Ｋ－ｍｅｄｏｉｄ—ｂａｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｔｈｒｏｕｇｈ ｍｅｔｉｒｃ ａｃｃｅｓｓ ｍｅｔｈｏｄｓ［Ｊ］． Ｔｈｅ Ｊｏｕｍａｌ ｏｆ Ｓｙｓｔｅｍｓ ａｎｄ Ｓｏｆｔｗａｒｅ，２００８，８１（３）：３４３－３５５． ［９］ＰＡＲＴＹＫＡ Ｊ，ＫＨＡＮ Ｌ，ＴＨＵＲＡＩＳＩＮＧＨＡＭ Ｂ．Ｓｅｍａｎｔｉｃ ｓｃｈｅｍａ ｍａｔｃｈｉｎｇ ｗｉｔｈｏｕｔ ｓｈａｒｅｄ ｉｎｓｔａｎｃｅｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｒｆｅｒｅｎｅｅ ｏｎ Ｓｅｍａｎｔｉｃ Ｃｏｍｐｕｔｉｎｇ．２００９：２９７－３０２． ［１０］ＤａｔａＳｅｔ［ＥＢ／ＯＬ］．（２０１０）．ｈｔｔｐ：／／ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ／ｍｌ／ｄａｔａ－ ｓｅｔｓ．ｈｔｍ１．
