K-Means算法中K值的确定.pdfVIP

K-Means算法中K值的确定

聚类算法在数据处理中有广泛的应用，K-Means算法是一种较为常用且有效

的聚类算法。但它有一个缺点，在进行算法之前需要预先给出聚类的个数。因此，

如何在K-Means算法中确定合适的K值成为该算法的一大问题。本文讨论了几种

常用的确定K值的方法，并详细讨论了一种利用评价函数判断K值好坏的方法，

之后在若干个数据集中进行了测试，取得了较好的效果。

1.1聚类算法的演变

正所谓，物以类聚，人以群分。将可识别的物体进行分类一直以来都是符合

人类的基本认知规律的。早在公元前三世纪的古希腊，分类学就已经作为一门科

学盛行于当下，而作为其代表人物的亚里士多德不仅对五百余种不同的动植物进

行了分类，还对五十余种动物进行了解剖，并首先指出鲸鱼是胎生的。我国著名

医药学家李时珍外出至我国的各大名山大川考察，尝遍百草，将千余种植物分为

五部，三十类。俄罗斯著名化学家门捷列夫更是首创了元素周期表，将化学元素

依其质子数分门别类，并以此对一些尚未被发现的元素作出预言。

可以看到的是，不论在人类的何种时期，将事物分门别类都是一个恒久的问

题。在工业时代之前，通过人工的方法进行分类尚且是没有问题的。然而，在信

息革命后的今天，我们若还是一味的依赖传统方法，就将难逃被时代淘汰的命运。

因为信息时代所需要分门别类的，是海量的数据。而面对这样规模的数据，人工

的方法将会有过大的消耗，再加上人类对于数据的认知是十分抽象的，缺乏直观

的认识，因此其效果大打折扣。

面对这些问题，聚类分析应运而生。聚类分析，又名群分析。它以相似性为

基础，在没有鲜艳信息的前提下，将看似无序的研究样本分类成多个类簇。其原

则是组内的相似性较高，而组间的相似性较低。它的起源便是上文所提到的分类

学。在早期的分类学中，人们主要依靠经验和专业知识进行分类。纵观人类科技

发展史，随着科技进程的不断推进，当原始的分类方法不足以满足我们对分类的

需求，人们便将数学工具应用到分类学中，逐步形成了数值分类学、聚类分析等

学科。聚类分析并不依赖于人类的直觉，而是通过算法的应用，将数据进行基于

某种规则的客观分类。在数据规模增大到一定程度的时候，这种方法相较于传统

方法就具有了不可比拟的优势。

1.2聚类算法的应用

1

在生活中，聚类分析被广泛应用，譬如在推荐系统中，聚类分析就有着举足

轻重的作用。当该系统作用时，我们需要识别出不同的客户群，即了解被推荐人

可能还会想要购买什么商品。就网上书店而言，一个购买《经济学原理》的用户，

还有可能会购买《货币战争》。而这样的用户可能被归为“经济学爱好者”这一

客户群。那么，如果客户能够得到了正确的分类，则经系统推荐出的书目被售出

的概率也将增大。因此，一个准确的聚类能够有效地提高商品的销量，具有很大

的商业价值。

在面对文本处理的问题中，我们可以运用聚类假设的原则，即相似度大的文

档被分为同类文档，相似度小的文档被分为不同类文档。考虑到文本聚类不需要

人工标注与训练过程，因此其具有比较高的自动化处理能力与灵活性。它在多文

档自动文摘系统Newsblaster中作为其自然语言处理的预处理步骤。此外，在搜

索引擎中，如果对有哪些信誉好的足球投注网站引擎的返回结果聚类，则可以缩小检索内容的范围，让用

户更为精确地找到所需要的信息。

而对于模式识别而言，聚类分析也显得颇为重要。在基于聚类的模式识别中，

不论是图像识别，或是语音识别，首先要将图像转化为数据，亦即提取图像或是

语音的特征值。在获取了特征值以后，图像或是语音便映射到了某个数据点。我

们需要根据特征值对其进行聚类。从而在对某个陌生图像进行识别时，只需判断

其特征值的分类便可完成识别。

此外，聚类也可以应用于防垃圾邮件系统中。电子邮件是我们用于信息通讯

的一个常用媒介。但是这个媒介时常会被利用作发送诸如广告，病毒，诈骗信息

等垃圾邮件，打扰人们的正常使用。因此，在电子邮箱中，我们需要一个防垃圾

邮件系统，用于鉴别“垃圾邮件”与“非垃圾邮件”。而对一个新的邮件进行分

类，便可更好的判断该邮件是否属于不良邮件，以改善电子邮件用户的用户体验。

聚类算法不仅应用广泛，其种类也是繁多的。依据其聚类原理可以分为基于

划分的方法，基于层次的方法，基于密度的方法等等。而K-Means聚类算法就

是一种十分经典的基于划分的方法。它的算法简单，聚类速度较快，但是有一个