人工智能-机器学习-KMeans算法k值及初始类簇中心点的选取。

开课吧开课吧锤锤2021-02-04 14:00

KMeans算法是最常用的聚类算法,主要思想是:在给定K值和K个初始类簇中心点的情况下,把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中,所有点分配完毕之后,根据一个类簇内的所有点重新计算该类簇的中心点(取平均值),然后再迭代的进行分配点和更新类簇中心点的步骤,直至类簇中心点的变化很小,或者达到指定的迭代次数。

  KMeans算法本身思想比较简单,但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。

人工智能面试

  1. 确定K个初始类簇中心点

  最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点,但是该方法在有些情况下的效果较差,如下(下图中的数据是用五个二元正态高斯分布生成的,颜色代表聚类效果):

人工智能面试

《大数据》一书中提到K个初始类簇点的选取还有两种方法:1)选择彼此距离尽可能远的K个点 ;2)先对数据用层次聚类算法或者Canopy算法进行聚类,得到K个簇之后,从每个类簇中选择一个点,该点可以是该类簇的中心点,或者是距离类簇中心点最近的那个点。

  1) 选择批次距离尽可能远的K个点

  首先随机选择一个点作为第一个初始类簇中心点,然后选择距离该点最远的那个点作为第二个初始类簇中心点,然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点,以此类推,直至选出K个初始类簇中心点。

  该方法经过我测试效果很好,用该方法确定初始类簇点之后运行KMeans得到的结果全部都能完美区分五个类簇:

  人工智能面试

  2) 选用层次聚类或者Canopy算法进行初始聚类,然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。

  常用的层次聚类算法有BIRCH和ROCK,在此不作介绍,下面简单介绍一下Canopy算法,主要摘自Mahout的Wiki:

  首先定义两个距离T1和T2,T1>T2.从初始的点的集合S中随机移除一个点P,然后对于还在S中的每个点I,计算该点I与点P的距离,如果距离小于T1,则将点I加入到点P所代表的Canopy中,如果距离小于T2,则将点I从集合S中移除,并将点I加入到点P所代表的Canopy中。迭代完一次之后,重新从集合S中随机选择一个点作为新的点P,然后重复执行以上步骤。

  Canopy算法执行完毕后会得到很多Canopy,可以认为每个Canopy都是一个Cluster,与KMeans等硬划分算法不同,Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点,或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。

  2. K值的确定。

  《大数据》中提到:给定一个合适的类簇指标,比如平均半径或直径,只要我们假设的类簇的数目等于或者高于真实的类簇的数目时,该指标上升会很缓慢,而一旦试图得到少于真实数目的类簇时,该指标会急剧上升。

  类簇的直径是指类簇内任意两点之间的最大距离。

  类簇的半径是指类簇内所有点到类簇中心距离的最大值。

  废话少说,上图。下图是当K的取值从2到9时,聚类效果和类簇指标的效果图:

人工智能面试

人工智能面试

 左图是K取值从2到7时的聚类效果,右图是K取值从2到9时的类簇指标的变化曲线,此处我选择类簇指标是K个类簇的平均质心距离的加权平均值。从上图中可以明显看到,当K取值5时,类簇指标的下降趋势最快,所以K的正确取值应该是5.

补充:

k-means++算法

k-means++算法选择初始seeds的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。

1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心

2. 对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)

3. 选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大

4. 重复2和3直到k个聚类中心被选出来

5. 利用这k个初始的聚类中心来运行标准的k-means算法

人工智能在计算机领域内,得到了愈加广泛的重视。并在机器人,经济政治决策,控制系统,仿真系统中得到应用。发展前景很可观,有对人工智能感兴趣的同学就赶快学习起来吧。以上就是小编今天为大家整理发布的“人工智能-机器学习-KMeans算法k值及初始类簇中心点的选取。”一文,希望为正在学习人工智能的朋友提供学习参考,更多人工智能面试尽在开课吧广场人工智能面试频道!

有用
分享