数据挖掘中聚类分析的理论研究
摘要：近年来，数据挖掘技术是非常热门的研究方向,聚类分析作为数据挖掘的核心技术，也是非常热门的研究课题。本文主要对数据挖掘中的聚类分析进行理论上的研究，介绍聚类分析的常用方法，着重研究K-means的原理和EM聚类的实例。
关键词：数据挖掘，聚类分析，理论研究，K-means，EM
一、背景
随着计算机技术的不断发展、网络的迅速普及，人们与外界进行信息交流的渠道和机会越来越多。在这个过程中，人们获得的数据资源很丰富，正是由于大量数据的涌入，就存在一些无用的数据，这增加了信息使用者使用有用数据的难度。
如何从巨量的数据中获得有用的、有价值的信息,采用传统的数据库技术有时显得无能为力，如何从信息的海洋中提取出人们感兴趣的知识，以帮助人们完成特定的任务成为了一个迫切需要解决的问题。基于这样一种需求，用来帮助用户从这些海量数据中分析出其间所蕴涵的有价值的模式和知识的技术——数据挖掘就应运而生了。 二、选题介绍
本文所要研究的就是关于数据挖掘中聚类分析的理论，着重介绍聚类分析的方法，分析聚类的理论价值。
数据挖掘是一门内容丰富的学问，它涉及很多数据挖掘的方法。利用数据挖掘技术以及SQL Server 2005软件平台，能够研究很多实际问题，如模式识别、空间数据分析、GIS地图、图像处理、市场研究、WEB文档归类、市场营销客户群归类、城市规划、地震研究等。
数据挖掘汇集了来自机器学习、模式识别、数据库、统计学、人工智能以及管理信息系统等各学科的成果。多学科的相互交融和相互促进，使得数据挖掘这一新学科得以蓬勃发展。被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科。数据挖掘的根本在于统计学, 统计方法中多元数据分析的三大方法之一的聚类分析则是数据挖掘采用的核心技术, 成为该研究领域中一个非常活跃的研究课题。
所谓数据挖掘，又叫数据库中的知识发现, 简称KDD,就是从大量的、不完全的、有噪声的、模糊的、随机的、无序的数据中提取隐含在其中的有效的、有价值的、可理解的模式，进而发现有用的或是潜在有用的知识，并得出时间的趋向和关联，为用户提供问题求解层次的决策支持能力。数据挖掘所处理的数据至少具有如下特点:（1） 数据源是丰富多彩的. 数据量巨大, 有结构化的数据, 但更多的是半结构化的数据；（2） 有用数据是隐藏的. 有用数据不是直观明了地表现出来, 而是隐藏在巨量的数据之中；（3） 有用数据能被人们所理解, 以人们熟知的模式反映数据的本质特征。
聚类分析是数据挖掘中一种很重要的技术。聚类分析基于“ 物以类聚”的朴素思想, 根据事物的特征对其进行聚类或分类。所谓聚类，就是把拥有大量数据的集合分成若干簇，在同一个簇中的数据对象之间最大程度的相似，而在不同簇中的数据对象之间具有最大程度的不同。在实际应用中，一个聚类结果会影响到数据挖掘的后续工作，通常一个好的聚类结果会使数据分析工作变得简单清晰，比较容易得到用户想要的知识，而一个糟糕的聚类结果却正好相反，甚至得不到用户想要的结果。因此聚类分析成了数据挖掘中的最为关键的部分，发展成为一个很活跃的研究方向。 三、原理介绍
聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的。根据其基本思想，可以分为：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法。实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合。 （1）划分方法
划分方法的基本思想是：给定具有N 个对象或元组的数据库，指明想要得到的簇的数目k，一个划分方法利用采取的算法将这N 个对象划分成k 个分组，其中k （2）层次方法 层次聚类方法通过将数据组织成若干组并形成一个相应的树状图来进行聚类。根据其聚类的过程是自下而上还是自上而下，层次聚类方法又分成了聚合聚类和分解聚类两种。其主要思想如下：聚合聚类方法：将数据集中的每一个对象看作是一个单独的簇，然后根据某个给定的原则将这些簇进行合并，直到数据集中的对象形成一个簇或者是满足事先定义的某个终止条件。分解聚类方法：与聚合聚类方法恰好相反，将所有的数据集看成是一个大的聚类，根据某个给定的规则对这个簇进行划分，细化成越来越小的簇，直到每个数据对象自成一个簇或者达到某个终止条件。几种典型的层次方法有BIRCH，CURE 等。 （3）基于密度的方法 对于非球形的簇，用对象之间的距离来度量相似性是不够的，因此为了发现任意形状的簇，利用密度(数据或对象点的数目)来代替距离，提出了基于密度的聚类方法。该方法从数据对象的分布密度出发，将簇看成是由低密度区域分割开的高密度对象区域。DBSCAN 是一种典型的基于密度的方法，它通过检查数据库中每个点的e 邻域来进行聚类。 （4）基于网格的方法 该方法采用一个多分辨率的网格数据结构，它首先将数据空间划分成有限数目的单元，形成一个网格结构，所有的处理都是以单个的单元为对象。处理速度通常与目标数据库中记录的个数无关，它只与单元的个数有关，故这种方法的一个突出优点就是处理速度很快。代表性算法有STING。STING 算法将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。 （5）基于模型的方法 基于模型的方法为每个簇都假定了一个模型，并寻找数据对给定模型的最佳拟合。该方法通过构建反映数据点空间分布的密度函数来实现聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。人工神经网络就是一种基于模型的聚类方法，是模拟生物神经网络的结构和功能而设计的一种信息处理系统。人工神经网络方法将每个簇描述为一个标本，标本作为簇的原型，不一定对应特定的数据实例和对象。根据某些距离度量，新的对象可以被分配给标本与其 最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标本的属性来预测。 常用的聚类方法有：CLARANS(随机搜索聚类法),CURE（利用代表点聚类）,BIRCH（利用层次方法的平衡迭代归约和聚类）,DBSCAN（基于高密度连接区域的密度聚类方法）,STING（统计信息风格），（FCM）模糊聚类算法。 这些聚类方法可以导出确定的聚类, 即一个数据点或者属于一个类, 或者不属于一个类, 而不存在重叠的情况。我们可以称这些聚类方法为“ 确定性分类” 。在一些没有确定支持的情况中, 聚类可以引入模糊逻辑概念。对于模糊集来说, 数据点都是以一定程度属于某个类, 也可以同时以不同的程度属于几个类。常用的模糊聚类算法是模糊C平均值FCM算法。该算法是在传统C均值算法中应用了模糊技术。 此图显示了各种聚类分析方法的异同，在实际应用中，它们适用的场合也不尽相同。 数据挖掘对聚类分析的要求：1.可扩展性(Scalability)：大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率；2.处理不同数据类型的能力；3.数字型，二元类型，分类型/标称型，序列型,比例标度型等等；4.发现任意形状的能力：基于距离的聚类算法往往发现的是球形的聚类，其实现实的聚类是任意形状的；5.用于决定输入参数的领域知识最小化，对于高维数据，参数很难决定，聚类的质量也很难控制；6.处理噪声数据的能力，对空缺值、孤立点、数据噪声不敏感；7.对于输入数据的顺序不敏感，同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果；8.高维度，高维度的数据往往比较稀松，而且高度倾斜；9.基于约束的聚类，找到既满足约束条件，又具有良好聚类特性的数据分组；10可解释性和可用性，聚类要和特定的语义解释和应用相联系。 聚类分析在数据挖掘中的应用主要有三个方面： 一、聚类分析可以作为其他算法的预处理步骤, 这些算法再在生成的簇上进行处理。可作为特征和分类算法的预处理步骤, 也可将聚类结果用于进一步关联分析。 二、可以作为一个独立的工具来获得数据分布的情况, 观察每个簇的特点, 集中对特定的某些簇做进一步分析。可用在市场细分、目标顾客定位、业绩评估、生物群种划分等方面。如在商务上, 聚类分析可以帮助市场分析人员从客户基本库中发现不同的客户群, 并且用购买模式来刻画不同的客户群的特征。 三、聚类分析可以完成孤立点挖掘。许多数据挖掘算法试图使孤立点影响最小化, 或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中, 孤立点可能预示着欺诈行为。 四、内容 在实际应用聚类分析中，可以根据有无领域知识参与将聚类分析的整个过程分解为3个环节，下图是整个过程的流程图。 （一）K-means 1、概念引入 K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。 K-means算法是硬聚类算法，是典型的局域原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到
