Cluster：
Cluster: a collection of data objects
Similar to one another within the same cluster
Dissimilar to the objects in other clusters
Cluster analysis：根据数据的特征找出数据间的相似性，将相似的数据分成一个类。
Unsupervised learning: no predefined classes
Examples of Clustering Applications：
Marketing:帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征
Land use:在地球观测数据库中用以确定相似地区
City-planning:根据房子的类型，价值，和地理位置对一个城市中的房屋分组
好的聚类方法能产生高质量的聚类。所谓高质量，指：类中的对象高度相似，类间的对象高度不相似
聚类方法的好坏也可以按照它是否能够发现更多的隐含模式来度量
Dissimilarity/Similarity metric: 相似性通常用距离函数来表示，typically metric: d(i, j)
距离函数的定义对于不同的数据通常是不同的，如：interval-scaled、Boolean、Categorical、ordinal ratio、vector variables.
根据应用背景或者数据语义的不同，对不同的变量可以适当加权
Data matrix（数据矩阵，或称为对象属性结构）：用p个变量（也称为属性）来表现n个对象，例如用年龄，身高，性别，种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者看为n*p维（n个对象*p个属性）的矩阵。
Dissimilarity matrix（相异度矩阵，或称为对象-对象结构）：存储n个对象两两之间的近似性，表现形式是一个n*n维的矩阵。
d(i,j)是对象i和对象j之间相异性的量化表示，通常它是一个非负的数值，当对象i 和j越相似，其值越接近0；两个对象越不同，其值越大。既然d(i,j) = d(j,i)，而且d(i,i)=0，可以得到如下矩阵：
聚类分析中的数据类型：
nInterval-scaled variables（区间标度 ）
nBinary variables（二元变量 ）
nNominal, ordinal, and ratio variables（标称型、序数型和比例标度型 ）
nVariables of mixed types（混合型 ）
区间标度变量的典型的例子包括重量和高度，经度和纬度坐标，以及大气温度等。
选用的度量单位将直接影响聚类分析的结果。例如，将高度的度量单位由“米”改为“英尺”，或者将重量的单位由“千克”改为“磅”，可能产生非常不同的聚类结构。
为了避免对度量单位选择的依赖，数据应当标准化。为了实现度量值的标准化，一种方法是将原来的度量值转换为无单位的值。
给定一个变量f的度量值，可以进行如下的变换：
计算平均的绝对偏差（mean absolute deviation）Sf
其中：
计算标准化的度量值，或z-score：
计算对象间的相异度
对象间的相异度（或相似度）是基于对象间的距离来计算的
通常使用明考斯基距离：
其中i = (xi1, xi2, …, xip) ，j = (xj1, xj2, …, xjp) 分别代表两个p-维的对象, q是一个正整数
q = 1的时候，d称为曼哈顿距离
当q =2表示欧几里得距离
距离函数具有如下属性：
1．d（i，j）≥0：距离是一个非负的数值。
2．d（i，i）=0：一个对象与自身的距离是0。
3．d（i，j）= d（j，i）：距离函数具有对称性。
4．d（i，j）≤ d（i，h）+d（h，j）：从对象I到对象j的直接距离不会大于途径任何其他对象的距离。
可以对每个变量根据其重要性赋予一个权重
二元变量只有两个状态：0或1
0表示该变量为空、1表示该变量存在
例如，给出一个描述病人的变量smoker，1表示病人抽烟，而0表示病人不抽烟。
像处理区间标度变量一样来对待二元变量会误导聚类结果，所以要采用特定的方法来计算其相异度。
二元变量的可能性
假设所有的二元变量有相同的权重，得到一个两行两列的可能性表
a是对对象i和j值都为1的变量的数目，b是在对象i中值为1，在对象j中值为0的变量的数目，是在对象i中值为0，在对象j中值为1的变量的数目，是在对象i和j中值都为0的变量的数目。变量的总数是a+b+c+d
对称的二元变量
如果二元变量的两个状态有相同的权重, 那么该二元变量是对称的，也就是两个取值0或1没有优先权。例如，“性别”
基于对称二元变量的相似度称为恒定的相似度，即当一些或者全部二元变量编码改变时，计算结果不会发生变化。
对恒定的相似度来说，评价两个对象i和j之间相异度的最著名的系数是简单匹配系数，其定义如下：
不对称的二元变量
如果两个状态的输出不是同样重要，那么该二元变量是不对称的。例如一个疾病检查的肯定和否定的结果。根据惯例，我们将比较重要的输出结果，通常也是出现几率较小的结果编码为1，而将另一种结果编码为0。
给定两个不对称的二元变量，两个都取值1的情况（正匹配）被认为比两个都取值0的情况（负匹配）更有意义。基于这样变量的相似度被称为非恒定的相似度。
对非恒定的相似度，最著名的评价系数是Jaccard系数，在它的计算中，负匹配的数目被认为是不重要的，因此被忽略。
标称型、序数型、比例标度型 略
聚类算法
1、基于划分的方法
给定一个n个对象或元组的数据库，划分方法构建数据的k个划分，每个划分表示一个聚类，并且k<=n。也就是说，它将数据划分为k个组，同时满足如下的要求：（1）每个组至少包含一个对象；（2）每个对象必须属于且只属于一个组。
2、基于层次的聚类方法
主要思想是把数据对象排列成一个聚类树，在需要的层次上对其进行切割，相关联的部分构成一个cluster。基于层次的聚类方法有两种类型：
（1）聚合层次聚类。最初每个对象是一个cluster，然后根据它们之间的相似性，对这些原子的cluster进行合并。大多数层次方法属于这一类，它们的主要区别是cluster之间的相似性的定义不同。
（2）划分层次聚类，它与上面的过程正好相反。
用户可以指定算法终止的条件，例如，聚类的个数或每个cluster的半径低于某个阀值。
n弱点在于合并或分裂点的选取问题，因为一组对象一旦合并或分裂，就不能有undo的操作
时间复杂度为O（N2），对于处理大数据量有性能问题。
3、基于密度的方法
绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现凸状的簇，而在发现任意形状的簇上遇到了困难。
基于密度的聚类方法的主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪音”数据，发现任意形状的簇。
4、基于方格的方法
把多维数据空间划分成一定数目的单元，然后在这种数据结构上进行聚类操作。
该类方法的特点是它的处理速度，因为其速度与数据对象的个数无关，而只依赖于数据空间中每个维上单元的个数。
5、基于模型的方法
神经网络方法
基于统计的方法
K-means算法
K-Means方法是MacQueen1967年提出的。给定一个数据集合X和一个整数K（£n），K-Means方法是将X分成K个聚类并使得在每个聚类中所有值与该聚类中心距离的总和最小。
K-Means聚类方法分为以下几步：
[1] 给K个cluster选择最初的中心点，称为K个Means。
[2] 计算每个对象和每个中心点之间的距离。
[3] 把每个对象分配给距它最近的中心点做属的cluster。
[4] 重新计算每个cluster的中心点。
[5] 重复2，3，4步，直到算法收敛。
Example：
把14个人分成3组，只有一个属性，年龄，初始的centroids是1, 20, , 40
下边的表是完成步骤1，2后的结果
重新计算centroid ，得到5,12, 和 48
重新计算每个实例与3个Cluster的距离
P5 更接近 C2
需要重新计算C1 和 C2的centroid，C3 没有变化不需要重新计算
3个Cluster的centroid 是4,11, 和 48
计算每个实例到Cluster的距离
P4 更接近 C2
需要重新计算C1 和 C2的centroid，C3 没有变化不需要重新计算
3个Cluster的 centroid 是3,10和 48
计算每个实例到Cluster的距离
没有任何变化
算法不再迭代
K-Means方法具有下面的优点
（1）对于处理大数据量具有可扩充性和高效率。算法的复杂度是O（tkn），其中n是对象的个数，k是cluster的个数，t是循环的次数，通常k，t<<n。
（2）可以实现局部最优化,如果要找全局最优，可以用退火算法或者遗传算法
K-Means方法也有以下缺点
（1）Cluster的个数必须事先确定，在有些应用中，事先并不知道cluster的个数。
（2）K个中心点必须事先预定，而对于有些字符属性，很难确定中心点。
（3）不能处理噪音数据。
（4）不能处理有些分布的数据（例如凹形）
K-Means方法的变种
(1)K-Modes ：处理分类属性
(2)K-Prototypes：处理分类和数值属性
(3)K-Medoids
它们与K-Means方法的主要区别在于：
（1）最初的K个中心点的选择不同。
（2）距离的计算方式不同。
（3）计算cluster的中心点的策略不同。
Classification vs.Clustering
Classification： Supervised learning. Learns a method for predicting the instance class frompre-labeled (classified) instances
Unsupervised learning：Finds “natural” grouping of instances given un-labeled data
