K-means算法WEB文本挖掘中的聚类研究(3)

菜单

1.2.1 聚类分析简介

聚类分析简称聚类，是一个将数据对象划分为子集的过程[ ]。每个子集称为“簇”，使得簇中对象彼此相似同时簇间的对象不相似。由聚类分析算法产生的簇的集合称为一个聚类。聚类的产生和算法有关，在完全相同的数据集中，不同的聚类方法可能产生不同的聚类。这种划分并不是通过人，而是通过聚类算法进行的。聚类非常有用，因为它可能会产生新的事先无法被人发现的群组，这可能就是新的知识[ ][ ]。

聚类分析是统计学的分支之一，主要集中在基于距离的聚类分析。很多种方法，比如K-means，K-medoids和一些别的方法已经作为工具被加入到了许多很有用的软件包或者是系统中。比较著名的有S-Plus、SPSS以及SAS等。聚类算法被称作“无监督学习”，一般不提供任何标号信息，由系统自己通过观察学习，而不是示例学习。

1.2.2 研究现状

聚类分析是数据挖掘中的重要研究内容之一。聚类分析是一种重要的数据分析技术，被很多开发人员广泛的研究。通过聚类，人们能够识别稀疏或者密集的区域，发现全部的模式，以及各类不同数据属性中可能非常有趣的相互关系。聚类的用途广泛，可以应用于商业、农业、地理信息系统中。聚类分析算法也可作为其他算法（如关联分析和分类）的预处理步骤，这样可以使得这些算法的效率大大的提高。聚类有时又称为自动分类，因为聚类可以自动的发现分组，这是聚类算法的突出优点。在某些应用中，聚类可以用于离群点检测，比如信用卡欺诈和电子商务犯罪活动监控[ ]。这么多的应用，使得聚类分析已经成为数据挖掘领域中一个非常活跃的研究课题。

在数据挖掘的领域，研究工作一般集中在寻找有效聚类分析大型数据库的合适的方法上。研究主题包括聚类方法的可伸缩性、对复杂形状以及各种数据的类型聚类的有效性上，另外还有一些高维的聚类技术，以及针对大型数据库中的混合数据的聚类方案[ ]。

1.2.3 传统的聚类算法概述

. 虽然聚类的方法很多，对聚类算法很难有一个简洁的分类，分类很有可能会有重叠，因为一种方法具有很多种特征。尽管如此，还是可以对不同的聚类方法提出很多一些系统的描述。传统的聚类方法主要一般分为四类，划分的方法、层次的方法、基于密度的方法、基于网格的方法，每一类的方法都不尽相同，下面将详细的介绍一些常用的方法 [ ]。源:自~751·论`文'网·www.751com.cn/

1.2.4 基于划分的方法

聚类分析中最简单、最基本的版本是划分，它把对象组织成多个互斥的组和簇。我们假定簇个数K作为背景知识给定，这个参数很重要，因为他是划分方法的起点。

形式地，给定n个数据对象的数据集为D，另外还有生成的簇数K，划分算法将对象分为K个分区（K<n），每个分区就是一个簇。我们的目标是让同一个簇中的对象是“相似的”，而不同簇间的对象是“相异的”。所以我们为了达到全局最优解，划分的方法一般都必须枚举所有的划分，这样容易导致开销巨大，一般采用经典算法渐进的提高聚类的质量，逐步逼近最优解。比如K-均值算法或K-中心点算法，这类算法很适合发现一些球状簇 [ ]。如果要是为了发现复杂形状的簇和对超大型的数据集进行聚类，我们就必须扩展一下基于划分的方法了。这也是划分方法的缺陷之一。

1.2.5 基于层次的方法

尽管划分方法满足把对象分为一些相异的簇这一基本聚类要求，但是在一些不同的情况下，我们可能想要将数据划分成不同层次上的组群。层次方法创建给定数据对象集的层次分解。层次聚类方法将数据对象组成层次结构或簇的“树”，层次聚类可以分为凝聚层次聚类法与分裂层次聚类法两种[ ]。凝聚层次聚类的方法先将n个独立的数据点看做是n个簇，然后不断的合并，直到簇的个数与之前规定的相符合为止。分裂层次聚类的方法，先将n个数据点划归同一个簇，然后不断分裂，直到簇的个数与之前规定的相符合为止。经典算法有AGNES算法和DIANA算法。这种方法的缺陷在于一旦某个步骤完成，这个步骤就不能被撤销，回溯在这种基于层次的方法中完全不能使用，所以，基于层次的方法不能更正错误的决定 [ ]。