聚类算法及其评价

姓名：Jyx
班级：csdn人工智能直通车-5期
描述：这是本人在学习人工智能时的学习笔记，加深理解

聚类

1. 聚类是一种非监督学习，聚类需要将一系列样本输入到聚类算法中，学习样本的内在结构。聚类往往不单独存在，而是作为一个大的监督学习算法的一部分存在
2. 聚类的原则。 类内散度最小，类间散度最大
3. 聚类的用途
   3.1 减少计算量。通过对样本分类，以分类标签代替原始向量，大大减少计算量
   3.2 识别离群点。
   3.3 可视化
4. 聚类的要素。特征选择，近邻测度，聚类准则，聚类算法，结果验证，结果判定

近邻测度

1. 距离测度
   
   d(x,y)=||x−y||1pp $$d(x,y)=||x-y|{|}_p^{\frac{1}{p}}$$
2. 余弦相似度
   
   d(x,y)=xTy|x| |y| $$d(x,y)=\frac{x^{T}y}{|x||y|}$$
3. 相关系数
   
   d(x,y)=cov(x,y)δxδy $$d(x,y)=\frac{cov(x,y)}{{\delta }_x{\delta }_y}$$
4. 杰卡德相似系数
   
   d(x,y)=∑k−1i=1aiinx+ny−∑k−1i=1∑k−1j=1aijwhere nx=∑i=1k−1∑j=0k−1aij,ny=∑i=0k−1∑j=1k−1aij $$\begin{gathered} d(x,y)=\frac{\underset{i=1}{\overset{k-1}{\sum }}{a}_{ii}}{n_x+n_y-\underset{i=1}{\overset{k-1}{\sum }}\underset{j=1}{\overset{k-1}{\sum }}{a}_{ij}} \\ where{n}_x=\underset{i=1}{\overset{k-1}{\sum }}\underset{j=0}{\overset{k-1}{\sum }}{a}_{ij},n_y=\underset{i=0}{\overset{k-1}{\sum }}\underset{j=1}{\overset{k-1}{\sum }}{a}_{ij} \end{gathered}$$
   
   其中矩阵 {aij} $\{a_{ij}\}$称为相依表（Contingency table）

聚类算法

1. 分类
   1.1 基于距离的聚类算法
   1.2 基于密度的聚类算法
   1.3 基于连接的聚类算法
2. 基于距离的聚类算法
   2.1 KMeans
   对于一个k类问题，KMeans 的优化目标为
   
   argminC∑i=1k∑x∈Ci(x−μi)2,ui=1nCi∑x∈Cix $$\underset{C}{\arg min}\underset{i=1}{\overset{k}{\sum }}\underset{x\in C_i}{\sum }(x-{\mu }_i{)}^2,u_i=\frac{1}{n_{C_i}}\underset{x\in C_i}{\sum }x$$
   
   这是一个组合优化问题，完全的求解几乎不可能。一般的的思路都是采用贪婪算法，求解局部最优，因此KMeans一般要使用随机初值多尝试几次
   

算法描述

1. 选择随机的聚类中心 μi ${\mu }_i$初始化算法
2. 根据每个样本距离聚类中心的距离对每个样本进行分类, x∈Ci,argmini(x−ui)2 $x\in C_i,\underset{i}{\arg min}(x-u_i{)}^2$
3. 利用分类好的聚类结果更新新的聚类中心 ui=1nCi∑x∈Cix $u_i=\frac{1}{n_{C_i}}\underset{x\in C_i}{\sum }x$
4. 重复2,3步直 ui $u_i$基本不变

2.2 层次聚类
层次聚类来源于生物学的生物分类，一级包含一级，形成一个层次聚类。层次算法并不存在一个优化目标。层次聚类有两种，一种是分裂，一种是聚合。分裂是自顶向下，聚合是自底向上
基本算法描述：

1 将每一个样本初始化一个类 Ci $C_i$
2 选取一对 Cnew=Ci∪Cj，argmini,jd(Ci,Cj) $C_{new}=C_i\cup C_j，\underset{i,j}{\arg min}d(C_i,C_j)$
3 删除原来的 Ci,Cj $C_i,C_j$
4重复2,3直至只有一个类

这样就形成了一个分类树，然后根据某些知识和准则选取每一级作为最后的聚类结果
2.3 吸引力传播
2.4 DBSCAN