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

PAGE PAGE 4 K-Means算法中K值的确定 聚类算法在数据处理中有广泛的应用，K-Means算法是一种较为常用且有效的聚类算法。但它有一个缺点，在进行算法之前需要预先给出聚类的个数。因此，如何在K-Means算法中确定合适的K值成为该算法的一大问题。本文讨论了几种常用的确定K值的方法，并详细讨论了一种利用评价函数判断K值好坏的方法，之后在若干个数据集中进行了测试，取得了较好的效果。 1.1 聚类算法的演变 正所谓，物以类聚，人以群分。将可识别的物体进行分类一直以来都是符合人类的基本认知规律的。早在公元前三世纪的古希腊，分类学就已经作为一门科学盛行于当下，而作为其代表人物的亚里士多德不仅对五百余种不同的动植物进行了分类，还对五十余种动物进行了解剖，并首先指出鲸鱼是胎生的。我国著名医药学家李时珍外出至我国的各大名山大川考察，尝遍百草，将千余种植物分为五部，三十类。俄罗斯著名化学家门捷列夫更是首创了元素周期表，将化学元素依其质子数分门别类，并以此对一些尚未被发现的元素作出预言。 可以看到的是，不论在人类的何种时期，将事物分门别类都是一个恒久的问题。在工业时代之前，通过人工的方法进行分类尚且是没有问题的。然而，在信息革命后的今天，我们若还是一味的依赖传统方法，就将难逃被时代淘汰的命运。因为信息时代所需要分门别类的，是海量的数据。而面对这样规模的数据，人工的方法将会有过大的消耗，再加上人类对于数据的认知是十分抽象的，缺乏直观的认识，因此其效果大打折扣。 面对这些问题，聚类分析应运而生。聚类分析，又名群分析。它以相似性为基础，在没有鲜艳信息的前提下，将看似无序的研究样本分类成多个类簇。其原则是组内的相似性较高，而组间的相似性较低。它的起源便是上文所提到的分类学。在早期的分类学中，人们主要依靠经验和专业知识进行分类。纵观人类科技发展史，随着科技进程的不断推进，当原始的分类方法不足以满足我们对分类的需求，人们便将数学工具应用到分类学中，逐步形成了数值分类学、聚类分析等学科。聚类分析并不依赖于人类的直觉，而是通过算法的应用，将数据进行基于某种规则的客观分类。在数据规模增大到一定程度的时候，这种方法相较于传统方法就具有了不可比拟的优势。 1.2 聚类算法的应用 在生活中，聚类分析被广泛应用，譬如在推荐系统中，聚类分析就有着举足轻重的作用。当该系统作用时，我们需要识别出不同的客户群，即了解被推荐人可能还会想要购买什么商品。就网上书店而言，一个购买《经济学原理》的用户，还有可能会购买《货币战争》。而这样的用户可能被归为“经济学爱好者”这一客户群。那么，如果客户能够得到了正确的分类，则经系统推荐出的书目被售出的概率也将增大。因此，一个准确的聚类能够有效地提高商品的销量，具有很大的商业价值。 在面对文本处理的问题中，我们可以运用聚类假设的原则，即相似度大的文档被分为同类文档，相似度小的文档被分为不同类文档。考虑到文本聚类不需要人工标注与训练过程，因此其具有比较高的自动化处理能力与灵活性。它在多文档自动文摘系统Newsblaster中作为其自然语言处理的预处理步骤。此外，在有哪些信誉好的足球投注网站引擎中，如果对有哪些信誉好的足球投注网站引擎的返回结果聚类，则可以缩小检索内容的范围，让用户更为精确地找到所需要的信息。 而对于模式识别而言，聚类分析也显得颇为重要。在基于聚类的模式识别中，不论是图像识别，或是语音识别，首先要将图像转化为数据，亦即提取图像或是语音的特征值。在获取了特征值以后，图像或是语音便映射到了某个数据点。我们需要根据特征值对其进行聚类。从而在对某个陌生图像进行识别时，只需判断其特征值的分类便可完成识别。 此外，聚类也可以应用于防垃圾邮件系统中。电子邮件是我们用于信息通讯的一个常用媒介。但是这个媒介时常会被利用作发送诸如广告，病毒，诈骗信息等垃圾邮件，打扰人们的正常使用。因此，在电子邮箱中，我们需要一个防垃圾邮件系统，用于鉴别“垃圾邮件”与“非垃圾邮件”。而对一个新的邮件进行分类，便可更好的判断该邮件是否属于不良邮件，以改善电子邮件用户的用户体验。 聚类算法不仅应用广泛，其种类也是繁多的。依据其聚类原理可以分为基于划分的方法，基于层次的方法，基于密度的方法等等。而K-Means聚类算法就是一种十分经典的基于划分的方法。它的算法简单，聚类速度较快，但是有一个缺点：需要预先给出聚类数K的值。因此，本文的主要目的就是给出一个选择适合的K值的方法。在第二章中我们详细介绍了聚类算法原理，以及K-Means算法的过程，并讨论的一些古典的与新起的选取K值的方法。而第三章则重点讨论了一种评价函数选取K值的方法，并随后做了相应的数值试验以对其结果进行考量。 第二章 浅谈聚类算法 2.1 聚类算法的分类 正如前文谈到的，数据聚类在数据分析中有着重要作用，并在