title: 机器学习笔记(一)聚类

机器学习笔记(一)聚类

date: 2015-08-09 10:18:55

MachineLearning

1. 基本概念

聚类试图将数据集中的样本划分为若干个通常是不相交子集，每个子集称为一个“簇”，这样每个簇就可以看成是一个潜在的类别，簇的概念语义需要由使用者来把握和命名。

1.1 性能度量

对于聚类结果，我们需要使用一个指标来评价聚类的好坏，聚类性能度量一般有两种，一种是将聚类结果与某个“参考模型”进行比较，称为“外部指标”；另一种是直接考察聚类结果而不利用任何参考模型，称为“内部指标”。

1.2 距离计算

在聚类中我们需要将相似的样本划分到同一个簇中，但是如何判断两个样本是否相似，换句话说如何判断某个样本和一个样本的相似程度要高于另外一个样本，这里就需要我们定义两个样本之间的相似程度或者说距离。

距离需要满足以下三个条件：
- 非负性
- 对称性
- 三角不等式性

1.2.1 Minkovski距离

Minkovski距离是比较常见的一种距离计算公式，计算公式如下：
$dis(x_i,x_j) = ({\sum_{u = 1}^{n}|x_{iu}-x_{ju}|^p})^\frac{1}{p} \quad$,当p=1是该距离变成曼哈顿距离，当p=2时，该距离变成欧式距离。

1.2.2 余弦距离

余弦距离常用来计算文档的相似程度，衡量的是两个向量的方向的重合程度，同方向时距离为1，越相似。计算公式为：
$dis(x_i,y_j) = \frac{\sum_{u = 1}^{n}x_{iu}y_{ju}}{||x_i||||y_i||}$

1.2.3 杰卡德距离

两个集合A和B的交集元素在A、B并集中所占的比例，称为两个集合的杰卡德相似系数，$J(A,B) = \frac{|A \bigcap B|}{|A \bigcup B|}$`,而杰卡德距离则是`$dis(A,B) = 1 - J(A,B) \quad$

2. 几种常见聚类算法

2.1 k-means

k-means是最原始的聚类算法，

2.2 学习向量量化(LVQ)

关键点：训练数据集有类别标记、输出一组刻画聚类簇的向量。

假设最后的聚类结果是Q个类，那么最后生成一个Q维向量表示Q个聚类；

迭代时：
如果样本$x_i$和最近的原型向量类标记相同，那么更新原型向量为：
$p = p^* + \eta*(x_i - p^*)$

否则，更新原型向量为：
$p = p^* - \eta*(x_i - p^*)$，这里的$\eta$为为学习率，取值范围为(0,1)

2.3 高斯混合聚类

关键点：判断数据属于高斯混合模型中的哪一个高斯分布；首先由训练集学习出高斯混合模型中的参数，然后预测的时候计算新样本的后验概率，判断该新样本属于哪一个高斯模型，即属于哪一个聚类簇。

2.4 基于密度的聚类—DBSCAN

邻域、核心对象、密度直达、密度可达、密度相连
簇：x密度可达的所有样本点组成的集合即时一个簇。
算法描述：
1.根据邻域找出所有核心对象
2.根据核心对象集合、未访问集合生成聚类簇

---未完待续

2.5 层次聚类

2.6 谱聚类