西瓜书学习笔记-聚类
聚类
1 聚类任务
聚类的目标是通过对无标记训练样本的学习来揭示数据内在性质及规律，为进一步的数据分析提供基础。
聚类过程仅能自动生成簇，但是簇所对应的概念语义需要由使用者来定义。
2 性能度量
聚类性能度量也叫做聚类“有效性指标”。聚类的目的是使得簇内相似度高且簇间相似度低。
聚类的性能度量有两类：
一类是将聚类结果与某个参考模型相比较，称为外部指标。
另一类是直接考察聚类结果，称为内部指标。
SS中包含了在C中属于相同簇，在C中也属于相同簇的样本集合。
SD中包含了在C中属于相同簇，在C中不属于相同簇的样本集合。
...
显然，每个样本对（xi，xj）仅能出现在一个集合中，所以：
a+b+c+d = m（m-1）/2
现在，上述指标取值在[0,1]之间，取值越大越好。
avg描述了簇内样本间平均距离。
diam簇内样本间最大距离。
dmin描述了CiCj两个簇内，最近样本的距离。
dcen描述了CiCj两个簇中心的距离。
3 距离计算
我们通常将属性划分为连续属性和离散属性。然而，在讨论距离计算的时候，属性上是否定义了序关系更加重要。例如定义域为{1，2，3}这样的离散属性与连续属性的性质更加接近，这样的属性称为有序属性。而定义域为{飞机，汽车，火车}这样的离散属性则不能直接在属性上计算距离，称为无序属性。
对于无序属性可以使用VDM距离
mu,a表示为属性u上取值为a的样本数
mu,a,i表示第i个样本簇中，属性u上取值为a的样本数
令k为样本簇数，属性u上的两个离散取值a，b的VDM距离为：
4 原型聚类
此类算法假设聚类结构能够通过一组原型刻画，通过算法先对原型进行初始化，随后通过不断的迭代更新求解。
- k均值算法
其过程是重复下面三个步骤：
随机选择k个样本点作为初始均值向量。
将其余样本划入距离最近的簇中。
更新均值向量。
- 学习向量量化
与一般聚类算法不同的是，(LVQ)这种算法数据样本带有监督信息标记，学习过程借助监督信息来辅助聚类。
接受代标记的数据集D和原型向量个数k，以及初始化的原型向量标记ti,ti∈Y,i=1,2,…,k，学习率参数η∈(0,1)。输出为原型向量q1,q2,…,qk。
我们假设样本集为
D={(x1,y1),(x2,y2),…,(xm,ym)}
每个样本均由 n个属性描述
xj=(xj1,xj2,…,xjn)
yj∈Y,j=1,2,…,m
算法主要步骤包括：初始化原型向量；迭代优化，更新原型向量。
具体来说，主要是：
1、对原型向量初始化，随机选择一个数据向量作为 qj的初始值；
2、从数据集D 中任意选择一个样本 xj，找到与此样本距离最近的原型向量，假设为qi ；
3、如果xj的标记yj 与qi的标记ti相等，即 yj=ti，则令q′=qi+η⋅(xj−qi)
否则，q′=qi−η⋅(xj−qi)
4、更新原型向量：qi=q′
重复上述过程直到到达预定次数或下降小于某阈值。
- 高斯混合聚类
高斯混合使用概率模型来表达聚类原型
μ是n维均值向量，Σ是n*n的协方差矩阵，高斯分布由μ和Σ两个参数确定。
根据上式，我们要从GMM分布中随机的取一个点的话，可以分为两步：
首先随机的从K个组件中选一个，每个组件被选中的概率就是其混合系数α。
然后考虑从这个组件中选取一个点，这时已经回到了普通高斯分布，转换为了已知的问题。
GMM做聚类时，我们假定数据由GMM生成，那么我们只需要根据数据推导出GMM的概率分布即可。GMM的K个组件就对应了K个簇。
假定我们有N个数据点，并且假设他们服从分布P（x），现在要确定的是里面的一些参数，对于GMM而言，需要确定的是π，Σ，μ。我们需要找到一组参数，使得概率分布生成给定数据点的概率最大。
概率就等于似然函数的值：
取对数得到
对于每个数据x而言，其后验概率为
而后循环更新参数即可。
5 密度聚类
密度聚类假设聚类结构通过样本分布的紧密程度来确定，从样本的密度去考虑样本的可连接性。
DBSCAN是密度聚类的代表算法。
主要定义了以下几个概念：
对于给定的数据集D = {x1，x2，x3...xm}
ε-邻域：对于任意xi，其ε-邻域包含D中所有与xi距离不大于ε的样本点。
核心对象：若xi的ε-邻域至少包含MinPts个样本，则称其为核心对象。
密度直达：xj位于xi的ε-邻域，则称xj可由xi密度直达。
密度可达：A由B密度直达，B由C密度直达，则称A由C密度可达。
密度相连：A、B皆有C密度可达，则称AB密度相连。
DBSCAN中的簇定义为：由密度可达导出的最大密度相连样本集合。
算法流程为：
从所有样本点中，根据ε和MinPts找出所有核心对象作为种子。
以任意核心为起点，找到所有密度可达对象生成簇。
直到所有的样本全部被访问。
6 层次聚类
层次聚类试图从不同的层次对数据集进行划分，进而形成树状结构。
其策略有自下而上和自上而下两种。
AGNES为自下而上的层次聚类算法。
它将数据集中的每一个数据点作为一个初始簇，然后在算法的运行中将最近的两个簇进行合并，知道全部合并结束或者达到某个终止条件。
