基于图的聚类算法研究+文献综述(2)
时间:2017-05-03 22:02 来源:毕业论文 作者:毕业论文 点击:次
1.1.1 数据挖掘的内容 数据挖掘源于数学、计算机、经济管理等多门学科，一个清楚的分类就显得尤为重要[ ]。数据挖掘大致可以分为以下几个方面：分类、聚类、关联规则[ ]。 分类方法[ ][ ][ ]是将数据集按照某个标准分成若干个类，并告诉使用者某个数据属于某个类。它需要有一个训练样本集，将测试集与样本集做比较，分类最终将测试集中的数据划分到样本集的每一个类中。 聚类方法[ ][ ]是将数据集中，差异性小的点聚合起来，形成若干个簇，每个簇都反映了它们的个性。这个方法不需要有训练集，使用者只要做一些简单的设置，如聚类个数或是聚类度量标准等，就可以得到聚类结果。 关联规则[ ]通过扫描整个数据集，将经常出现的一对或一组数据体现出来。这种方法主要基于统计的方法，通过设定阈值，从海量数据中得到符合阈值要求的组合，组合中出现的元素表明它们相互之间有关系。 1.1.2 数据挖掘的意义 数据挖掘就是从大量繁杂的数据中获取隐含在其中的信息，比如说对顾客分类，聚类，欺诈甄别，潜在顾客识别等，现在应用领域很广的，涉及了零售，金融，银行，医疗，政府决策，企业财务，商业决策等，越来越多的成为人们从数据中获取相关知识的重要途径。 1.2 聚类研究现状 数据挖掘要求我们从数据中提取未知和隐藏的知识[ ][ ]。在各种数据挖掘技术中，聚类是最重要的技术之一，有助于分析和发现数据集中的共性。在聚类中，簇内数据的相似程度高，而簇间对象的相似程度尽可能的低。基于图的聚类算法，很多都是从传统的算法演变过来的，所以研究传统的算法，会给我们研究聚类算法一定的启发和指导，甚至可以在传统算法上进行改进，使之符合数据的要求。 1.2.1 传统的聚类算法 传统的聚类方法可以分为五类，分别是基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法，每一类的算法都不尽相同，下面将详细的介绍一些常用的算法。[ ][ ] 1.2.1.1 基于划分的方法 用户在初始情况下输入要聚成的簇的个数，程序在计算过程中将数据集中的数据划分到每个簇当中，在划分过程中通过迭代，不断调整每个数据点所属的簇，目的是使簇的中心更加合理，划分标准最优。但是在调整过程中需要注意的是每个数据点只能属于一个簇，每个簇至少包含一个数据点。这类方法的代表算法有：K-means、APM、K-mediods。 1.2.1.2 基于层次的方法 层次聚类分析也是一种广泛使用的方法。层次聚类可以分为凝聚层次聚类法和分裂层次聚类法。凝聚层次聚类的方法先将n个独立的数据点看做是n个簇，然后不断的合并，直到簇的个数符合预先的设定为止。分裂层次聚类的方法，先将n个数据点划归同一个簇，然后不断分裂，直到簇的个数符合预先的设定为止。凝聚层次聚类法（HAC）较为常用，簇的个数取决于人为的设置。对于凝聚层次聚类法，CURE和ROCK在层次聚类中使用静态模型来确定最相似的簇进行合并。除此之外BIRCH也十分典型。 1.2.1.3 基于密度的方法 基于密度的方法以阈值作为终止条件，通过簇的不断扩大进行聚类，直到密度低于设定的阈值为止。典型的算法有DBSCAN、OPTICS[ ]等。 1.2.1.4 基于网格的方法 这种方法首先将数据空间按照一定的尺度划分为若干个网格，再将数据点归类到各个网格中。聚类的过程在网格结构中进行，对于消除噪声有一定的积极意义。这类算法的代表是STING算法。 1.2.1.5 基于模型的方法 这种方法首先需要使用者对聚类的模型进行假设，即假设要聚类的数据是基于某种分布的。然后使用这种模型寻找合适的数据。典型的方法有COBWEB[ ]算法。 (责任编辑：qin) |