『数据挖掘十大算法 』笔记三：K-means

2021-10-19 15:59:47 浏览数 (1)

数据挖掘Top 10算法

C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART

K-means算法:

算法流程

输入：聚类个数k，以及包含 n个数据对象的数据库。 输出：满足方差最小标准的k个聚类。 算法流程： 1. 从 n个数据对象任意选择 k 个对象作为初始聚类中心。 2. 若果不满足终止条件，到3，否则到6。 3. 根据每个聚类的中心对象，计算每个对象与这些中心对象的距离；并根据距离最小的中心重新对相应对象划分新的类，例如Pi离中心Si最近，则输入Si点群。 4. 重新计算每个（有变化）聚类的中心对象。 5. 若满足终止条件到6，否则循环(2)到(3)直到每个聚类满足终止条件。 6. 输出聚类结果。

算法很简单，其中主要的就是求中心点算法. 由于随机选择初始质心，所以可能两次聚类结果完全不同。

求中心点算法

求点群中心点的算法你可以很简的使用各个点的各自维度的平均值。为什么这么取值可以见后面聚类算法评估标准的SSE函数求偏导。

距离公式

Minkowski Distance公式

d_{ij} = sqrt[lambda]{sumlimits_{k=1}^n {|x_{ik}-x_{jk}|}^lambda}

n是其维度。λ可以随意取值，可以是负数，也可以是正数，或是无穷大。

Euclidean Distance公式

也就是Minkowski Distance公式λ=2的情况

d_{ij} = sqrt[2]{sumlimits_{k=1}^n {|x_{ik}-x_{jk}|^lambda}}

CityBlock Distance公式

也就是Minkowski Distance公式λ=1的情况

d_{ij} = {sumlimits_{k=1}^n {|x_{ik}-x_{jk}|}}

向量表示法

cos(theta) = frac{a·b}{|a||b|} = frac{sum_{k=1}^n x_{1k}*x_{2k}}{sqrt[2]{sum_{k=1}^n x_{1k}^2 sum_{k=1}^n x_{2k}^2}}

迭代终止条件：

  1. 比较相邻的2轮迭代结果，在2轮过程中移动的非质心点的个数，设置移动非质心点占比全部点数的最小比例值，如果达到则算法终止
  2. 为了防止k-means聚类过程长时间不收敛，设置最大迭代次数，如果达到最大迭代次数还没有达到上述条件，则也终止计算 3。 如果相邻2次迭代过程，质心没有发生变化，则算法终止，这是最强的终止约束条件。能够满足这种条件，几乎是不可能的，除非两次迭代过程中没有非质心点重新指派给到另一个不同的质心。

K-Means主要缺陷

  • K的选择。
    • K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目K）
  • 聚类中心的选择。
    • K-Means算法需要用初始随机种子点选择初始聚类中心。这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means 算法可以用来解决这个问题，其可以有效地选择初始点）

    ​

K-Means 算法

  1. 先从我们的数据库随机挑个随机点当“种子点”。
  2. 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
  3. 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大（一种方法：再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。）
  4. 重复第（2）和第（3）步直到所有的K个种子点都被选出来。
  5. 进行K-Means算法。

k-means算法评价标准

聚类算法目标是使得同一个簇的差异很小，不同簇之间的数据差异最大化。

一般采用误差平方和作为衡量的目标函数SSE，上面提到的目标函数f就是SSE也是误差平方和

SSE = sumlimits_{i=1}^k sumlimits_{x in C_i} D(c_i,x)

其中

c_i

表示聚类的中心点，x为数据点，D(c,x)为距离公式，一般λ为2.

D(c,x) =d_{cx} = sqrt[lambda]{sumlimits_{k=1}^n {|w_{ck}-w_{xk}|^lambda}}

其中n为其维度，

w_{ck}

为c在第k维上的分量。

lambda =2

时对SSE求偏导，

frac{partial } {partial C_k}{SSE} = frac{partial } {partial C_k}{sumlimits_{i=1}^k sumlimits_{x in C_i} (c_i-x)^2}\=sumlimits_{i=1}^k sumlimits_{x in C_i} frac{partial}{partial C_k}{(c_i-x)^2}\=sumlimits_{i=1}^ksumlimits_{xin C_i} 2(c_i-x) = 0

解上面方程得：

m_i*c_i=sumlimits_{x in C_i} x Rightarrow c_i = frac{1}{m_i}sumlimits_{x in C_i}x

从此推导我们可以明白为什么选择均值作为类簇的中心点，因为中心点为均值是，才能使得SSE最小。

CSDN博客：http://blog.csdn.net/shine19930820/article/details/64907266

附录

算法分类

​ 机器学习算法按照学习方式分为监督学习、非监督学习、半监督学习、强化学习

监督学习：从给定的训练数据集中学习出一个函数，当新的数据到来时，可以根据这个函数预测结果。训练集中的目标是由人标注的。

非监督式学习：与监督学习相比，训练集没有人为标注的结果。常见的非监督式学习算法有聚类。

半监督式学习：输入数据部分被标识，部分没有被标识，介于监督式学习与非监督式学习之间。常见的半监督式学习算法有支持向量机。

强化学习：在这种学习模式下，输入数据作为对模型的反馈，不像监督模型那样，输入数据仅仅是作为一个检查模型对错的方式，在强化学习下，输入数据直接反馈到模型，模型必须对此立刻作出调整。常见的强化学习算法有时间差学习。

​ 按照算法类似性分为决策树学习、回归、聚类、人工神经网络

决策树：根据数据的属性采用树状结构建立决策模型。决策树模型常常用来解决分类和回归问题。常见的算法包括 CART (Classification And Regression Tree)、ID3、C4.5、随机森林 (Random Forest) 等。

回归算法：试图采用对误差的衡量来探索变量之间的关系的一类算法。常见的回归算法包括最小二乘法 (Least Square)、逻辑回归 (Logistic Regression)、逐步式回归 (Stepwise Regression) 等。

聚类算法：通常按照中心点或者分层的方式对输入数据进行归并。所有的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类。常见的聚类算法包括 K-Means 算法以及期望最大化算法 (Expectation Maximization) 等。

人工神经网络：模拟生物神经网络，是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络算法包括感知器神经网络 (Perceptron Neural Network) 、反向传递 (Back Propagation) 和深度学习等。

生成方法和判别方法

监督学习方法又分生成方法（Generativeapproach）和判别方法（Discriminative approach），所学到的模型分别称为生成模型（GenerativeModel）和判别模型（Discriminative Model）。

判别方法： 由数据直接学习决策函数Y=f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。典型的判别模型包括k近邻，感知机，决策树，支持向量机等。

生成方法： 由数据学习联合概率密度分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：P(Y|X)= P(X,Y)/ P(X)。基本思想是首先建立样本的联合概率概率密度模型P(X,Y)，然后再得到后验概率P(Y|X)，再利用它进行分类。如朴素贝叶斯和隐马尔科夫模型等。

由生成模型可以得到判别模型，但由判别模型得不到生成模型。

参考资料

《统计学习方法》 《The Elements of Statistical Learning 》 《Machine Learning A Probabilistic Perspective》 Top 10 algorithms in data mining

相似算法：

  • 『数据挖掘十大算法 』笔记一：决策树
  • 『数据挖掘十大算法 』笔记二：SVM-支持向量机
  • 『数据挖掘十大算法 』笔记三：K-means
编程算法 聚类算法 监督学习 serverless

0 人点赞