k-means聚类算法

参考:

K均值聚类算法

分类 vs. 聚类

参考:5 分钟带你弄懂 k-means 聚类

分类:类别是已知的,通过对已知分类的数据进行训练和学习,找到这些不同类别的特征,再对未分类的数据进行分类。属于有监督学习(有标签)
聚类:事先不知道数据会分为几类,通过聚类分析将数据聚合成几个群体。聚类不需要对数据进行训练和学习。属于无监督学习(无标签)

k-means聚类

定义

k-means聚类算法通过计算距离作为相似度来衡量两个对象是否属于同一簇。其算法如下:

  1. 随机选取$k$个对象作为初始聚类中心
  2. 计算所有对象和这$k$个聚类中心的距离(欧式距离),将其分配给距离最近的聚类中心
  3. 完成所有对象的分配后,重新计算这$k$个聚类的中心,重复第2步
  4. 终止条件:
    1. 没有(或最小数目)对象被重新分配给不同的聚类
    2. 没有(或最小数目)聚类中心发生变化
    3. 误差平方和局部最小

具体实现过程中,需要注意以下几点:

  1. $k$是超参数,表明了本次实现要计算的类别数
  2. 通过计算$k$个聚类的均值来重新确定聚类中心。注意:此时的聚类中心可能就不是某一个对象了

实现

百度百科给出了很好的实现范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class KMeansClusterer:

def __init__(self, ndarray, cluster_num):
self.ndarray = ndarray
self.cluster_num = cluster_num
self.points = self.__pick_start_point(ndarray, cluster_num)

def cluster(self):
result = []
for i in range(self.cluster_num):
result.append([])
for item in self.ndarray:
distance_min = sys.maxsize
index = -1
for i in range(len(self.points)):
distance = self.__distance(item, self.points[i])
if distance < distance_min:
distance_min = distance
index = i
result[index] = result[index] + [item.tolist()]
new_center = []
for item in result:
new_center.append(self.__center(item).tolist())
# 中心点未改变,说明达到稳态,结束递归
if (self.points == new_center).all():
return result

self.points = np.array(new_center)
return self.cluster()

def __center(self, list):
'''
计算一组坐标的中心点
'''
# 计算每一列的平均值
return np.array(list).mean(axis=0)

def __distance(self, p1, p2):
'''
计算两点间距
'''
tmp = 0
for i in range(len(p1)):
tmp += pow(p1[i] - p2[i], 2)
return pow(tmp, 0.5)

def __pick_start_point(self, ndarray, cluster_num):

if cluster_num < 0 or cluster_num > ndarray.shape[0]:
raise Exception("簇数设置有误")

# 随机点的下标
indexes = random.sample(np.arange(0, ndarray.shape[0], step=1).tolist(), cluster_num)
points = []
for index in indexes:
points.append(ndarray[index].tolist())
return np.array(points)

距离计算

k-means聚类算法通过欧式距离来衡量对象和聚类中心的相似度。对于多属性的对象而言,选择哪些属性参与距离计算也是一个很好的优化方法

示例:iris分类

使用k-means聚类算法分类iris数据集

数据集定义

参考:[数据集]Iris

iris数据集包含了4个属性,分别表示(单位cm):

  1. 萼片(sepal)长度
  2. 萼片宽度
  3. 花瓣(petal)长度
  4. 花瓣宽度

每个类别有50个实例,整个数据集共150

sklearn实现

参考:利用python内置K-Means聚类算法实现鸢尾花数据的聚类

sklearn提供了k-means算法,实现iris聚类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from sklearn import datasets
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans


def load_data():
# Import some data to play with
iris = datasets.load_iris()
X = iris.data
y = iris.target

return X, y


def plot(data, target, title='iris'):
x0 = data[target == 0]
x1 = data[target == 1]
x2 = data[target == 2]

fig = plt.figure()
plt.title(title)
plt.scatter(x0[:, 0], x0[:, 1], c="red", marker='o', label='Iris-0')
plt.scatter(x1[:, 0], x1[:, 1], c="green", marker='*', label='Iris-1')
plt.scatter(x2[:, 0], x2[:, 1], c="blue", marker='+', label='Iris-2')
plt.xlabel('petal length')
plt.ylabel('petal width')
plt.legend(loc=2)
plt.show()


if __name__ == '__main__':
data, target = load_data()
plot(data, target)

# 构造聚类器
estimator = KMeans(n_clusters=3)
# 聚类
estimator.fit(data)
# 获取聚类标签
label_pred = estimator.labels_
plot(data, label_pred, title='k-means cluster')

上述结果使用了iris4个属性进行聚类下面仅使用后两个属性进行聚类

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == '__main__':
data, target = load_data()
data = data[:, 2:]
plot(data, target)

# 构造聚类器
estimator = KMeans(n_clusters=3)
# 聚类
estimator.fit(data)
# 获取聚类标签
label_pred = estimator.labels_
plot(data, label_pred, title='k-means cluster')

坚持原创技术分享,您的支持将鼓励我继续创作!