数据挖掘：基于密度的聚类方法

数据挖掘一般是指从大量的数据中通过算法来搜索隐藏于其中的有效信息过程。数据挖掘通过与统计、在线分析处理、情报检索、机器学习、专家系统和模式识别等诸多方法相配合，实现有效信息的获取和表达。

在算法方面，数据挖掘可分为三大类：分类区隔类、推算预测类和序列规则类；其中，六分项为：Classification和Clustering（分类区隔类）；Regression和Time-series（推算预测类）；Association和Sequence（序列规则类）。下面将对这六分项进行说明。

“分类”是根据一些变量的数值做计算，再依照结果作分类。“分类”算法是用来预测数据对象的离散类别（Categorical Label）。同时，“分类”算法也可以根据历史经验对已经分类好的数据研究它们的特征，然后再根据这些特征对其他未经分类或是新的数据做预测。

“分类”的主要算法有：

（1）决策树法

决策树归纳是经典的分类算法。大多数决策树算法都采用自顶向下递归的分类方式构造决策树，树的每一个结点上使用信息增益度量选择测试属性，从而可以从生成的决策树中提取规则。

（2）KNN法

KNN（K-Nearest Neighbor）法即K最近邻法，该方法的思路非常简单直观：如果一个样本与在特征空间中的K个最相似（即特征空间中最邻近）样本相接近，那么该样本属于K个样本的所属类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

（3）SVM法

SVM法即支持向量机法（Support Vector Machine），该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。

（4）VSM法

VSM法即向量空间模型法（Vector Space Model），这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量：D=D（T₁，W₁；T₂，W₂；…；T_n，W_n），然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。

（5）Bayes法

Bayes法是一种在已知先验概率和条件概率情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。Bayes方法的薄弱环节在于，实际情况下类别总体的概率分布和各类样本的概率分布函数（或密度函数）常常是不知道的。为了获得它们，就要求样本足够大。另外，Bayes法要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该方法往往在效果上难以达到理论上的最大值。

（6）神经网络法

神经网络分类算法的重点是构造阈值逻辑单元，一个值逻辑单元是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输出一个量。

“聚类”是将数据分类到不同的类或者簇的过程，同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。聚类与分类的不同在于，聚类所要求划分的类是未知的。从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。

聚类分析是一种探索性的分析，在分类过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。

从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合做进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。

主要算法如下：

（1）划分方法（PAM：PArtitioning method）

首先创建K个划分，K为要创建的划分个数；然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括：K-means、K-medoids、CLARA（Clustering LARge Application）、CLARANS（Clustering Large Application based upon RANdomized Search）。(www.xing528.com)

（2）层次方法（Hierarchical method）

创建一个层次以分解给定的数据集。该方法可以分为自上而下（分解）和自下而上（合并）两种操作方式。为弥补分解与合并的不足，层次合并经常要与其他聚类方法相结合，如循环定位。典型的这类方法包括：BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）方法，它首先利用树的结构对对象集进行划分，然后再利用其他聚类方法对这些聚类进行优化；CURE（Clustering Using REprisentatives）方法，它利用固定数目代表对象来表示相应聚类，然后对各聚类按照指定量（向聚类中心）进行收缩；ROCK方法利用聚类间的连接进行聚类合并；CHEMALOEN方法则是在层次聚类时构造动态模型。

（3）基于密度的方法

根据密度完成对象的聚类。它根据对象周围的密度（DBSCAN）不断增长聚类。典型的基于密度方法包括：DBSCAN（Densit-based Spatial Clustering of Application with Noise）：该算法通过不断生长足够高密度区域来进行聚类；它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集；OPTICS（Ordering Points To Identify the Clustering Structure）：并不明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。

（4）基于网格的方法

首先将对象空间划分为有限个单元以构成网格结构，然后利用网格结构完成聚类。主要代表有：STING（STatistical INformation Grid）就是一个利用网格单元保存的统计信息进行基于网格聚类的方法；CLIQUE（Clustering In QUEst）和Wave-Cluster则是一个将基于网格与基于密度相结合的方法。

（5）基于模型的方法

它假设每个聚类的模型并发现适合相应模型的数据。典型的基于模型方法包括：统计方法COBWEB，是一个常用的且简单的增量式概念聚类方法，主要计算离散属性，它的输入对象是采用符号量（属性-值）来加以描述的。采用分类树的形式来创建一个层次聚类；LASSIT是COBWEB的另一个版本，它可以对连续取值属性进行增量式聚类。该方法为每个结点中的每个属性保存相应的连续正态分布（均值与方差）；并利用一个改进的分类能力描述方法。

“回归分析”是确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。它基于观测数据建立变量间适当的依赖关系，以分析数据内在规律，并可用于预报、控制等问题。

“回归分析”主要算法：

回归分析按照涉及变量的多少，分为一元回归和多元回归分析；在线性回归中，按照因变量的多少，可分为简单回归分析和多重回归分析；按照自变量和因变量之间的关系类型，可分为线性回归分析和非线性回归分析。若将范围扩大也可利用Logistic Regression来预测类别变量，特别在广泛运用现代分析技术如类神经网络或决策树理论等分析工具，推估预测的模式已不局限于传统的线性，在预测的功能上大大增加了选择工具的弹性与应用范围的广度。

“时间序列预测”与Regression功能类似，只不过它是用现有的数值来预测未来的数值。两者最大的差异在于Time-Series所分析的数值都与时间有关。Time-Series Forecasting的工具可以处理有关时间的一些特性，譬如时间的周期性、阶层性、季节性以及其他的一些特别因素（如过去与未来的关联性）。

“关联分析”是从大量数据中发现项集之间有趣的关联和相关联系。关联分析的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中的不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。其他的应用还包括价目表设计、商品促销、商品的排放和基于购买模式的顾客划分。

“关联分析”的主要算法：

（1）Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则的频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

该算法的基本思想：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第一步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。

（2）FP-树频集算法

针对Apriori算法的固有缺陷，FP-树频集算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使得一个FP-tree可以放入主存储中。

“序挖掘”是数据中一个特殊存放等差数列的表，该表受数据库系统控制，任何时候数据库系统都可以根据当前记录数大小加上步长来获取到该表下一条记录应该是多少，这个表没有实际意义，常常用来做主键用。Sequence Discovery与Association关系很密切，所不同的是Sequence Discovery中事件的相关是以时间因素来做区隔的。