机器学习笔记_ 聚类_1：Kmeans+密度聚类_kmeans聚类结合局部密度

相似度

• Minkowski距离- $dist(X,Y)=(\sum\limits_{i=1}^n|x_i-y_i|^p)^\frac{1}{p}$
• 杰卡德相似系数- $J(A,B)=\frac{|A \cap B|}{|A \cup B|}$
• 余弦相似度-$cos(\theta)=\frac{a^Tb}{|a||b|}$
• Person相似系数-$\rho_xy=\frac{cov(X,Y)}{\sigma_x\sigma_y}=\frac{E[(x-\mu_x)(Y-\mu_y)]}{\sigma_x\sigma_y}$
• 相对熵(K-L)- $D(p||q)=\sum\limits_xp(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)}$

• 余弦相似度和Persion相似度

persion是将x,y坐标各自平移到原点后的余弦夹角

kmeans

• 步骤
  
  1. 初始化选择k个类别的中心,$\quad \mu_1,\cdots,\mu_n$
  2. 对于每个样本$x_i$, 将其标记为距离类别中心最近的点 $label_i=arg\min\limits_{1\leq j \leq k}||x_i-\mu_j||$
  3. 每个类别的中心更新为隶属该样本的所有样本的均值 $\mu_j=\frac{1}{|c_j|}\sum\limits_{i \in C_j}x_i$
  4. 重复，直到小于阈值
• 终止条件
  
  1. 迭代次数
  2. 簇中心变化率
  3. 最小平方误差MSE

• kmeans++
  初始化的seed点应该尽可能远

• 算法

  1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
  2. 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
  3. 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
  4. 重复2和3直到k个聚类中心被选出来
  5. 利用这k个初始的聚类中心来运行标准的k-means算法

  从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下

  1. 先从我们的数据库随机挑个随机点当“种子点”
  2. 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
  3. 然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
  4. 重复2和3直到k个聚类中心被选出来
  5. 利用这k个初始的聚类中心来运行标准的k-means算法

层次聚类

DBSCAN

算法: 将簇定义为密度相连的点的最大集合

定义：

1. 对象的 $\varepsilon-$领域: 给定对象在半径$\varepsilon$内的区域
2. 核心对象：给定数目m, 若一个对象的 $\varepsilon-$领域，包含至少m个对象，称为核心对象
3. 直接密度可达: 给定一个对象集合D，若p是在q的 $\varepsilon-$领域，且q是一个核心对象，则称对象p是从q直接密度可达
4. 密度可达
5. 密度相连
6. 簇
7. 噪声

算法:

1. 若一个点p的$\varepsilon-$领域包括多于m个对象，则创建一个p作为核心对象类簇
2. 寻找并合并核心对象密度可达对象
3. 没有新点可以更新簇时，算法结束
4. 包含过少的对象的簇被认为是噪声

密度最大值聚类

• 局部密度 $\rho_i=\sum\limits_j\chi(d_{ij}-d_c)$; $\chi=\{_{0 \quad otherwise}^{1 \quad x<0}$
  $d_c是阶段距离，\rho_i是到对象i的距离小于d_c的对象的个数$
  $d_c选择，使得平均每个点的领居数为所有点的1\% -2\%$

• 高局部密度 $\delta_i=\min\limits_{j:\rho_i >\rho_j}(d_{ij})$
  $局部密度高于对象i的所有对象中，到对象i最近的距离$

• 算法
  
  1. 较大的$\rho_i$和$\delta_i$的点被认为是簇的中心
  2. 较小的$\rho$和较大的$\delta$是异常点
  3. 密度可达距离