第ｌ３卷第３４期２０１３年１２月 科学技术与工程 Ｖ０１．１３ Ｎｏ．３４ Ｄｅｅ．２０１３ １６７１—１８１５（２０１３）３４—１０３５９－０６ Ｓｃｉｅｎｃｅ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ ⑥２０１３ Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｒｇ． 数据挖掘中Ｋ－均值聚类算法的缺陷及 工作效率改进的实验研究 陈晓勇 顾 晖 彭志娟 （南通大学计算机科学与技术学院，南通２２６０１９） 摘要 均值聚类算法在当前提取数据挖掘的聚类分析方法中已经取得了一定的成就，为了进一步改进其在数据预处理 及神经网络结构中的应用，文中对算法进行了缺陷研究，主要做了以下几个方面的工作：对Ｋ一均值算法进行了思路及算法主 要流程分析；得出Ｋ－均值聚类算法存在简单、迅速、结果簇密集、簇与簇之间区别较为明显等优点；分析得出算法存在与处理 符号属性的数据不太适应、必须事先给出 值（想要生成的簇的个数）、对“噪声数据”以及孤立的点数据有较大影响、需要不 断计算更新调整后的新聚类中心等缺点。在实验验证中结果得出：聚类结果可知，选取不同的值初始值对聚类结果的影响很 小；如果聚类数据集迭代次数较多时，可以尝试着改变其数据的输入顺序；变动数据集的输入顺序，会直接影响聚类结果。实 验结果对于 均值算法的工作效率提高了，具有明显的参考价值，这一研究对于数据挖掘技术的改进具有一定的意义。 关键词 均值 聚类算法 噪声数据 文献标志码迭代 Ａ 工作效率 中图法分类号ＴＰ３９１．３； 数据挖掘（ｄａｔａ ｍｉｎｉｎｇ）是在大量的、不完整的、 及到人才培养，尤其是培养该工程领域的专门技术 人员，例如数据库管理人员。目前对于数据挖掘技 术的研究不再局限于理论研究，而是将其推向科技 产品的研究及相关技术的应用 Ｊ。随着我国经济 不规则的、不清晰的、随机的数据中挖掘出对于实 际应用有意义但之前并未在意的数据的非凡过程， 有时这一过程也被称之为已知的数据库中对知识 的发现（ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒｙ，ＫＤＤ）¨ 。原始的数 据类型多种多样，一般情况下有结构化数据类型和 不断发展，市场经济呈现多样化，新型产业不断崛 起，对数据挖掘技术的需求也越来越强烈，国内许 多软件企业已将目光投向数据挖掘这一领域，并尝 试着研法相关软件。目前，用于提取额数据挖掘中 有用信息的主要方法是聚类分析法，对于该方法的 研究已经取得了一定的成绩，尤其是对基于距离的 聚类分析。聚类同分类是相反的，前者是无监督的 学习，后者是有监督的学习，聚类主要是针对无标 记对象而言的，利用该分析方法将无标记的对象变 半结构化的数据类型，举例说明，数据库中的数据 即为结构化数据类型，而图像图形及网络互联网上 的数据类型为半结构化的类型。通常情况下，利用 桂南演绎等方法来发现新的知识，利用有关统计学 的数学和非数学方法将所挖掘的数据进行总结从 而得到对我们有实际意义的知识数据 Ｊ。在挖掘 数据并进行归纳总结的整个过程中，涉及到许多环 节，包括的学科内容也很广泛，在整个过程中，它主 得有意义 ’加Ｊ。聚类算法按照所使用的数据类型、 功能、聚类需求可以分为：基于划分的算法、基于层 要应用到了人工智能数学统计学，除此以外，还有 许多与数据有关的技术知识，在这个过程中还会涉 ２０１３年７月１２日收到，８月９日修改 南通大学自然科学 次的算法、基于密度的算法、基于模型的算法以及 基于网格的算法。目前，对于基于划分的 均值聚 类算法的研究已经取得了一定的成绩。该算法应 研究项目（１２Ｚ０３７）、南通大学校级自然科学类科研 用范围较广泛，在语音频率压缩及图像文本聚类中 均采用该算法，除此以外，在数据预处理及神经网 络结构的任务分解等领域该算法发挥重要作 基金交通运输专项项目（１ＯＺＪＯ０２）资助 第一作者简介：陈晓勇，男。硕士。Ｅ—ｍａｉｌ：ｎｔｕｃｈｅｎｘｙ＠１２６．ｃｏｍ。 科学技术与工程 １３卷 用¨ 。本文基于这一背景，对数据挖掘中Ｋ。均值 聚类算法的缺陷及工作效率改进进行了实验研究， 这一研究对于数据挖掘技术的改进具有一定的 意义。 １ －均值聚类算法的缺陷分析 １．１ Ｋ－均值聚类算法特点分析 １９６７年ＭａｃＱｕｅｅｎ首次提出了Ｋ．均值（Ｋ． ｍｅａｎｓ）算法，这一算法也被叫做 平均或 均值聚 类算法。该算法是到目前为止最为成功的一种聚 类方法。这种算法最显著的特点是将每个群集子 集内的所有数据样本的平均值作为集群的代表点， 该算法的主要思想是：通过采取一种反复的过程使 数据集被分成不同的类别，进而使用评价结果的聚 类性能标准的功能来实现的，从而使产生的每个群 集的紧凑及独立。 均值聚类算法主要适用于连续 性较好的聚类效应。 １．１．１ 均值聚类算法基本思想 Ｋ－均值算法的工作原理可以概括为：首先，要从 数据集中自动随机选择Ｋ个点作为初始聚类中心， 然后再计算各个样品同集群的距离，按照样品同聚 类中心的距离为标准进行分类。通过距离函数求 出每一个新生成的所要作聚类的数据对象的平均 距离值，所求出的平均距离值即为新的聚类中心， 如果连续两次计算所得到的聚类中心点相同，就表 明聚类准则函数收敛，即完成样本的调整。使用Ｋ 均值聚类算法时要注意，每完成一次对样本的分类 时，都要对其结果进行验证，以便检查其是否正确， 如果验证结果显示不正确，则需要对聚类进行调 整。当对所有样本完成调整后，接下来要对聚类中 心进行修改，开始下一轮的迭代过程。假设在某一 次迭代算法过程中，对所有样本的分类结果是正确 的，不需要再进行调整，聚类中心也没会出现有一 点任何变化，就表明该聚类函数收敛，Ｋ．均值聚类算 法到此结束。 １．１．２ Ｋ－均值聚类算法主要流程 Ｋ－均值聚类算法主要流程为：输入含有ｎ个数 据对象个数的数据库和所需要的簇的数目ｋ；输出ｋ 个簇。平方误差准则达到最小。算法描述：从／７，个 数据对象中自动随机的选择ｋ个对象来作为初始状 态的的聚类中心；根据各个聚类对象的均值（即每 个簇的中心点），来计算各个数据对象与所有中心 对象之间的距离，并以最短距离为依据要求对相应 的对象进行再一次的划分；重新计算各个发生了变 化的聚类的均值（即距离中心对象）；循环过程直至 各个聚类不再发生变化为止。算法步骤：为各个聚 类确定一个初始的聚类中心，这样就可以产生Ｋ个 初始聚类中心。按最小距离的原则把样本集中的 样本分配到最邻近聚类。把各聚类中的样本均值 规定为新的聚类中心。重复执行步骤２、３直至聚类 中心不再发生变化。结束过程，得到Ｋ个聚类。 １．２ Ｋ－均值聚类算法的缺陷分析 由上述Ｋ一均值聚类的特点可知，算法首先具有 以下主要优点： 均值聚类算法主要是针对于聚类 问题而出现的一种算法，该算法与其他算法相比较 简单，迅速。尤其对于数据集较大的聚类分析而 言，该算法的可伸缩和高效率得到进一步体现。因 为它的时间复杂度是０（ ｋ ），其中， 是所有对 象的个数；ｋ是所需要的簇的个数； 是迭代发生了 多少次。通常情况下有ｋ＜＜ｎ且 ＜＜／７，。当结果 簇是密集的，而且簇与簇之间的区别较为明显时， 它的效果比较好。 与此同时可以发现算法也存在以下缺陷： （１）只有在簇的平均值已经完成定义以后， 均值算法才能使用，但是这一要求又与处理符号属 性的数据不太适应。在Ｋ．均值算法中，第一步要自 动随机选取初始的聚类中心，以其为基础进行初始 划分；第二步就要对初始划分进行优化操作。这些 初始点的选择直接影响着聚类分析的结果，选择合 适的初始点能够有效确保聚类结果的准确性，否则 可能得到的结果不准确。这是该算法急需解决的 一个问题。目前主要采用遗传算法——ＧＡ来解决 这一问题。 （２）必须事先给出ｋ值（想要生成的簇的个 数）。初始值ｋ直接影响最终的结果。ｋ值不同，其 最终结果也不同。 均值算法要求在计算前给出ｋ 值，但ｋ值的选择要考虑多种因素，因而确定十分困 难。事实上，一般情况下是不能够提前确定给定的 ３４期 陈晓勇，等：数据挖掘中 均值聚类算法的缺陷及 作效率改进的实验研究 数据集成划分成多少个类别才最适合这个数据集。 这也是该算法急需解决的一个问题。针对这一问 一不断地计算更新调整后的新的聚类中心。基于这 点可知当数据巨大时，利用该算法所要花费的时 间较长，操作较困难，因而要时刻考虑到该算法的 时间及复杂性进行调整以满足各项要求。 题目前有些方法可以对ｋ值进行初步确定：一种是 根据方差分析理论结合应用混合Ｆ统计量来求得 最合适分类数，通过模糊划分熵的方法进一步验证 结果是否合理；另一种是全协方差矩阵的ＲＰＣＬ算 ２ －均值聚类算法工作效率改进的实验研究 ２．１ 实验一 法，将不合理的训练数据的类逐步删除；还有一种 是次胜者受罚的学习竞争规从而自动决定类的合 理数日。 本次试验所使用的数据集是从数据下载的 ｅ－ｆａｔＳＯ０．１０．ｔｘｔ数据集，此次所选用的数据集中包括 １５０个数据，目的主要是考察不同初始点对 均值 聚类算法最终聚类结果的影响情况。图ｌ为本次实 验一的过程。 （３）该算法对“噪声数据”以及孤立的点数据都 可能对平均值产生较大的影响。 （４）通过观察Ｋ．均值算法流程可以发现，使用 一均值聚类算法时要不断地对样本进行分类，还要 ａ）初始点为第１、２、３序号的聚类图 ｃ）初始点为第１（Ｘ）、１０１、１０２序 的聚类 （ｄ）初始点．工Ｊ第１ １Ｉ １¨¨序寸的聚类 １图１实验一过程 分析：通过聚类结果可知，选取不同的初始值 对聚类结果的影响很小。通过对比如１（ａ）可知，图 １为初始点是序号１、２、３的聚类图，其共迭代５次， 图１（ｂ）为初始点是序号４、５、６的聚类图，其共迭代 １０３６２ 科学技术与工程 ｌ３卷 ７次，而且观察两图发现其聚类结果输出顺序发生 了变化，除此以外还有极少数据发生变化，无其他 不同点；通过对比如图１（ｃ）和１（ｂ）可知，图１（ｃ） ２．２实验二 此次实验主要是验证数据输入顺序对聚类结 果的影响，此次使用的数据集仍然延续实验一的数 据集，只是将其数据顺序进行调换，将前７５个数据 同后７５个数据进行调换，本次试验只是验证数据集 输入顺序的改变对聚类结果的影响，所以只选取两 种初始值进行验证，与实验一进行对比。 为初始点是序号１００、１０１、１０２的聚类图其迭代次数 为９次，较图１（ｂ）相比有所增加，除此以外数据聚 类的输出顺序有所改变，无其他不同点；图１（ａ）、图 １（ｂ）、图ｌ（ｃ）分别为序号为ｌ，２，３、序号为４，５，６、 序号为１００，１０１，１０２的聚类图，图１（ｄ）为序号为１、 分析：此次所使用的数据集同实验一相同，只 是将该数据集的前７５个数据和后７５个数据进行调 换。将２与图ｌ（ａ），图１（ｂ）与图２的对比结果可 知，数据的输入顺序有所改变，将使得其聚类结果 有很大的不同，除此以外，还会使得迭代次数有所 １０、１００的聚类图，此次所选择的初始值为不连续的 三个数据，通过该图可以观察到，其同图１（ａ）相比 只有输出顺序有所改变，其他并无不同。 结论：对比分析ｐ１｛个聚类结果 ，叮以发现虽 然它们所选取的初始点小同，但是其结果并没有较 大的区别，只是输｝ｎ顺序及迭代次数略有不同，其 中选取最前面的三个数据和后面某一不连续的数 增加。这表明数据输入顺序直接影响着Ｋ－均值算 法的迭代次数。另外，再对比图２的２个结果，虽然 两次的聚类结果是一样的，但是迭代的次数当选取 第４、５、６个数据为初始点比选取第１、２、３个数据为 初始点迭代次数有所增加，聚类结果的输出顺序也 有所改变，同时也验证了实验一的结论。 据为初始点时迭代次数最少。实验表明：初始值不 同对Ｋ．均值算法的迭代次数有一定的影响，因而初 始值选取合理可以有效减少迭代次数，从而提高算 法效率，减少工作时问，对于实际应用具有重要意 义。因此，从这此实验得到的结论是： 结论：数据的输入顺序不同直接影响着 一均值 算法的聚类结果，尤其是对迭代次数的影响。因而 要提高算法效率可以尝试着改变数据集的顺序。 虽然本次试验中改变输入顺序使得迭代次数有所 增加，不过再次改变输入顺序可能使迭代次数有所 （１）优先考虑需用数据最开始的连续的点作为 初始点，从而有效减少迭代次数完成聚类。 （２）改变Ｋ一均值算法的初始点可以影响数据集 的迭代次数，对聚类结果影响不大。 减少。这些都说明Ｋ一均值算法对数据输入顺序特 别敏感，因此得到的结论如下： （３）每次初始值的改变也会造成数据输出顺序 的改变，即使是在聚类结果不变的情况下。 （１）如果聚类数据集迭代次数较多时，可以尝 （ ｐｌｌｌｐｌ２Ｉｐｌ：￣Ｊ作为初始聚类结果 ｈ）ｐ［，ｌ，ｌｐ［５］ｐｔＣｑ个数据作为初始聚类结粜 图２对比实验 ３４期 陈晓勇，等：数据挖掘中 一均值聚类算法的缺陷及工作效率改进的实验研究 试着改变其数据的输入顺序。 （２）不要轻易变动数据集的输入顺序，否则可 能直接影响聚类结果。 ２．３实验结果探讨 在了解 均值算法的基本思想及主要流程的 基础上，影响Ｋ．均值聚类算法结果的两个因素—— 初始点的选择及数据输入顺序，进行验证。针对这 两个因素，分别进行了两个实验：实验一主要验证 初始点的选择对聚类结果的影响，通过观察图１可 知，选取不同的初始点使得其迭代次数不同，聚类 输出顺序不同，对于聚类结果无明显影响；实验二 主要是验证数据输入顺序不同对聚类结果的影响， 将实验二中的结果同实验一中的结果进行对比，发 现其对聚类结果的影响较明显，除此其将改变迭代 次数。这两个实验为提高 一∞ 舳 ∞ ∞ 均值算法的工作效率 加 ０ 提高了理论参考。 ２．４算法改进对比 从ｃ—ｆａｔＳＯ０—１０．ｔｘｔ数据集上选取４个数据集 Ｉｒｉｓ，Ｗｉｎｅ，Ｓｏｙｂｅａｎ（ｓｍａｌ１），Ｖｅｈｉｃｌｅ进行聚类分析。 ＵＣＩ数据集是一个专门用于测试机器学习、数据挖 掘算法的公共数据集。本文对４个数据集进行了改 进和未改进的对比实验，图３列出了本文算法对比。 从上述实验结果可以看出，改进算法对数据集Ｗｉｎｅ 和Ｓｏｙｂｅａｎ聚类后值有大幅的提高，提高了２０％左 右。而另外两个数据集Ｉｒｉｓ，Ｖｅｈｉｃｌｅ则有所降低。 Ｗｉｎｅ数据集有１７８个数据，分成３类，每个数据项 有１３个属性，各个属性的取值范围差距较大。Ａｌ— ｃｏｈｏｌ（属性１），Ｆｌａｖａｎｏｉｄｓ（属性８），Ｃｏｌｏｒ—ｉｎｔｅｎｓｉｔｙ （属性１１）这３个属性对分类最为重要，它们的取值 范围分别为：（０．３４～５．０８），（１．２８—１３），（１１．０３～ １４．８３），而对分类贡献不大的属性Ｐｒｏｌｉｎｅ（属性ｌ３） 的取值范围是（２７８～１ ６８０），在采用欧式距离计算 相似性时，属性Ｐｒｏｌｉｎｅ起到了绝对的作用，导致使 用欧氏距离聚类时严重降低了效果，而使用本文提 出的改进方法则明显地减弱Ｐｒｏｌｉｎｅ（属性１３）的影 响，提高了聚类的结果。 ３总结 本文在数据挖掘的基础上提出了Ｋ－均值聚类 Ｉｒｉｓ Ｗｉｎｅ Ｓｏｙｂｅａｎ Ｖｅｈｉｃｌｅ 图３算法改进对比 算法，对该算法的主要特点及其基本思想进行介 绍，并给出了其主要流程，重点分析该算法的优缺 点，及其所存在的问题，并对其存在的问题利用实 验进行验证，实验证明初始值的选取及数据的顺序 直接影响着聚类结果，从而对提高 均值聚类的运 算效率有一定的理论意义。 参考文献 １ 周 萍．改进的图像分割遗传 ．均值聚类算法．海军工程大学 学报，２００９；０３：７５—７８ ２陶新民，徐晶，杨立标，等．一种改进的粒子群和 均值混合 聚类算法．电子与信息学报，２０１０；０１：９２— ７ ３谢娟英，蒋帅，王春霞，等．一种改进的全局 ．均值聚类算法． 陕西师范大学学报（自然科学版），２０１０；０２：１８—２２ ４陈宗海，文锋，聂建斌，等．基于节点生长 均值聚类算法的 强化学习方法．计算机研究与发展，２００６；０４：６６１—６６６ ５ Ｎｇ Ａ Ｙ，Ｊｏｒｄａｎ Ｍ Ｉ，Ｗｅｉｓｓ Ｙ．Ｏｎ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ：ａｎａｌｙｓｉｓ ａｎｄ ａｎ ａｌｇｏｒｉｔｔｍｓ．Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒｌａ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ，２００１； １４（３）：８４９－－８５６ ６ Ｗｕ Ｋ Ｌ，Ｙａｎｇ Ｍ Ｓ．Ａｌｔｅｒｎａｔｉｖｅ ｆｕｚｚｙ ｃ－ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００２；３５（７）：２２６７－－２２７８ ７ Ｈａｍｍｅｒｌｙ Ｇ．Ｅｌｋａｎ Ｃ．Ａｌｔｅｒｎａｔｉｖｅｓ ｔｏ ｔｈｅ ｋ－ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ｆｉｎｄ ｂｅｔｔｅｒ ｃｌｕｓｔｅｒｉｎｇｓ．Ｐｒｏｃ ｏｆ ｔｈｅ １ｔｈ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌ— ｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ，２００２；１１（６）：６ｏ０—６Ｏ７ ８ Ａｌｓａｂｔｉ Ｋ，Ｒａｎｋａ Ｓ，Ｓｉｎｇｈ Ｋ．Ａｎ ｅｆｆｉｃｉｅｎｔ Ｋ－ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ— ｒｉｔｈｍ．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＰＰＳ／ＳＰＤＰ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ． Ｄａｔａ Ｍｉｎｉｎｇ，１９９７；１６（３）：３４—３９ ９李苏梅，韩国强．基于 均值聚类算法的图像区域分割方法． 计算机工程与应用，２００８；１６：１６３—１６７ １Ｏ刘靖明，韩丽川，侯立文．基于粒子群的 均值聚类算法．系 统工程理论与实践，２００５；０６：５４—５８ １１樊宁． 均值聚类算法在银行客户细分中的研究．计算机仿 真，２０１ １；０３：３６９—３７２ １２关云鸿．改进 ．均值聚类算法在电信客户分类中的应用．计 算机仿真，２０１１；０８：１３８—１４０，１５２ （下转第１０３６８页） １０３６８ 科学技术与工程 １３卷 ２００３；１ ｂａｓｅｄ ｏｎ ａｎ ｅｆｆｅｃｔｉｖｅ ａｐｐｅａｒａｎｃｅ ｆｉｌｔｅｒ．ＩＥＥＥ Ｔｒａｎｓ Ｐａｔｔｅｒｎ Ａｎ￣ｙｓｉｓ ＩＥＥＥ Ｃｏｎｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００７；２９（９）：１６６１～１６６７ ６ Ｗｕ Ｙ，Ｙｕ Ｔ．Ｈｕａ Ｇ Ｔｒａｃｋｉｎｇ ａｐｐｅａｒａｎｃｅ ｗｉｔｈ ｏｃｃｌｕｓｉｏｎｓ．Ｐｒｏｃ ７８９—－７９５ Ｆｏｃｕｓ－ｅｖａｌｕａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｇｒａｄｉｅｎｔ Ｔｈｒｅｓｈｏｌｄ Ｃｏｕｎｔ ＺＨＡＮＧ Ｈｏｎｇ—ｆｅｉ ，ＺＨＡＮＧ Ｙａ．ｔａｏ ，ＬＩＵ Ｚｈｉ．ｇｕａｎｇ （Ａｒｍｙ Ａｖｉａｔｉｏｎ Ｒｅｐｒｅｓｅｎｔｉｖｅ Ｏｆｆｉｃｅ ｉｎ Ｌｕｏｙａｎｇ，ｌｕｏｙａｎｇ ４７１００９，Ｐ．Ｒ．Ｃｈｉｎａ； Ｃｈｉｎａ Ａｉｒｂｏｒｎｅ Ｍｉｓｓｉｌｅ Ａｃａｄｅｍｙ Ｍｅａｓｕｒｅｍｅｎｔ＆Ｃｏｎｔｒｏｌ Ｃｏ．Ｌｔｄ ．，Ｌｕｏｙａｎｇ ４７１００９，Ｐ．Ｒ．Ｃｈｉｎａ） ［Ａｂｓｔｒａｃｔ］ Ｔｈｅ ｍｅｔｈｏｄ ｏｆ ａｕｔｏ。ｆｏｃｕｓｉｎｇ ｆｏｒ ｇｒａｙ ｓｃａｌｅ ｄｉｇｉｔａｌ ｉｍａｇｅ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ａｓｐｅｃｔ ｏｆ ｄｉｇｉｔａｌ ｉｍａｇｉｎｇ ｓｙｓ． ．ｔｅｍ．Ａｎ ａｃｃｕｒａｔｅ ａｎｄ ｅｆｉｃｉｅｎｔｆ ｅｖａｌｕａｔｉｏｎ ｏｆ ｔｈｅ ｉｍａｇｅ ｒｅｓｏｌｕｔｉｏｎ ｉｓ ａ ｋｅｙ ｓｔｅｐＴｈｅｒｅ ａｒｅ ｓｏｍｅ ｅｘｉｓｔｉｎｇ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄｓ，ｂｕＩ ｔｈｅｒｅ ａｒｅ ｓｏｍｅ ｌｉｍｉｔａｔｉｏｎｓ ｂｅｃａｕｓｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ ｕｓｅｄｂｙ ｉｍａｇｅ ａｎａｌｙｓｉｓ ａｎｄ ｓｔａｔｉｓｔｉｃｓ． ． ｐｒｅｓｅｎｔ ａ ｎｅｗ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｒｅｇｉｏｎａｌ ｃｏｎｔｒａｓｔ，ｏｖｅｒｃｏｍｅｓ ｓｏｍｅ ｏｆ ｔｈｅｉｒ ｌｉｍｉｔａｔｉｏｎ．Ｔｈｅ ｍａｔｈｅｍａｔｉｃａ１ ｍｏｄｅｌ ｉｓ ｅｓｔａｂｌｉｓｈｅｄ ｉｎｄｉｖｉｄｕａｌｌｙ，ａｎｄ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ａｎｄ ａｎａｌｙｓｉｓ ａｒｅ ａｌｓｏ ｇｉｖｅｎＡｆｔｅｒ ａｎａｌｙｚｅｄ ｓｏｍｅ ｆｏｃｕｓ ｅｖａ１ｕ— ． ａｔｉｏｎ ｆｕｎｃｔｉｏｎｓ，ｃｏｎｃｌｕｄｅｄ ｔｈａｔ ｔｈｉｓ ｍｅｔｈｏｄ ｎｏｔ ｏｎｌｙ ｓａｔｉｓｉｆｅｄ ｔｈｅ ｂａｓｉｃ ｔａｃｔｉｃｓｂｕｔ ａｌｓｏ ｈａｓ ｈｉｇｈ ｓｅｎｓｉｔｉｖｉｔｙ．Ｉｔ ｃａｎ ，ｂｅ ｕｓｅｄ ｉｎ ｓｏｍｅ ｈｉｇｈ—ａｃｃｕｒａｃｙ ｅｑｕｉｐｍｅｎｔ． ［Ｋｅｙ ｗｏｒｄｓ］ ｇｒａｄｉｅｎｔ ｃｏｕｎｔ （上接第１０３６３页） ｄｅｆｉｎｉｔｉｏｎ ｅｖａｌｕａｔｅ ａｕｔｏ—ｆｏｃｕｓｉｎｇ ； ｉｍａｇｅ ａｎａｌｙｓｉｓ ） Ｒｅｓｅａｒｃｈ ｏｆ Ｅｘｐｅｒｉｍｅｎｔａｌ Ｄａｔａ Ｍｉｎｉｎｇ Ｋ－ｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ｔｏ Ｉｍｐｒｏｖｅ ｔｈｅ Ｅｆｉｃｉｅｎｃｙ ｏｆ Ｄｅｆｅｃｔ ｆＣＨＥＮ Ｘｉａｏ－ｙｏｎｇ，ＧＵ Ｈｕｉ，ＰＥＮＧ Ｚｈｉ－ｊｕａｎ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｔｏｎｇ ２２６０１９，Ｐ．Ｒ．Ｃｈｉｎａ） ［Ａｂｓｔｒａｃｔ］ Ｋ－ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｅｘｔｒａｃｔ ｔｈｅ ｃｕｒｒｅｎｔ ｄａｔａ ｍｉｎｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ ｍｅｔｈ０ｄ ｈａｓ ａｃｈｉｅｖｅｄ ｓｏｍｅ ｓｕｃｃｅｓｓ，ｉｎ ｏｒｄｅｒ ｔｏ ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅ ｔｈｅｉｒ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｄａｔａ ｐｒｅｐｒｏｃｅｓｓｉｎｇ ａｎｄ ｎｅｕｒａ１ ｎｅｔｗ０ｒｋ ｓｔｒｕｃｔｕｒｅ ｉｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｔｈｅ ｔｅｘｔ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｆｅｃｔ ｓｔｕｄｉｅｓ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｍａｊｏｒ ａｓｐｅｃｔｓ ｏｆ ｗ０ｒｋ．Ｔｈｅ ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｄｅａｓ ａｎｄ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｍａｉｎｌｙ ｐｒｏｃｅｓｓ ａｎａｌｙｓｉｓ；ｄｒａｗ Ｋ．ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｈｅｒｅ ｉｓ ａ ｓｉｍｐｌｅ，ｒａｐｉｄ，ｒｅｓｕｌｔ ｃｌｕｓｔｅｒｓ ｄｅｎｓｅ ｃｌｕｓｔｅｒｓ ａｎｄ ｃｌｕｓｔｅｒｓ ｓｕｃｈ ａｓ ｔｈｅ ｍｏｒｅ ｏｂｖｉｏｕｓ ｄｉｆｆｅｒｅｎｃｅｓ ｂｅｔｗｅｅｎ ｂｅｎｅｆｉｔｓ： ａｎａｌｙｓｉｓ ａｎｄ ｐｒｏｃｅｓｓｉｎｇ ａｌｇｏｒｉｔｈｍ ｈａｓ ｏｂｔａｉｎｅｄ ｄａｔａ ｓｙｍｂｏｌ ａｔｔｉｒｂｕｔｅｓ ａｒｅ ｎｏｔ ａｃｃｕｓｔｏｍｅｄ ｔｏｗｈｉｃｈ ｍｕｓｔ ｂｅ ｇｉｖｅｎ ，ｔｈｅ ｖａｌｕｅ ｏｆ ｋ（ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ｙｏｕ ｗａｎｔ ｔｏ ｇｅｎｅｒａｔｅ）． Ｏｎ ｔｈｅ”ｎｏｉｓｅ ｄａｔａ”ａｓ ｗｅｌｌ ａｓ ｉｓｏｌａｔｅｄ Ｄｏｉｎｔ ｄａｔａ ｈａｖｅ ａ ｇｒｅａｔｅｒ ｉｍｐａｃｔ，ｎｅｅｄ ｔｏ ｃｏｎｓｔａｎｔｌｙ ｕｐｄａｔｅｄ ａｄｊｕｓｔｉｎｇ ｔｈｅ ｎｅｗ ｃｏｍｐｕｔｉｎｇ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ ａｎｄ ｏｔｈｅｒ ｓｈｏｒｔｃｏｍｉｎｇｓ． Ｔｈｅ ｒｅｓｕｌｔｓ ｏｂｔａｉｎｅｄ ｉｎ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｖｅｒｉｉｆｃａｔｉｏｎ：ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓｓｅｌｅｃｔ ａ ｄｉｆｆｅｒｅｎｔ ｖａ１ｕｅ ０ｆ ｔｈｅ ｉｎｉｔｉａ１ ｖａｌｕｅ ，ｈａｓ ｌｉｔｔｌｅ ｅｆｆｅｃｔ ｏｎ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｈｓ；ｃｌｕｓｔｅｒｉｎｇ ｄａｔａ ｓｅｔ ｉｆ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｉｔｅｒａｔｉｏｎｓ ｉｓ ｌａｒｇｅ．ｙｏｕ ｃａｎ ｔｒｙ ｔｏ ｃｈａｎｇｅ ｉｔｓ ｄａｔａ ｉｎｐｕｔ ｏｒｄｅｒ．Ｃｈａｎｇｅ ｄａｔａ ｓｅｔ ｔｈｅ ｉｎｐｕｔ ｓｅｑｕｅｎｃｅｉｔ ｗｉｌｌ ｄｉｒｅｃｔｌｙ ａｆｆｅｃｔ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕＩｔｓ．Ｔｈｅ ，ｒｅｓｕｈｓ ｏｒｆ ｔｈｅ Ｋ－ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｗｏｒｋ ｅｆｉｃｉｆｅｎｃｙ ｈａｓ ｏｂｖｉｏｕｓ ｒｅｆｅｒｅｎｃｅ ｖａｌｕｅｔｈｉｓ ｓｔｕｄｙ ｆｏｒ ｔｈｅ ｉｍｐｒｅｖｅｍｅｎｔ ｏｆ ｄａｔａ ，ｍｉｎｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｈａｓ ａ ｃｅｒｔａｉｎ ｓｉｇｎｉｆｉｃａｎｃｅ． ［Ｋｅｙ ｗｏｒｄｓ］ Ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｉｒｎｇ ａｌｇｏｒｉｔｈｍ ｎｏｉｓｅ ｄａｔａ ｉｔｅｒａｔｉｖｅ ｗｏｒｋ ｅｍｃｉｅｎｃｖ