k中心点算法思想

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《k中心点算法思想》，欢迎阅读！

k-中心点算法

k-均值算法对离群点敏感，因为当出现对象远离大多数数据，而被分配到一个簇时，它们可能严重地扭曲簇的均值，进而影响其他对象到簇的分配。为了进一步克服这一缺点，我们提出了新的改进方法——k-中心点算法。即通过采用最靠近中心的对象来代表簇。

基本算法步骤如下：

（1）初始化：对于给定数据集D包含n个欧式空间中的对象，把n个对象划分为k（k<=n）个簇。首先选定k个对象o1，o2，……，ok，作为聚类中心，把（okD）对象pD划分到簇Ck中，使得欧氏距离E

(po

i1pCi

k

k

)2最小。

（1mk）（2）调整聚类中心，随机选取一个非代表对象orandom代替om，重新

分配所有剩余对象p，使得

E（(pok)2

i1

pCi

im

k

pCm

(po

2 )random）

（3）若E-E0，则orandomom，否则本次迭代中om不发生变化。

（1）重复以上操作，直到（3）中E-E0不再成立，则迭代终止，否则转（2）迭代继续。

K-均值算法与k-中心点算法的比较

(a) 当存在噪声和离群点时，k-中心点方法比k-均值方法更加鲁棒。 (b) k-中心点较少的受离群点影响。

(c) k-中心点方法的执行代价比k-均值方法要高。

(d) k-均值算法复杂度为O(nkt)，k-中心点算法复杂度为O(k(n-k)2)。 (e) n与k较大时，k中心点方法的执行代价很高。 (f) 两种方法都要用户指定簇的数目k。

本文来源：https://www.wddqxz.cn/b2257f85580216fc710afd61.html