赞
踩
今天一起学习下机器学习的今典分类算法之k-means
k均值聚类是基于样本集合划分的聚类算法。简而言之,k 均值聚类将样本划分为 k 个类,将 n 个样本划分到 k 个类中,每个样本到其所属类中心的距离最小。k-means聚类属于硬聚类。
软聚类就是把数据以一定的概率分到各类中,比如高斯混合模型(GMM),比如模糊 C 均值模型(Fuzzy c-Means)。聚类的结果往往是样本1在A类的概率是 0.7,在 B 类的概率是 0.3。软聚类又称为模糊聚类(fuzzy clustering)。
硬聚类就是把数据确切地分到某一类中,比如K-Means。
定义样本与其所属类中心的距离总和为损失函数
W
(
C
)
=
∑
l
=
1
k
∑
C
(
i
)
=
l
∣
∣
x
i
−
x
l
‾
∣
∣
2
W(C)=k∑l=1∑C(i)=l||xi−¯xl||2
W(C)=l=1∑kC(i)=l∑∣∣xi−xl∣∣2
式中,
x
l
‾
=
(
x
‾
1
l
,
x
‾
2
l
,
.
.
.
,
x
‾
m
l
)
\overline{x_l} = (\overline{x}_{1l}, \overline{x}_{2l}, ...,\overline{x}_{ml})
xl=(x1l,x2l,...,xml)是第 l 个类的中心(均值),m代表特征数。
k均值聚类是通过使损失函数最小化来选择最优的划分或者函数 C ∗ C\ast C∗。
C ∗ = a r g m i n C ∑ l = 1 k ∑ C ( i ) = l ∣ ∣ x i − x l ‾ ∣ ∣ 2 C∗=argminCk∑l=1∑C(i)=l||xi−¯xl||2 C∗=argCminl=1∑kC(i)=l∑∣∣xi−xl∣∣2
输入:n 个样本的集合
输出:样本集合的聚类
C
∙
C\bullet
C∙
k 个类,需要迭代 k 次,每次迭代需要计算 n 个样本的 m 个特征的均值,所以k-means的时间复杂度为O(nmk),其中 n 为样本数,k 为类别数,m 为特征数。
李航.统计学习方法(第二版) [M].北京:清华大学出版社,2019
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。