K-means算法
聚类的基本思想
俗话说"物以类聚，人以群分"
聚类（Clustering）是一种无监督学习(unsupervised learning)，简单地说就是把相似的对象归到同一簇中。簇内的对象越相似，聚类的效果越好。
- 定义：给定一个有个对象的数据集，聚类将数据划分为个簇，而且这个划分满足两个条件：
每个簇至少包含一个对象
每个对象属于且仅属于一个簇。
- 基本思想：对给定的，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。
k-means 算法
k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
算法步骤如下：
- 随机选择K个中心点
- 把每个数据点分配到离它最近的中心点；
- 重新计算每类中的点到该类中心点距离的平均值
- 分配每个数据到它最近的中心点；
- 重复步骤3和4，直到所有的观测值不再被分配或是达到最大的迭代次数（R把10次作为默认迭代次数）。
实战演练
- 生成数据集
from matplotlib import pyplot as plt
%matplotlib inline
from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=300, centers=4,
cluster_std=0.60, random_state=0)
plt.scatter(X[:, 0], X[:, 1], s=50)
- 导入k-means
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200)
print(centers)
[[ 1.98258281 0.86771314]
[-1.37324398 7.75368871]
[ 0.94973532 4.41906906]
[-1.58438467 2.83081263]]
自己动手写一个k-mean
import numpy as np
from sklearn.metrics import pairwise_distances_argmin # 距离
def find_clusters(X, n_clusters, rseed=2):
# 1. Randomly choose clusters
rng = np.random.RandomState(rseed)
i = rng.permutation(X.shape[0])[:n_clusters]
centers = X[i]
while True:
# 2a. 基于最近的中心指定标签
labels = pairwise_distances_argmin(X, centers)
# 2b. 从点的方式找到新的中心
new_centers = np.array([X[labels == i].mean(0)
for i in range(n_clusters)])
# 2c. 检查收敛性
if np.all(centers == new_centers):
break
centers = new_centers
return centers, labels
centers, labels = find_clusters(X, 4)
plt.scatter(X[:, 0], X[:, 1], c=labels,
s=50, cmap='viridis')
print(centers)
print(labels)
[[ 0.94973532 4.41906906]
[-1.37324398 7.75368871]
[ 1.98258281 0.86771314]
[-1.58438467 2.83081263]]
[2 1 0 1 2 2 3 0 1 1 3 1 0 1 2 0 0 2 3 3 2 2 0 3 3 0 2 0 3 0 1 1 0 1 1 1 1
1 3 2 0 3 0 0 3 3 1 3 1 2 3 2 1 2 2 3 1 3 1 2 1 0 1 3 3 3 1 2 1 3 0 3 1 3
3 1 3 0 2 1 2 0 2 2 1 0 2 0 1 1 0 2 1 3 3 0 2 2 0 3 1 2 1 2 0 2 2 0 1 0 3
3 2 1 2 0 1 2 2 0 3 2 3 2 2 2 2 3 2 3 1 3 3 2 1 3 3 1 0 1 1 3 0 3 0 3 1 0
1 1 1 0 1 0 2 3 1 3 2 0 1 0 0 2 0 3 3 0 2 0 0 1 2 0 3 1 2 2 0 3 2 0 3 3 0
0 0 0 2 1 0 3 0 0 3 3 3 0 3 1 0 3 2 3 0 1 3 1 0 1 0 3 0 0 1 3 3 2 2 0 1 2
2 3 2 3 0 1 1 0 0 1 0 2 3 0 2 3 1 3 2 0 2 1 1 1 1 3 3 1 0 3 2 0 3 3 3 2 2
1 0 0 3 2 1 3 0 1 0 2 2 3 3 0 2 2 2 0 1 1 2 2 0 2 2 2 1 3 1 0 2 2 1 1 1 2
2 0 1 3]
# 改变随机种子
centers, labels = find_clusters(X, 4, rseed=0)
plt.scatter(X[:, 0], X[:, 1], c=labels,
s=50, cmap='viridis');
扩展k-means（SpectralClustering）
from sklearn.datasets import make_moons
X, y = make_moons(200, noise=.05, random_state=0)
plt.scatter(X[:, 0], X[:, 1])
labels = KMeans(2, random_state=0).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels,
s=50, cmap='viridis')
很明显这样划分有问题
对于make_moons的数据不推荐直接用k-means
- 引出SpectralClustering光谱聚类
from sklearn.cluster import SpectralClustering
model = SpectralClustering(n_clusters=2, affinity='nearest_neighbors',
assign_labels='kmeans')
labels = model.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels,
s=50, cmap='viridis');
实例：k-means on digits （手写字体）
不是深度学习的MNIST手写体识别。
from sklearn.datasets import load_digits
digits = load_digits()
digits.data.shape # (1797, 64)
kmeans = KMeans(n_clusters=10, random_state=0)
clusters = kmeans.fit_predict(digits.data)
kmeans.cluster_centers_.shape #(10, 64)
fig, ax = plt.subplots(2, 5, figsize=(10, 6))
centers = kmeans.cluster_centers_.reshape(10, 8, 8)
for axi, center in zip(ax.flat, centers):
axi.set(xticks=[], yticks=[])
axi.imshow(center, interpolation='nearest', cmap=plt.cm.binary)
# 众数
from scipy.stats import mode
# 创建（10，8，8）零矩阵
labels = np.zeros_like(clusters)
for i in range(10):
# clusters是1797的标签的数组
mask = (clusters == i)
labels[mask] = mode(digits.target[mask])[0]
from sklearn.metrics import accuracy_score
accuracy_score(digits.target, labels)
# 0.7935447968836951
from sklearn.metrics import confusion_matrix
mat = confusion_matrix(digits.target, labels)
sns.heatmap(mat.T, square=True, annot=True, fmt='d', cbar=False,
xticklabels=digits.target_names,
yticklabels=digits.target_names)
plt.xlabel('true label')
plt.ylabel('predicted label')
精度为0.7935447968836951未免太差了
使用TSNE 提高精确度
高维数据降维可视化TSNE
from sklearn.manifold import TSNE
# 10---> 2
tsne = TSNE(n_components=2, init='random', random_state=0)
digits_proj = tsne.fit_transform(digits.data)
# 计算clusters
kmeans = KMeans(n_clusters=10, random_state=0)
clusters = kmeans.fit_predict(digits_proj)
# 预测labels
labels = np.zeros_like(clusters)
for i in range(10):
mask = (clusters == i)
labels[mask] = mode(digits.target[mask])[0]
# 计算精度
accuracy_score(digits.target, labels)
# 0.9326655537006121本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录