前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >『数据挖掘十大算法 』笔记三:K-means

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

作者头像
百川AI
发布2021-10-19 15:59:47
4940
发布2021-10-19 15:59:47
举报
文章被收录于专栏:我还不懂对话我还不懂对话

数据挖掘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]{\sum\limits_{k=1}^n {|x_{ik}-x_{jk}|}^\lambda}

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

Euclidean Distance公式

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

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

CityBlock Distance公式

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

d_{ij} = {\sum\limits_{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 = \sum\limits_{i=1}^k \sum\limits_{x \in C_i} D(c_i,x)

其中

c_i

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

D(c,x) =d_{cx} = \sqrt[\lambda]{\sum\limits_{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}{\sum\limits_{i=1}^k \sum\limits_{x \in C_i} (c_i-x)^2}\\=\sum\limits_{i=1}^k \sum\limits_{x \in C_i} \frac{\partial}{\partial C_k}{(c_i-x)^2}\\=\sum\limits_{i=1}^k\sum\limits_{x\in C_i} 2(c_i-x) = 0

解上面方程得:

m_i*c_i=\sum\limits_{x \in C_i} x \Rightarrow c_i = \frac{1}{m_i}\sum\limits_{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

相似算法:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-03-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据挖掘Top 10算法
  • K-means算法:
    • 算法流程
      • 求中心点算法
        • 距离公式
          • Minkowski Distance公式
          • Euclidean Distance公式
          • CityBlock Distance公式
          • 向量表示法
        • 迭代终止条件:
          • K-Means主要缺陷
          • K-Means++算法
          • k-means算法评价标准
          • 附录
            • 算法分类
              • 生成方法和判别方法
                • 参考资料
                  • 相似算法:
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档