第３３卷第１３期ＶｏＬ３３计算机工程ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ２００７年７月Ｊｕｒｙ２００７Ｎｏ．１３改进的ｋ．平均聚类算法研究孙士保“，秦克云１（１西南交通大学智能控制开发ｌｍｂ，成都６１００３１ｔ２．河南科技大学电子信息工程学院，洛阳４７１００３）摘要：聚类算法的好坏直接影响聚类的效果。该文讨论ｒ经典的ｋ平均聚类算珐，说明了它存在不能很好地处理符号数据和对噪声与孤立点数据敏感等不足。提出了‘种基于加权改进的ｋ－平均聚类算｛击，克服了ｋ－平均聚类算法的缺点，并从理论上分析了该算祛的复杂度。实验证明，用该方法实现的数据聚类与传统的基于平均值的方法相比较，能有效提高数据聚类效果。关蝴：聚类算法；ｋ－平均；权；聚类数据挖掘ＲｅｓｅａｒｃｈｏｎＭｏｄｉｆｉｅｄｋ－ｍｅａｎｓＤａｔａＣｌｕｓｔｅｒＡｌｇｏｒｉｔｈｍＳＵＮＳｈｉｂａｏ“．ＱＩＮＫｅｙｕｎｌ（１ＩｎｔｅｌｌｉｇｅｎｔＣｏｎｔｒｏｌＤｅｖｅｌｏｐｍｅｎｔＣｅｎｔｅｒ，Ｓｏｕｒｈｗｅｓ｜ＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ６１００３１，２．ＥｌｅｃｔｒｏｎｉｃＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＣｏｌｌｅｇｅ，ＨｅｎａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｌｕｏｙａｎｇ４７１００３）ＩＡｂｓｔｒａｃｔ｜Ｔｈｅｍｅｍｏｄｏｆｄａｔａｃｌｕｓｔｅｒｉｎｇｗｉｌｌｉｎｆｌｕｅｎｃｅｔｈｅｅｆｆｅｃｔｏｆｃｌｕｓｔｅｒｉｎｇｄｉｒｅｃｔｌｙ．Ｔｈｅａｌｇｏｒｉｔｈｍｏｆｋ－ｔｎｅａｌ｜ｓｉｓｄｉｓｃｕｓｓｅｄ，ｔｈｅｓｈｏｒｔａｇｅｓｏｆｔｈｉｓａｌｇｏｔｉｔｈｍｓｕｃｈｉｔｎｏｔｄｅａｌｗｉｔｈｓｙｍｂｏｌｉｃｄａｍａｎｄｉｔｉｓｓｅｎｓｉｔｉｖｅｆｏｒｄａｔａｏｆｉｓｏｌａｔｉｏｎｐｏｉｎｔａｎｄｎｏｉｓｅｄｅｍｏｎｓｔｒａｔｅｄＡｍｏｄｉｆｉｅｄｋ—ｍｅａｎｓｉｓｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｅｘｐｅｒｉｍｅｍｓｃｌｕｓｔｅｒｉｎｇｗｅｉｇｈｔｓｉｓｐｕｔｆｏｒｗａｒｄ，ｉｔｃｈａｎｇｅｓｔｈｅｓｈｏｒｔｃｏｍｉｎｇｓｏｆｋ－ｍｅａｎｓＩｔｓｃｏｍｐｌｅｘｉｔｙａｎａｌｙｚｅｄｆｒｏｍｔｈｅｏｒｅＯｃＭＴｈｅｔｈｅｅｆｆｉｃｉｅｎｃｙｓｈｏｗｔｈａｔ．ｃｏｍｐａｒｅｄｗｉｔｈｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄｂａｓｅｄｍｅａｌ％，ｔｈｅｍｏｄｉｆｉｅｄｄａｔａｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｏｆｄａｔａ［ＫｅｙｗｏｒｄｓＩｃｌｕｓｔｅｒａｌｇｏｎｔｈｒａ；ｋ－ｍｅａｎｓ；ｗｅｉｇｈｔｓ；ｃｌｕｓｔｅｒｄａｔａｍｉｎｉｎｇ聚类是将物理或抽象对象的集合分组成为由类似的对象组成柏多个类的过程。它的目的是使得属于同一类别的个体之间的相似度尽可能大，而不丽类别的个体之间的相似度尽町能小。在机器学习领域。聚类是无指导学习的一个例子。聚类分析是知识发现的重要方法，在图像识别、信息检索、数据挖掘、统计学、机器学习、空问数据库、生物学以及市场营销等领域有着广泛的虚用”“ｌ。目前常用的聚类算法包括：以ｋ一平均算法（ｋ—Ｍｅａｎｓ）９１和ｋ一中心点算法（ｋ—Ｍｅｄｏｉｄ）［６１为代表的划分法；阻ＡＧＮＥＳｌ６Ｉ和ＤＩＡＮＡ埘为代表的层次聚粪算法ｉ以ＤＢＳＣＡＮ［７１和ＯＰＴＩＣＳｌ剐为代表的基于密度的方法；以ＳＴＩＮＧｌ９１为代表的基于嘲格的方法；以ＣＯＢＷＥＢｌ２１和ＳＯＭＤｏ］为代表的基于模型的方法；以顺序地比较一个集合中的对象””和ＯＬＡＰ数据立方体””为代表的基于孤立点的分析方法。这些方法中的大部分聚类算法都是面向数值属性，而针对符号属性的比较少‘１，２１ｏ现有许多改进的算法，如基于数据场改进的ＰＡＭ聚类算法””，基ＦＲｏｕｇｈ集的层次聚类算法”…。对于文献１１３冲基于数据场改进的ＰＡＭ聚类算ｊ击是一种较好的划分聚类算法，但在处理数据场势函数时的计算开销很大，很难应用到大型数据集中去；另外，它对数值属性效果较好，对符号属性基本上不能实现。本文给出一种基于加权改进的ｋ一平均聚类算法，这种新的划分聚类算法，不仅可以处理数值属性，而且可以处理符号属性，另外，当被挖掘的数据中存在孤立点数据和“噪声”时，这种算法的处理效果也非常好。１１．１ｋ－平均算法ｋ·平均算法的主要思想是试图对ｎ个对象给出ｋ个划分（ｋ＜ｎ），其中每个划分代表一个簇。首先，随机地选择ｋ个对象，每个对象初始地代表一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值，对数据库中的每个对象与每个簇的平均值相比较，把对象赋给最相似的某个簇。这个过程不断重复，直到簇中的对象都是“相似的”，面不同簇中的对象都是“相异的”，即准则函数收敛使平方误差函数值最小。１．２ｋ－平均算法盼扰靛点用ｋ一平均算法来聚类时，当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度是Ｏ（ｎｔｔ），其中，ｎ是所有对象的数Ｈ，ｋ是簇的数目，ｔ是迭代的次数。通常ｈｎ且ｆ“ｎ。这个算法经常以局部最优结束。但是，ｋ—ｆ均方法只有在簇的平均值被定义的情况下才能使用。这对于处理符号属性的数据不适用，它还要求用户必须事先给出女（要生成的簇的数日）值。另外，对于“噪声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。１．３ｋ·平均算法的过程算法：ｋ－平均。划分的ｋ一平均算祛基于簇中对象的甲均值。输入：簇的数目ｋ和包含ｎ个对象的数据库。基盒疆日：国家自然科学基金资助项目（６０４７４０２２）柞者臂介：孙士保：（１９７０－－），男，讲师、博士研究生，主研方向：智能信息处理；秦克云，博士、教授、博士生导师收藕刚■：２００６—０７·１０Ｅ－ｍａｉｌ：ｓｕｎｓｈｉｂａｏ＠１２６ｃｏｍｋ－平均算法的分析ｋ一平均（ｋ—Ｍｅａｎｓ）算法是一种基于划分方法的聚类算法，它是最早提出的较为经典的聚类算法之一。万方数据 输出：ｋ个簇，使平方误差准则是小。方法：（】）任意选择ｋ个对象作为初始的簇中心；（２）ｒｅｐｅａｔ；（３）根据簇中对象的平均值，特每个对象（重新）赋给最类似的簇；¨）更新簇的平均值，即计算每个簇中对象的平均值；蟾）ｕｎｔｉｌ不再发生变化，２基于加权改进的ｋ－平均算法２．１权时产生在含有ｎ个数据对象的数据库中，每个数据对象对于知识发现来说作用足不同的，为了区分这些相异之处，给每个数据对象赋予一个定量的值ｗ，即权。Ｗ，＝｝．，其Ｌ卜ｕ，己训…，ｗ：，÷∑：．ｄ（Ｘｉ，Ｘｊ），ｄ（Ｊ，，＾，）为，，与ｘ，之间的相异度，通常它是一个非负的数值，当‘与ｘ．之间越相似或接近，其值越接近０，反之就越大，ａ（ｘ。，Ｘ。）＝０。相异度有多种计算方法障】，不同的方法会有不同的聚类效果，这里采用常用的距离作为度量方式。权重越小，说明越相似或越接近；权重越大，说明差异性越大或越远。对于比较密集的数据点，它们距中心点的距离相近，权重是比较接近的，很容易聚类在一簇。而对于一个稳定的系统来说“噪声”和孤立点的数目不会太多，如果太多这个系统就没法使用，在本算法中“噪声”和孤立点的权重稍大，为了消除“噪声”和孤立点数据的影响，采用加权平均的方式来解决。当与别的数据点一起经加权平均后对整体影响远小于直接采用平均的方法。因此，这种权重的计算方法还是比较台理的。２．２基于加权改进的ｋ·平均算祛（ｋ－ＷＭｅａｎｓ）该算法的基本思想是对簇中每个对象计算加权平均值，将数据库中的每个对象（重新）赋给最类似的簇，反复进行这种操作，直到准则函数收敛即使平方误差的总和达到满意的程度。这显然是针对数值属性数据，而符号属性数据直接对簇中对象求权平均值，然后再对数据库中的每个对象重新调整。每一簇的加权平均值的计算方法是：ＡＷＭ，＝÷∑：；。ｗ，ｐ；，其中ＡＷＭ，（１≤，≤ｔ）表示簇Ｃ，的加权平均值（或权平均值）；ｔ是蘸Ｃ，中对象的个数，不同的簇ｔ值不同；Ｐ，是空间中的点，表示给定的簇Ｃ．中ｔ个数据对象之一；。是簇Ｃ，中数据对象的权重。准则函数（平方误差总和）Ｅ＝∑：：，∑舻，ｌｎ—ＡＷＭ，ｎ其中Ｐ．取簇Ｃ，中的每。个数据。ｋ－ＷＭｅａｎｓ算法：基于簇中对象的加权平均值或权平均值。输入：簇的数日ｋ和包含ｎ个对象的数据库。输出：ｔ个簇，使平方误差总和Ｅ最小。方法：（”任意选择ｋ个对象作为初始的簇ｔ私心；（２１ｒｅｐｅａｔ：（３）根据簇中对象的加权平均值（或权平均值），将每个对象ｒ重新）赋给最类似的簇；（４）更新簇的加权平均值（或权平均值），即计算每个簇中对象的加权平均值（或权平均值）；（５）ｕｎｔｉｌ不再发生变化。３与经典的ｋ－平均算法的比较本算法与经典的ｋ一平均聚类算法”相比，就是把经典算万 方数据法中的平均值变成了这里的加权平均值或权平均值，存计算加权平均值或权平均值时会增加一些时间开销，但它的处理能力却大大增强。它不仅能处理数值属性数措，还可以处理符号属性数据，对“噪声”和孤立点数据不怎么敏感，少量的该类数据不会对加权平均值（或权平均值）产生大的影响。该算法的复杂度和经典算法是一致的，也是Ｏ（ｎｋｔ），其中，ｎ是所有对象的数日，ｋ是簇的数日，ｔ是选代的次数。因此当ｋ“ｎ且ｔ“ｎ时对处理大数据集是可伸缩的和高效率的。另外，该算法和经典算法１样都需要事先估计簇的个数ｋ，如想得到最优解时必须试探不同的ｋ值。４实验结果本文采用ＵＣＩ［１５１提供的机器学习数据库中的部分数据对ｋ－ＷＭｅａｎｓ算法和ｋ－Ｍｅａｎｓ算法进行了测试。对于数值属性数据采用ｉｒｉｓ．ｔｈｙｒｏｉｄ－ｄｉｓｅａｓｅ和ｇｌａｓｓ３组数据集；符号属性数据采用ｂａｌｌｏｏｎ，ｓｏｙｂｅａｎ和ＺＯＯ３组数据集，按ｋ－ＷＭｅａｎｓ算法和ｋ－Ｍｅａｎｓ算法分别对它们进行聚类。在表１中给出了聚类的结果。其中，第１列是数据集的名称；第２、３、４列分别给出ｒ数据集的样品个数，决策值的个数，以及条件属性的个数；第５列和第６列是ｋ－ＷＭｅａｎｓ算法和ｋ－Ｍｅａｎｓ算法在数据集上对数据进行分类盼精确度。表１ｋ－ＷＭｃａｎｓ算法和ｋ－Ｍｅａｎｓ算法在ＵＣＩＩｔ据集上曲比较ＤａｔａＳｅｔ＃Ｉｎｓｔａｎｃｅ＃Ｃｏｎｃｅｐｔ＃Ａｔｔｄｂｕｔｅｋ－ＷＭｅｎｎｓｋ，ＭｅａｒｌｓＡｅｅｕｒａｃｙ／％Ａｃｃｕｒａｃｙ／％…ｓＪ５０３４９３Ｉ８９６Ｔｈｙｒｏｉｄ－ｄｉｓｅａｓｅ２１５３９５２９４３２１４９８８７６Ｂａｌｌｏｏｎ２０２４８８００３５９７３Ｚｏｏ１０ｌ７１６９５７０由表１可以看出ｋ－ＷＭｅａｎｓ对数据的聚类结果总体上优于ｋ－Ｍｅａｎｓ，同时它又能较好地聚类符号属性数据。５结束婿引进加权方法对现有的ｋ－Ｍｅａｎｓ算法进行了尝试性的改进，使其减小了孤立点和“噪声”的影响，实验证明了这种基于加权改进的ｋ叫；均聚类算法的有效性。而且这种基于加权的ｋ一乎均算法能够处理符号属性数据，是传统的ｋ－平均算法所不能达到的。它可以运用到较大的数据库中去，但它能否运用到特大型复杂的数据库中进行聚类数据挖掘还有待进一步的研究。参考文献１史忠植知识发现【Ｍ］北京：清华太学出版社，２００２２ＨａｒｔＪｉａｗｅｉ，ＫａｍｂｅｒＭＤａｔａＭｉｎｉｎｇ：ＣｏｎｃｅｐｔｓａｎｄＴｅｃｈｎｉｑｕｅｓ［Ｍ］ＳａｎＦｒａｎｃｉｓｃｏ：ＭｏｒｇａｎＫａｕｆｍａｎｎＰｕｂｌｉｓｈｅｒｓ，２０００３ＧｒａｂｍｅｉｅｒＪ，ＲｕｄｏｌｐｈＡＴｅｃｈｎｉｑｕｅｓｏｆＣｌｕｓｔｅｒＡｌｇｏｒｉｔｈｍｓｉｎＤａｔａＭｉｎｉｎｇ［Ｊ］ＤａｔａＭｉｎｉｎｇａｎｄＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ，２００２．６（４）３０３４Ｊ３ＪｎＡＫ．ＭｕｒｔｙＭＮＦｌｙｎｎＰＪＤａｔａＣｌｕｓｔｅｒｉｎｇ：ＡＲｅｖｉｅｗ［Ｊ］ＡＣＭＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙｓ，１９９９，３１（３）２６４—３２３５ＭａｃＱｕｅｅｎＪＳｏｍｅＭｅｔｈｏｄｓｆｏｒＣｌａｓｓｉｆｉｃａｔｉｏｎａｎｄＡｎａｌｙｓｉｓｏｆＭｕｌｔｉｖａｒｉａｔｅＯｂｓｅｒｖａｔｉｏｎｓ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ５”ＢｅｒｋｅｌｅｙＳｙｍｐＭａｔｈ．Ｓｔａｔｉｓｔ．】９６７：２８Ｊ一２９７６ＫａｕｆｍａｎＪ，ＲｏｕｓｓｅｅｕｗＰＪＦｉｎｄｉｎｇＧｒｏｕｐｓｉｎＤａｔａ：ＡｎＩｎｔｒｏｄｕｃｔｉｏｎｔｏＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ［Ｍ］ＮｅｗＹｏｒｋ：ＪｏｈｎＷｉｌｅｙ＆Ｓｏｎｓ、１９９０７ＥｓｔｅｒＭ，ＫｒｉｅｇｅｌＨ只ＳａｎｄｅｒＪ，ｅｔａｌＡＤｅｎｓｉｔｙ—ｂａｓｅｄＡｌｇｏｄｔｔｍｌｆｏｒＤｉｓｃｏｖｅｒｉｎｇＣｌｕｓｔｅｒｓｉｎＬａｒｇｅＳｐａｔｉａｌＤａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ１９９６ＩｎｆｌＣｏｎｆ．ｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ，Ｐｏｒｔｌａｎｄ，ＯＲ１９９６—０８：２２６—２３１（下转第２０９页）２０１础的。将本文方法的相关程序在ＶＣ＋＋６．０环境下运行，也获得了成功。程序代码没有进行优化，以上图像序列的生成时间分别为０．２２ｓ和０．２６ｓ，优化后的结果能够满足用户实时性浏览的要求。实验表明，本方法显示的图像序列效果是良好的。参考文献ｌＪｏｈｎｓｏｎＢ，ＳｈｎｅｉｄｅｒｍａｎＢ．Ｔｒｅｅｍａｐｓ：ＡＳｐａｃｅ—ｆｉｌｌｉｎｇＡｐｐｒｏａｃｈｔＯｔｈｅＶｉｓｕａｌｉｚａｔｉｏｎｏｆＨｉｅｒａｒｃｈｉｃａｌＩｎｆｏｒｍａｔｉｏｎＳｔｒｕｃｔｕｒｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆｔｈｅ２”Ｉｎｔｌ．ＩＥＥＥＶｉｓｕａｌｉｚａｔｉｏｎＣｏｎｆ．．１９９１—１０．２ＺｈａｎｇＸ．ＦｕｍａｓＧＷ．ＭＣＶＥｓ：ＵｓｉｎｇＣｒｏｓｓ——ＳｃａｌｅＣｏｌｌａｂｏｒａｔｉｏｎｔＯＳｕｐｐｏｒｔＵｓｅｒＩｎｔｅｒａｃｔｉｏｎｗｉｔｈＭｕｌｔｉｓｃａｌＳｔｒｕｃｔｕｒｅｓ［Ｊ］．Ｔｅｌｅｏｐｅｒａ—ｔｏｒｓａｎｄＶｉｓｕａｌＥｎｖｉｒｏｎｍｅｎｔｓ，２００５，１４（１）：３１—４６．３ＲｏｂｅｒｓｔｏｎＧＧＭａｃｋｉｎｌａｙＪＤ．ＣａｒｄＳＫ．ＣｏｎｅＴｒｅｅｓ：Ａｎｉｍａｔｅｄ３ＤＶｉｓｕａｌｉｚａｔｉｏｎｓｏｆＨｉｅｒａｒｃｈｉｃａｌＩｎｆｏｒｍａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆＡＣＭＣｏｎｆｅｒｅｎｃｅＨｕｍａｎＦａｃｔｏｒｓｉｎＣｏｍｐｕｔｉｎｇＳｙｓｔｅｍｓ．１９９１：１８９．４ＺｉｅｇｌｅｒＪ，ＫｕｎｚＣ，ＢｏｔｓｃｈＶＭａｔｒｉｘＢｒｏｗｓｅｒ－－ＶｉｓｕａｌｉｚｉｎｇａｎｄＥｘｐｌｏｒｉｎｇＬａｒｇｅＮｅｔｗｏｒｋｅｄＩｎｆｏｒｍａｔｉｏｎＳｐａｃｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆＥｘｔｅｎｄｅｄＡｂｓｔｒａｃｔｓｏｆｔｈｅＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＣｏｍｐｕｔｅｒＨｕｍａｎＩｎｔｅｒａｃｔｉｏｎ．２００２：６０２—６０３．５ＨａｍＦｖ．ＵｓｉｎｇＭｕｌｔｉ—ｌｅｖｅｌＣａｌｌＭａｔｒｉｃｅｓｉｎＬａｒｇｅＰｒｏｊｅｃｔｓ［Ｃｌ／／Ｐｒｏｃ．ｏｆＩＥＥＥＳｙｍＰ．ＩｎｆｏｒｍａｔｉｏｎＶｉｓｕａｌｉｚａｔｉｏｎＣｏｎｆｅｒｅｎｃｅ．２００３：２２７—２３２．６ＦｕｍａｓＧＥＧｅｎｅｒａｌｉｓｅｄＦｉｓｈｅｙｅＶｉｅｗｓ［Ｃ］／／Ｐｒｏｃ．ｏｆＣＨＩ’８６ＨｕｍａｎＦａｃｔｏｒｓｉｎＣｏｍｐｕｔｉｎｇＳｙｓｔｅｍｓ．１９８６：１６—２３．７ＳｃｈａｆｆｅｒＤ，ＺａｏＺ，ＧｒｅｅｎｂｅｒｇＳ，ｅｔａ１．ＮａｖｉｇａｔｉｎｇＨｉｅｒａｒｃｈｉｃａｌｌｙＣｌｕｓｔｅｒｅｄＮｅｔｗｏｒｋｓＴｈｒｏｕｇｈＦｉｓｈｅｙｅａｎｄＦｕｌｌ—ｚｏｏｍＭｅｔｈｏｄｓ［Ｊ］．ＴｒａｎｓａｃｔｉｏｎＣｏｍｐｕｔｅｒＨｕｍａｎＩｎｔｅｒａｃｔｉｏｎ，１９９６，３（２）：１６２—１８８．８贾云得，吕宏静，刘万春．鱼眼变形立体图像恢复稠密深度图的方结论法［Ｊ】计算机学报，２０００，２３（１２）：１２３２－１２３４．图“是利用ｐｈｏｔｏｓｈｏｐ７．０对图３生成的一幅鱼眼图像，９ＷｉｊｋＪＪｖ’ＮｕｉｊＷＡＡ．ＳｍｏｏｔｈａｎｄＥｆｆｉｃｉｅｎｔＺｏｏｍｉｎｇａｎｄＰａｎｎｉｎｇ［Ｃ］／／Ｐｒｏｃ．ｏｆＩＥＥＥＳｙｍｐ．ＩｎｆｏｒｍａｔｉｏｎＶｉｓｕａｌｉｚａｔｉｏｎ方面的确具有较好的效果，但其缺点也是很显然的。Ｃｏｎｆｅｒｅｎｃｅ．２００３：１５—２２．１０ＩｇａｒａｓｈｉＴＨｉｎｃｋｌｅｙＫ．Ｓｐｅｅｄ—ｄｅｐｅｎｄｅｎｔＡｕｔｏｍａｔｉｃＺｏｏｍｉｎｇｆｏｒＢｒｏｗｓｉｎｇＬａｒｇｅＤｏｃｕｍｅｎｔｓ［Ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆＡＣＭＳｙｍｐｏｓｉｕｍｏｆＵｓｅｒＩｎｔｅｒｆａｃｅＳｏｆｔｗａｒｅａｎｄＴｅｃｈｎｏｌｏｇｙ．２００２：１３９—１４８．１１ＢｅｄｅｒｓｏｎＢＢ，ＭｅｙｅｒＪ，ＧｏｏｄＬ．Ｊａｚｚ：ＡｎＥｘｔｅｎｓｉｂｌｅＺｏｏｍａｂｌｅＵｓｅｒＩｎｔｅｒｆａｃｅＧｒａｐｈｉｃｓＴｏｏｋｉｔｉｎＪａｖａ［Ｃ］／／Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳｙｍｐ．ｏｎＵｓｅｒＩｎｔｅｒｆａｃｅＳｏｆｔｗａｒｅ．２０００：１７１．１８０．圈ｎ由圉３生成盼鱼眼图像１２ＢｅｄｅｒｓｏｎＢＢ．ＰｈｏｔｏＭｅｓａ：ＡＺｏｍｍａｂｌｅＩｍａｇｅＢｒｏｗｓｅｒＵｓｉｎｇＱｕａｎｔｕｍＴｒｅｅｍａｐｓａｎｄＢｕｂｂｌｅｍａｐｓ［Ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆＳｙｍ—而由本文方法生成的图像序列（图５～图７）不仅对用户感ｐｏｓｉｕｍｏｆＵｓｅｒＩｎｔｅｒｆａｃｅＳｏｆｔｗａｒｅａｎｄＴｅｃｈｎｏｌｏｇｙ．２００１：７１—８０．．兴趣的焦点图像给予详细的刻画，同时对焦点图像之间的联１３杨立志，顾耀林．一种基于有理二次样条曲线的图像放大方法【Ｊ１．系作出合适的表达，这种表达是以适合人们的记忆特点为基计算机应用，２００６，２６（５）：１０６１—１０６３．（上接第２０１）８ＡｎｋｅｒｓｔＭ，ＢｒｅｕｎｉｎｇＭ，ＫｒｉｅｇｅｌＨＰ，ｅｔａ１．ＯＰＴＩＣＳ：ＯｒｄｅｒｉｎｇＰｏｉｎｔｓ１２ＳａｒａｗａｇｉＳ，ＡｇｒａｗａｌＲ，ＭｅｇｉｄｄｏＮ．Ｄｉｓｃｏｖｅｒｙ—ｄｒｉｖｅｎＥｘｐｌｏｒａｔｉｏｎｔｏＩｄｅｎｔｉｆｙｔｈｅＣｌｕｓｔｅｒｉｎｇＳｔｒｕｃｔｕｒｅ［Ｃ］｜ｆＰ！ＯＣ．ｏｆ１９９９ＡＣＭ—ＳＩＧＭＯＤｏｆＯＬＡＰＤａｔａＣｕｂｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆＩｎｔｌ．Ｃｏｎｆ．ｏｎＥｘｔｅｎｄｉｎｇＤａｔａｂａｓｅＩｎｔｌ．Ｃｏｎｆ．ｏｎＭａｎａｇｅｍｅｎｔｏｆＤａｔａ．Ｐｈｉｌａｄｅｌｐｈｉａ，ＰＡ．１９９９—０６：４９．Ｔｅｃｈｎｏｌｏｇｙ．Ｖａｌｅｎｃｉａ．Ｓｐａｉｎ．１９９８—０３：１６８一１８２．９ＷａｎｇＷ．ＹａｎｇＪ．ＭｕｎｔｚＲ．ＳＴＩＮＧ：ＡＳｔａｔｉｓｔｉｃａｌＩｎｆｏｒｍａｔｉｏｎＧｒｉｄ１３余建桥，张帆．基于数据场改进的ＰＡＭ聚类算法【Ｊ】计算机科ＡｐｐｒｏａｃｈｔｏＳｐａｔｉａｌＤａｔａＭｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃ．ｏｆ１９９７Ｉｎｔｌ．Ｃｏｎｆ．ｏｎ学，２００５，３２（１）：１６５—１６７．ＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓ．Ａ血ｅｎｓ．Ｇｒｅｅｃｅ．１９９７—０８：１８６·１９５．１４刘少辉，胡斐，贾自艳，等．一种基于Ｒｏｕｇｈ集的层次聚类算１０ＫｏｈｏｎｅｎＴＳｅｌｆ－ｏｒｇａｎｉｚｅｄＦｏｒｍａｔｉｏｎｏｆＴｏｐｏｌｏｇｉｃａｌｌｙＣｏｒｒｅｃｔ法【Ｊ】．计算机研究与发展，２００４，４ｌ（４）：５５２－５５７．ＦｅａｔｕｒｅＭａｐｓ［Ｊ］．ＢｉｏｌｏｇｉｃａｌＣｙｂｅｒｎｅｔｉｃｓ，１９８２，４３（１）：５９—６９．１５ＨｅｔｔｉｃｈＳ．ＢｌａｋｅＣＬ．ＭｅｒｚＣＪ．ＵＣＩＲｅｐｏｓｉｔｏｒｙｏｆＭａｃｈｉｎｅ１ｌＡｒｎｉｎｇＡ，ＡｇｒａｗａｌＲ，ＲａｇｈａｖａｎＰ．ＡＬｉｎｅａｒＭｅｔｈｏｄｆｏｒＤｅｖｉａｔｉｏｎＬｅａｒｎｉｎｇＤａｔａｂａｓｅｓ［Ｚ］．１９９８－０１．ｈｔｔｐ：／／ｗｗｗ．ｉｃｓ．１ｕｃｉ．ｅｄｕ／～ｍｌｅａｒｎ／ＤｅｔｅｃｔｉｏｎｉｎＬａｒｇｅＤａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ１９９６Ｉｎｔｌ．Ｃｏｎｆ．ｏｎＤａｔａＭＬＲｅｐｏｓｉｔｏｒｙ．ｈｔｍｌ．ＭｉｎｉｎｇａｎｄＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ，Ｐｏｒｔｌａｎｄ．０Ｒ．１９９６—０８：１６４—１６９．万 方数据３对比图５～图７、图１１可以看出，鱼眼图像在表达整体联系改进的k-平均聚类算法研究
作者：作者单位：
孙士保， 秦克云， SUN Shibao， QIN Keyun
孙士保,SUN Shibao(西南交通大学智能控制开发中心,成都,610031;河南科技大学电子信息工程学院,洛阳,471003)， 秦克云,QIN Keyun(西南交通大学智能控制开发中心,成都,610031)
计算机工程
COMPUTER ENGINEERING2007，33(13)9次
刊名：英文刊名：年，卷(期)：被引用次数：
1.史忠植 知识发现 2002
2.Han Jiawei.Kamber M Data Mining:Concepts and Techniques 2000
3.Grabmeier J.Rudolph A Techniques of Cluster Algorithms in Data Mining 2002(04)4.Jain A K.Murty M N.Flynn P J Data Clustering:A Review 1999(03)
5.MacQueen J Some Methods for Classification and Analysis of Multivariate Observations 19676.Kaufman J.Rousseeuw P J Finding Groups in Data:An Introduction to Cluster Analysis 1990
7.Ester M.Kriegel H P.Sander J A Density-based Algorithm for Discovering Clusters in Large SpatialDatabases 1996
8.Ankerst M.Breuning M.Kriegel H P OPTICS:Ordering Points to Identify the Clustering Structure 19999.Wang W.Yang J.Muntz R STING:A Statistical Information Grid Approach to Spatial Data Mining 199710.Kohonen T Self-organized Formation of Topologically Correct Feature Maps 1982(01)
11.Arning A.Agrawal R.Raghavan P A Linear Method for Deviation Detection in Large Databases 199612.Sarawagi S.Agrawal R.Megiddo N Discovery-driven Exploration of OLAP Data Cubes 199813.余建桥.张帆 基于数据场改进的PAM聚类算法[期刊论文]-计算机科学 2005(01)
14.刘少辉.胡斐.贾自艳 一种基于Rough集的层次聚类算法[期刊论文]-计算机研究与发展 2004(04)15.Hettich S.Blake C L.Merz C J UCI Repository of Machine Learning Databases 1998
1.期刊论文 梁雪芳.别荣芳ⅱ.段季芳.付增梅.LIANG Xuefang.BIE Rongfang.DUAN Jifang.FU Zengmei 基于人工免疫网络的k-平均聚类算法的研究 -北京师范大学学报（自然科学版）2009,45(2)
以人工免疫网络理论结合k-平均算法,尝试了一种聚类分析的新的解决方案.对k-平均算法中每一次迭代求平均值来确定聚类中心的方式进行改进,采用人工免疫网络中克隆选择和变异机制对聚类中心进行操作,选取最优抗体作为下一次迭代的聚类中心,克服了k-平均算法中对孤立点敏感的缺点,从而大大减少了迭代次数.通过对4组标准数据的实验,结果表明,该算法具有很好的自适应性,收敛速度快,提高了聚类性能.
2.期刊论文 无线传感器网络网内数据融合的研究 -传感器与微系统2010,29(3)
针对目前无线传感器网络(WSNs)网内数据融合所面临的一些挑战,提出了一种基于无线传感器网络分布式K-平均聚类(DKCWSNs)算法的WSNs节点传感数据的分组策略,并采用基于自适应加权的数据融合方法对分组后的感知数据进行融合处理,从而获得更合理的结果.最后,通过实例验证了该方法的有效性.
3.学位论文 张儒良 聚类分析挖掘算法的改进及其应用 2004
为了提高k平均分区算法和层次凝聚算法的数据挖掘质量和执行效率,本文在综合分析k平均分区算法和层次凝聚算法各自优缺点和借鉴前人的算法改进方法的基础上,得出了一种速度更快、效率更高、聚类质量更好的改进算法(ICAA算法).本研究以贵州民族学院数学与计算科学系近四年的学生试卷数据作为测试对象,对ICAA算法与k平均分区算法和层次凝聚算法进行了性能比较.实践表明:ICAA算法是有效、可靠和快速的,它比k平均分区算法和层次凝聚算法节省了近一半的时间.从算法设计角度对ICAA算法进行了分析可知,该算法不但充分利用了k平均分区算法和层次凝聚算法的优点,而且在一定程度上避免了这两种算法的缺陷.与层次凝聚算法相比,ICAA算法在计算两个聚类之间的距离过程时大大减少了计算时间,其时间复杂度从层次凝聚算法的0(n<'2>)降为0(n).现在ICAA算法已被应用到贵州民族学院的《学生试卷质量分析系统》.该算法已发现了隐藏在试卷背后事先未被人们所知的一些问题,这些问题的发现为贵州民族学院教学管理提供了科学的辅助决策资料,为进一步提高试卷质量打下了良好的基础.
4.学位论文 王澜 教学网站中数据挖掘技术的研究与应用 2006
教学网站建设的目的，就是在教与学之间的互动环节上提供一个强而有力的平台。作为辅助教学的重要手段，教学网站目前已经蓬勃的发展起来。但是，纵观现有的教学网站：结构上，存在着重复建设多，代码复用性差，升级困难等问题；内容上，知识点不能形成很好的组织，不能结合个人特点形成动态教学。这就导致了两方面的问题：一方面，维护人员不能很好的发挥作用；另一方面，毫无特点的网站内容更是不能激起访问者的学习热情
，也就失去了网站建设的意义。因此，随着高校多媒体和网络资源的进一步建设，如何根据教育教学的需要开发高效、灵活，并且能最大限度满足人们信息获取和利用要求的学习网站，成为此次课题研究的主要方向。
本论文共分为六个部分。第一部分绪论，提出了“教学网站系统”概念，对课题的研究背景做了一下必要的总结，并提出了本次课题研究的意义。第二部分，介绍了课题所用到的关键技术和核心理论。主要阐述了网站结构搭建所要用到的struts和ibatis技术，以及内容建设所要用到的k．平均算法，并提出此算法目前的研究现状，为以后改进做准备。第三部分，根据原始算法的一些缺点，例如对K值和中心点选取过分依赖的问题，提出了改进的算法--KDM算法。通过对纯度和内聚性(紧密度和分离度)的比较，新算法有令人满意的效果。第四部分，把KDM算法应用到了教学网站的题库中，并提出了数据预处理技术。第五部分，介绍了所建网站的体系结构。详细介绍了struts框架，又针对struts在持久层开发的问题，提出了基于struts和ibatis的一种综合架构，增强了网站的复用性和可维护性。最后总结了此次研究所做的主要工作，并提出了不足，争取在以后的学习和工作中不断改进。
5.期刊论文 吴文丽.刘玉树.赵基海.WU Wen-li.LIU Yu-shu.ZHAO Ji-hai 一种新的混合聚类算法 -系统仿真学报2007,19(1)
聚类是数据挖掘的主要技术之一,是一种无导师监督的模式识别方式.聚类分析就是按照数据间的相似程度,依据特定的准则将数据划分成不同子类.K-平均算法是经典的聚类算法.蚂蚁聚类算法是近来涌现的新的聚类算法,它通过模拟蚁群的智能行为进行聚类分析,已经在数据挖掘中得到应用.通过分析蚂蚁聚类算法和K-平均算法两种不同聚类算法的基本思想,将两种算法结合得到混合聚类算法,仿真实验证明混合聚类算法的算法性能优于蚂蚁算法和K-平均算法.
6.学位论文 赵万磊 典型聚类算法及其应用研究 2005
聚类是知识工程和模式识别中一个重要的研究领域，在对大量数据进行分析和处理时有其独特的地位。聚类领域方面的研究经过上世纪80到90年代的突飞猛进的发展之后，产生了种类和用途繁多的聚类算法，然而，由于聚类本身属于无指导性学习，其处理问题的方式，以及获得解的可靠性大多是经验性的，而且通常算法过度依赖于具体的应用背景。论文针对聚类算法研究现状，围绕聚类算法及其相关问题，总结和评价现有聚类算法，以及影响聚类分析的各个环节，探讨改进制约聚类性能的关键因素，并论文对普适性较好的聚类算法进行改进。
由于现在存在聚类算法众多，论文首先对各种聚类算法分门别类进行分析讨论，每类算法以其中较为典型的算法为例，在分析总结评价算法优缺点的同时，还剖析聚类算法的具有各种特性的原因；虽然，聚类在许多没有先验知识的应用环境下是不可或缺的，但在没有先验知识的环境下解决问题，从直觉上比有先验知识下解决问题更困难。对此，论文从理论上分析了聚类问题的规模和难度。并且分析得出，基于划分和基于密度的算法具有良好的特性，对这两类典型算法的研究和改进具有重要意义。
检索结构是制约众多聚类算法效率的关键环节，论文分析讨论了两类现有的索引结构，在此基础上提出了一种简单有效的索引结构，并将其用于一个视频关键帧的匹配问题上，同时讨论了它在提高聚类效率上可行的应用。
K平均聚类算法是一类重要的聚类算法，它是目前应用最广的基于划分的聚类算法，论文在研究和总结最近聚类算法的研究进展上，提出了一种改进的K平均聚类算法，并将它应用到文本聚类上，论文还分析对比了该方法的有效性。另外，MeanShift算法是一种基于密度的聚类算法，最近的研究表明它可以成功的应用到诸如图像分割的问题上，论文将K平均聚类算法和MeanShift聚类算法相结合，提出一种新的可变带宽策略对已有MeanShift算法进行有效改进，并将它应用到图像分割上；虽然，K平均聚类算法得到广泛应用，但其迭代过程的收敛性很少有研究者提及，论文将其归结为MeanShift迭代过程的一个特例从而分析了它的收敛性。
7.学位论文 刘霞 模糊聚类在电信数据挖掘中的研究与应用 2003
首先,该文就数据挖掘的起源、发展和当前研究热点进行了综述,并介绍了数据挖掘的基本概念、数据存储类型、数据预处理技术(包括数据清理、数据集成、数据归约和数据变换等方法)、数据挖掘的功能以及模式兴趣度.随后,在聚类方法分类的基础上,重点介绍了聚类划分法中的k-平均方法、k-中心点方法以及它们的改进,并就模糊集合的相似关系提出了三种度量方法:相似度、距离和语义关联度.最后,以佛山电信关于通话记录的数据挖掘为背景,针对通话记录数据的特点,提出了基于模糊语义关联度的聚类算法,并通过数据选择、数据预处理、算法实现等具体步骤,证明基于模糊语义关联度的聚类算法是一种行之有效的电信通话记录数据挖掘算法.模糊聚类不仅适用于电信行业,在模式匹配、Web文本数据挖掘以及空间数据挖掘等方面都有一定的实际意义,具有广阔的发展空间.
8.期刊论文 尹珧人.王德广.YIN Yao-ren.WANG De-guang 一种改进的k-means聚类算法在入侵检测中的应用 -科学技术与工程2008,8(16)
讨论了经典的k-平均聚类算法,说明了它存在不能很好地处理符号数据和对噪声与孤立点数据敏感等不足,提出了一种改进的k-平均聚类算法,克服了k-平均聚类算法的缺点,并从理论上分析了该算法的复杂度.实验证明,用该方法实现的数据聚类与传统的基于平均值的方法相比较,能有效提高数据聚类效果以及入侵检测的准确度.
9.学位论文 芦立华 基于后缀树的中文文本聚类算法研究 2005
文本挖掘是指在大量文本集合上发现隐含的、有趣的、有用的模式和知识。文本挖掘技术的出现，使得汁算机处理大规模文本资源成为可能，对文本的处理，在信息检索等领域有着广阔的应用前景。
本文研究基于后缀树的中文文本聚类。文本聚类是文本挖掘重要手段和研究分支。后缀树作为一种数据结构，最早是为支持有效的字符串匹配和查询而提出的，例如：寻找最长的重复子串，相似串的匹配，串比较等问题。后缀树聚类(STC)方法的一个突出的特点是将文本看作短语串而非词的集合，这样可以更充分地使用词语之间的近似信息，达到更佳的聚类结果。STC已经在英文文本聚类中有了一些成功的应用，本文针对中文文本的特点，尝试将这种方法应用到中文文本聚类上。
本文对数据挖掘尤其是中文文本聚类及相关理论与技术进行了研究，主要包括以下内容： (1)对文本聚类算法进行了研究，特别是k-平均算法及其在中文文本中的应用。 (2)针对中文文本组成上的特点，研究了中文文本聚类的模型。
(3)研究并验证了后缀树技术在中文文本聚类这一特定领域应用的可行性。 (4)设计并实现了一个小型的中文文本聚类系统，可以进行k-平均和STC聚类。
(5)通过几组中文文本数据集对k-平均和STC两种聚类算法进行了实验和比较，得出了一些有用的结果，并从理论上作了进一步的说明和论证。同时，对试验中出现的问题进行了探讨，并提出了进一步研究的方向。
10.期刊论文 赵万磊.王永吉.张学杰.李娟.ZHAO Wan-lei.WANG Yong-ji.ZHANG Xue-jie.LI Juan 一种优化初始中心点的K平均文本聚类算法 -计算机应用2005,25(9)
文本聚类在信息过滤,网页分类中有着很好的应用.但它面临数据量大,特征维度高的难点.由于K平均算法易于实现,对数据依赖度底,在文本聚类中得到应用.然而,传统K平均以及它的变种会产生有较大波动的聚类结果.因此对K平均算法进行了改进,通过优化聚类初始中心的选择,得到一种适合对文本数据聚类分析的改进算法.大量实验显示,该算法可以生成质量较高而且聚类质量波动性较小的结果.
1.李杉.张化祥 基于Bagging的聚类集成方法[期刊论文]-计算机工程与设计 2010(1)
2.曹亮.舒红平.刘魁 基于观测数据偏差修正的DBSCAN改进算法[期刊论文]-计算机工程与设计 2009(13)
3.韩晓红.胡彧 K-means聚类算法的研究[期刊论文]-太原理工大学学报 2009(3)4.靳战峰.李江.孙立军 稳定性交通参数检验方法研究[期刊论文]-公路工程 2009(1)
5.黄浩.肖立志.张国毅.孙强 基于模拟退火的K-means算法研究[期刊论文]-舰船电子对抗 2008(6)6.孙秀娟.刘希玉 基于新聚类有效性函数的改进K-means算法[期刊论文]-计算机应用 2008(12)7.陈森平.陈启买 基于熵的K均值算法的改进[期刊论文]-广东技术师范学院学报 2008(9)
8.李江.SUN Li-jun 一种基于自由流车速的交通数据检验方法[期刊论文]-交通运输系统工程与信息 2008(4)9.李卫平 K-Means聚类算法研究[期刊论文]-中国西部科技 2008(8)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjgc200713068.aspx授权使用：黄小强(wfxadz)，授权号：dbeb1af2-616d-45f5-b8a7-9e2100a9c93e
下载时间：2010年11月1日
