[科普中国]-聚类分析

聚类分析指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为。

聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域，包括数学，计算机科学，统计学，生物学和经济学。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。

区别聚类与分类的不同在于，聚类所要求划分的类是未知的。

聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。

从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。

从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。

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

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

定义依据研究对象（样品或指标）的特征，对其进行分类的方法，减少研究对象的数目。

各类事物缺乏可靠的历史资料，无法确定共有多少类别，目的是将性质相近事物归入一类。

各指标之间具有一定的相关关系。

聚类分析(cluster analysis)是一组将研究对象分为相对同质的群组(clusters)的统计分析技术。 聚类分析区别于分类分析(classification analysis) ，后者是有监督的学习。

变量类型：定类变量、定量（离散和连续）变量

聚类方法1,层次聚类（Hierarchical Clustering）

合并法、分解法、树状图

2. 非层次聚类

划分聚类、谱聚类

聚类方法特征：

聚类分析简单、直观。

聚类分析主要应用于探索性的研究，其分析的结果可以提供多个可能的解，选择最终的解需要研究者的主观判断和后续的分析；

不管实际数据中是否真正存在不同的类别，利用聚类分析都能得到分成若干类别的解；

聚类分析的解完全依赖于研究者所选择的聚类变量，增加或删除一些变量对最终的解都可能产生实质性的影响。

研究者在使用聚类分析时应特别注意可能影响结果的各个因素。

异常值和特殊的变量对聚类有较大影响
当分类变量的测量尺度不一致时，需要事先做标准化处理。

当然，聚类分析不能做的事情是：
自动发现和告诉你应该分成多少个类——属于非监督类分析方法

期望能很清楚的找到大致相等的类或细分市场是不现实的；

样本聚类，变量之间的关系需要研究者决定；

不会自动给出一个最佳聚类结果；

我这里提到的聚类分析主要是谱系聚类（hierarchical clustering）和快速聚类（K-means）、两阶段聚类（Two-Step）；

根据聚类变量得到的描述两个个体间（或变量间）的对应程度或联系紧密程度的度量。
可以用两种方式来测量：
1、采用描述个体对（变量对）之间的接近程度的指标，例如“距离”，“距离”越小的个体（变量）越具有相似性。

2、采用表示相似程度的指标，例如“相关系数”，“相关系数”越大的个体（变量）越具有相似性。

计算聚类——距离指标D(distance)的方法非常多：按照数据的不同性质，可选用不同的距离指标。欧氏距离(Euclidean distance)、欧氏距离的平方(Squared Euclidean distance)、曼哈顿距离(Block)、切比雪夫距离(Chebychev distance)、卡方距离(Chi-Square measure) 等；相似性也有不少，主要是皮尔逊相关系数了！

聚类变量的测量尺度不同，需要事先对变量标准化；

聚类变量中如果有些变量非常相关，意味着这个变量的权重会更大

欧式距离的平方是最常用的距离测量方法；

聚类算法要比距离测量方法对聚类结果影响更大；

标准化方法影响聚类模式：

变量标准化倾向产生基于数量的聚类；

样本标准化倾向产生基于模式的聚类；

一般聚类个数在4－6类，不易太多，或太少；1

统计量群重心

群中心

群间距离

分层步骤定义问题与选择分类变量

聚类方法

确定群组数目

聚类结果评估

结果的描述、解释

K-means属于非层次聚类法的一种

（1）执行过程

初始化：选择（或人为指定）某些记录作为凝聚点

循环：

按就近原则将其余记录向凝聚点凝集

计算出各个初始分类的中心位置（均值）

用计算出的中心位置重新进行聚类

如此反复循环，直到凝聚点位置收敛为止

（2）方法特点

通常要求已知类别数

可人为指定初始位置

节省运算时间

样本量大于100时有必要考虑

只能使用连续性变量

过程特点：

处理对象：分类变量和连续变量

自动决定最佳分类数

快速处理大数据集

前提假设：

变量间彼此独立

分类变量服从多项分布，连续变量服从正态分布

模型稳健

算法原理第一步：逐个扫描样本，每个样本依据其与已扫描过的样本的距离，被归为以前的类，或生成一个新类

第二步，对第一步中各类依据类间距离进行合并，按一定的标准，停止合并

判别分析 Discriminant Analysis

介绍： 判别分析

分类学是人类认识世界的基础科学。聚类分析和判别分析是研究事物分类的基本方法，广泛地应用于自然科学、社会科学、工农业生产的各个领域。

判别分析DA

概述

DA模型

DA有关的统计量

两组DA

案例分析

判别分析

判别分析是根据表明事物特点的变量值和它们所属的类，求出判别函数。根据判别函数对未知所属类别的事物进行分类的一种分析方法。核心是考察类别之间的差异。

判别分析

不同：判别分析和聚类分析不同的在于判别分析要求已知一系列反映事物特征的数值变量的值，并且已知各个体的分类。

DA适用于定类变量（因）、任意变量（自）

两类：一个判别函数；

多组：一个以上判别函数

DA目的

建立判别函数

检查不同组之间在有关预测变量方面是否有显著差异

决定哪个预测变量对组间差异的贡献最大

根据预测变量对个体进行分类

分析模型要先建立判别函数 Y=a1x1+a2x2+...anxn，其中:Y为判别分数(判别值)，x1 x2...xn为反映研究对象特征的变量，a1 a2...an为系数

有关统计典型相关系数

特征值

Wilk's (0, 1) = SSw/SSt for X

组重心

分类矩阵

两组判别定义问题

估计DA函数系数

确定DA函数的显著性

解释结果

评估有效性

定义问题

判别分析的第一步

第二步就是将样本分为：

分析样本

验证样本

估算判别函数系数

直接法（direct method）就是同时用所有的预测变量估计判别函数，此时每个自变量都包括在内，而不考虑其判别能力。这种方法适用于前期研究或理论模型显示应包括哪些自变量的情况。

逐步判别分析（stepwise discriminant analysis），预测变量依据其对组别的判别能力被逐步引入。

确定显著性

零假设：总体中各组所有判别函数的均值相等。

特征值

典型相关系数

Wilk‘s (0, 1) 转换成卡方值检验

见travel.spo

解释结果

系数的符号无关紧要，但能够表示每个变量对判别函数值的影响，以及与特定组的联系。

我们可以通过标准化判别函数系数的绝对值初步判断变量的相对重要性。

通过考察结构相关系数，也可以对预测变量的相对重要性进行判断。

组重心

评估判别分析的有效性

根据分析样本估计出的判别权数，乘以保留样本中的预测变量值，就得出保留样本中每个样本的判别分。

可以根据判别分及适当的规则划分为不同的组别。

命中率（hit ratio）或称样本正确分类概率，就是分类矩阵对角线元素之和与总样本数的比例。

比较样本正确分类百分比与随机正确分类百分比。

因子分析模型因子分析模型（FA）

基本思想

因子分析模型

FA的基本思想

“因子分析”于1931年由Thurstone提出，概念起源于Pearson和Spearmen的统计分析

FA用少数几个因子来描述多个变量之间的关系，相关性较高的变量归于同一个因子；

FA利用潜在变量或本质因子（基本特征）去解释可观测变量

FA模型

X1=a11F1+a12F2+ …+a1pFp+v1

X2=a21F1+a22F2+ …+a2pFp+v2 X=AF+V

Xi=ai1F1+ai2F2+ …+aipFp+vi

Xm=ap1F1+ap2F2+ …+ampFm+vm

Xi — 第i个标准化变量

aip — 第i个变量对第p个公因子的标准回归系数

F — 公因子

Vi — 特殊因子

公因子模型

F1=W11X1+W12X2+ …+W1mXm

F2=W21X1+W22X2+ …+W2mXm

Fi=Wi1X1+Wi2X2+ …+WimXm

Fp=Wp1X1+Wp2X2+ …+WpmXm

Wi — 权重，因子得分系数

Fi — 第i个因子的估计值（因子得分）

有关统计量

Bartlett氏球体检验:各变量之间彼此独立

KMO值：FA合适性

因子负荷：相关系数

因子负荷矩阵

公因子方差（共同度）

特征值

方差百分比（方差贡献率）

累计方差贡献率

因子负荷图

碎石图

FA步骤

定义问题

检验FA方法的适用性

确定因子分析方法

因子旋转

解释因子

计算因子得分

注意事项

样本量不能太小

变量相关性

公因子有实际意义

主要应用商业聚类分析被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。

聚类分析是细分市场的有效工具，同时也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场，并作为多元分析的预处理。

生物聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识

地理聚类能够帮助在地球中被观察的数据库商趋于的相似性

保险行业聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组

因特网聚类分析被用来在网上进行文档归类来修复信息

电子商务聚类分析在电子商务中网站建设数据挖掘中也是很重要的一个方面，通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，可以更好的帮助电子商务的用户了解自己的客户，向客户提供更合适的服务。

主要步骤1. 数据预处理，

2. 为衡量数据点间的相似度定义一个距离函数，

3. 聚类或分组，

4. 评估输出。

数据预处理包括选择数量，类型和特征的标度，它依靠特征选择和特征抽取，特征选择选择重要的特征，特征抽取把输入的特征转化为一个新的显著特征，它们经常被用来获取一个合适的特征集来为避免“维数灾”进行聚类，数据预处理还包括将孤立点移出数据，孤立点是不依附于一般数据行为或模型的数据，因此孤立点经常会导致有偏差的聚类结果，因此为了得到正确的聚类，我们必须将它们剔除。

既然相类似性是定义一个类的基础，那么不同数据之间在同一个特征空间相似度的衡量对于聚类步骤是很重要的，由于特征类型和特征标度的多样性，距离度量必须谨慎，它经常依赖于应用，例如，通常通过定义在特征空间的距离度量来评估不同对象的相异性，很多距离度都应用在一些不同的领域，一个简单的距离度量，如Euclidean距离，经常被用作反映不同数据间的相异性，一些有关相似性的度量，例如PMC和SMC，能够被用来特征化不同数据的概念相似性，在图像聚类上，子图图像的误差更正能够被用来衡量两个图形的相似性。

将数据对象分到不同的类中是一个很重要的步骤，数据基于不同的方法被分到不同的类中，划分方法和层次方法是聚类分析的两个主要方法，划分方法一般从初始划分和最优化一个聚类标准开始。Crisp Clustering，它的每一个数据都属于单独的类；Fuzzy Clustering，它的每个数据可能在任何一个类中，Crisp Clustering和Fuzzy Clusterin是划分方法的两个主要技术，划分方法聚类是基于某个标准产生一个嵌套的划分系列，它可以度量不同类之间的相似性或一个类的可分离性用来合并和分裂类，其他的聚类方法还包括基于密度的聚类，基于模型的聚类，基于网格的聚类。

评估聚类结果的质量是另一个重要的阶段，聚类是一个无管理的程序，也没有客观的标准来评价聚类结果，它是通过一个类有效索引来评价，一般来说，几何性质，包括类间的分离和类内部的耦合，一般都用来评价聚类结果的质量，类有效索引在决定类的数目时经常扮演了一个重要角色，类有效索引的最佳值被期望从真实的类数目中获取，一个通常的决定类数目的方法是选择一个特定的类有效索引的最佳值，这个索引能否真实的得出类的数目是判断该索引是否有效的标准，很多已经存在的标准对于相互分离的类数据集合都能得出很好的结果，但是对于复杂的数据集，却通常行不通，例如，对于交叠类的集合。

算法聚类分析是数据挖掘中的一个很活跃的研究领域，并提出了许多聚类算法。传统的聚类算法可以被分为五类：划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。

1 划分方法(PAM:PArtitioning method) 首先创建k个划分，k为要创建的划分个数；然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括：

k-means,k-medoids,CLARA(Clustering LARge Application),

CLARANS(Clustering Large Application based upon RANdomized Search).

FCM

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:是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量（属性-值）对来加以描述的。采用分类树的形式来创建一个层次聚类。

CLASSIT是COBWEB的另一个版本.。它可以对连续取值属性进行增量式聚类。它为每个结点中的每个属性保存相应的连续正态分布（均值与方差）；并利用一个改进的分类能力描述方法，即不象COBWEB那样计算离散属性（取值）和而是对连续属性求积分。但是CLASSIT方法也存在与COBWEB类似的问题。因此它们都不适合对大数据库进行聚类处理.

传统的聚类算法已经比较成功的解决了低维数据的聚类问题。但是由于实际应用中数据的复杂性，在处理许多问题时，现有的算法经常失效，特别是对于高维数据和大型数据的情况。因为传统聚类方法在高维数据集中进行聚类时，主要遇到两个问题。①高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零；②高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此在高维空间中无法基于距离来构建簇。

高维聚类分析已成为聚类分析的一个重要研究方向。同时高维数据聚类也是聚类技术的难点。随着技术的进步使得数据收集变得越来越容易，导致数据库规模越来越大、复杂性越来越高，如各种类型的贸易交易数据、Web 文档、基因表达数据等，它们的维度（属性）通常可以达到成百上千维，甚至更高。但是，受“维度效应”的影响，许多在低维数据空间表现良好的聚类方法运用在高维空间上往往无法获得好的聚类效果。高维数据聚类分析是聚类分析中一个非常活跃的领域，同时它也是一个具有挑战性的工作。高维数据聚类分析在市场分析、信息安全、金融、娱乐、反恐等方面都有很广泛的应用。