聚类分析

K-means算法

1. 算法简要步骤
   1. 随机选取K个样本点（不一定来自样本数据）作为初始的质心
   2. 第一次迭代，将所有样本分配到这K个类中
      1. 对每个样本计算其到两个聚类中心的欧式距离（一般）将其分配到距离最近中心所在簇中
      2. 重新计算聚类中心，将其更新为该簇所有点的平均值。
      3. 计算本次迭代的准则函数$J_c$为新的簇中心的每个属性与簇中所有点属性距离平方的累加
   3. 重复2步骤的1、2、3步，直到聚类中心不再变化或者达到最大迭代次数或者$J_c$足够小

K-中心算法

算法简要步骤

1. 随机选取K个中心点，通过距离(一般选用曼氏距离)划分样本

2. 计算中心点被非中心点代替的总代价

   $C_{jih}=d_{jmin}-d_{j->原中心点}$：$C_{jih}代表O_i被O_h代替，O_j被重新分配的代价，d_{jmin}代表O_i被O_h代替后O_j到所有中心的最小值，d_{j->原中心点}代表O_j到原来中心点的距离$

   $T{C}_{ih}=\sum _{j=1}^A{C}_{jih}，T{C}_{ih}是O_i被O_h替代后的总代价$

3. 选取一个最小代价，使$O_h替代O_i$

4. 重复2,3步骤，直到代价不再减少为止

DBSCAN算法

1. 相关概念

   • 邻域：对于任意给定样本x和距离$\epsilon$,x的邻域是指导样本x的距离不超过$\epsilon$的样本集合
   • 核心对象：若样本x的$\epsilon$邻域内至少包含特定数目(MinPts)的样本，则x是一个核心对象
   • 密度直达：若样本b在a的$\epsilon$邻域内，且a是核心对象，则称样本b由样本a密度直达
   • 密度可达：对于样本a、b，如果存在样例$p_1,p_2,...,p_n$，其中，$p_1=a,p_n=b$，且序列中每一个样本都与它前一个样本密度直达，则称样本a与b密度可达
   • 密度相连：对于样本a和b，若存在样本k是的a与k密度可达，且k与b密度可达，则a与b密度相连

2. 相关算法