数据挖掘之聚类
文章大纲：
聚类概念
聚类应用
聚类目标
相似性计算方法
聚类方法分类
划分方法
1. 概念
按照数据之间的相似性，对数据集进行分组或分类（簇, cluster）的过程；试图使类内差距最小化，类间差距最大化。
利用聚类结果，可以提取数据集中隐藏的信息，对未来数据进行预测和分类。
特点：处理巨大的、复杂的数据集
2. 应用
（1）作为其它算法的预处理步骤：利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以获得进一步的有用信息。
（2）作为一个独立的工具来获得数据的分布情况：聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。
（3）聚类分析可以完成孤立点挖掘：许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。
3. 聚类分析的目标
聚类分析的目标就是形成的数据簇，并且满足下面两个条件：
--一个簇内的数据尽量相似（highintra-classsimilarity）；
--不同簇的数据尽量不相似（lowinter-classsimilarity）。
衡量一个聚类分析算法质量，依靠：
--相似度测量机制是否合适。
--是否能发现数据背后潜在的、手工难以发现的类知识。
4. 相似性度量
（1）距离相似性度量
（2）角度相似性度量
Similarity is expressed in terms of a distance function, which is typically metric: d(i, j)；
不同类型的数据，距离函数的定义也有所不同。
4.1 数据类型及其类内度量方式
（1）区间标度
区间标度是一个粗略线性标度的连续度量
eg：重量和高度，经度和纬度坐标以及大气温度。
明考斯基距离：
名氏距离
If q=1,dis曼哈顿距离(Manhattan distance)：
曼哈顿距离
If q=2,dis欧几里得距离Euclidean distance:
欧式距离
（2）二元变量
两种状态：0、1.
A。 对称型
简单匹配系数：
计算公式
数据表
B。非对称型
根据惯例，我们将比较重要的输出结果，通常也是出现几率较小的结果编码为1
给定两个不对称的二元变量，两个都取值1的情况被认为比两个都取值0的情况更有意义。因此，这样的二元变量被认为好像只有一个状态。
Jaccard系数：
计算中，负匹配的数目d认为是不重要的，被忽略；
计算公式
（3）标称型、序数型和比例标度型
（4）混合型
4.2 类间度量
设有两个类Ca和Cb，它们分别有m和h个元素，它们的中心分别为γa和γb。设元素x∈Ca，y∈Cb，这两个元素间的距离通常通过类间距离来刻画，记为D(Ca,Cb)。
两个聚类p和q：
（1）最短距离法
（2）最长距离法
（3）重心法
（4）类平均法
4.3 其他影响
特征选取不当---聚类无效
特征选取不足---误分类
模式特征坐标单位的选取也会强烈地影响聚类结果
尺度问题：标准化
标准化1
标准化2
标准化3
标准化4
4.4 角度相似性度量
角度度量
特点
5. 聚类方法分类
（1）按照聚类的标准，聚类方法可分为如下两种：
统计聚类方法：这种聚类方法主要基于对象之间的几何距离的。
概念聚类方法：概念聚类方法基于对象具有的概念进行聚类。
（2）按照聚类算法所处理的数据类型，聚类方法可分为三种：
数值型数据聚类方法：所分析的数据的属性只限于数值数据。
离散型数据聚类方法：所分析的数据的属性只限于离散型数据。
混合型数据聚类方法：能同时处理数值和离散数据。
（3）按照聚类的尺度，聚类方法可被分为以下三种：
基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度，如k-means、k-medoids、BIRCH、CURE等算法。
基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。
基于互连性(Linkage-Based)的聚类算法：通常基于图或超图模型。高度连通的数据聚为一类。
（4）按照聚类分析算法的主要思路，可被归纳为如下几种：
划分法（Partitioning Methods）：基于一定标准构建数据的划分。属于该类的聚类方法有：k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。
层次法（Hierarchical Methods）：对给定数据对象集合进行层次的分解。
密度法（density-based Methods）：基于数据对象的相连密度评价。
网格法（Grid-based Methods）：将数据空间划分成为有限个单元（Cell）的网格结构，基于网格结构进行聚类。
模型法（Model-Based Methods）：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。
6. 划分方法
给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，k<=n。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件：
a。每一个簇至少包含一个对象。
b。每一个对象属于且仅属于一个簇。
对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。
启发式方法: k-平均算法和k-中心点算法
k-均值算法:每个簇用该簇中对象的平均值来表示。
k-中心点算法:每个簇用接近聚类中心的一个对象来表示
k-means算法
（1）步骤
首先将所有对象随机分配到k个非空的簇中
计算每个簇的平均值，并用该平均值代表相应的簇。
根据每个对象与各个簇中心的距离，分配给最近的簇。
然后转第二步，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。
（2）算法
k-means算法
（3）主要优点
是解决聚类问题的一种经典算法，简单、快速。
对处理大数据集，该算法是相对可伸缩和高效率的。
当结果簇是密集的而簇间区别是明显的时，它的效果较好。
（4）主要缺点：
必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。
不适合于发现非凸面形状的簇或者大小差别很大的簇。
对于“躁声”和孤立点数据是敏感的，因为簇的中心是通过计算数据的平均值得到的，这些数据的存在会使聚类的中心发生很大的偏移。
