创建数据库
在该实例中,我们将会使用sklearn的make_blobs函数进行数据点的创建。首先介绍该函数,scikit中的make_blobs方法常被用来生成聚类算法的测试数据,直观地说,make_blobs会根据用户指定的特征数量、中心点数量、范围等来生成几类数据,这些数据可用于测试聚类算法的效果。 使用方法如下:
sklearn.datasets.make_blobs(n_samples, n_features,centers,cluster_std)
其中: n_samples是待生成的样本的总数。 n_features是每个样本的特征数。 centers表示样本中心的坐标。 cluster_std表示每个类别的方差,例如我们希望生成2类数据,其中一类比另一类具有更大的方差,可以将cluster_std设置为[1.0,3.0]。 在本实例中,我们使用make_b lobs构建数据库,代码如下:
x,y =make_blobs(n_samples=1000,n_features=2,centers=[[-1,0],[0,1],[1,0],[0,-1]],cluster_std=[0.4,0.2,0.2,0.2],random_state=4426)
其中样本点数设置为10000个样本点,为了方便下面实验结果的可视化,设置样本点的特征维数为2,将样本中心坐标设置为(-1,0),(0,1),(1,0),(0,-1),而每个类别的方差设置为0.4,0.2,0.2,0,为了保证每次实验结果相同,这里保持随机数种子不变,设置为4426,下面为的数据图的可视化结果图:
算法实现
(一)处理数据:使用make_blobs函数创建数据,可视化其样本分布
(二)构建K-means算法:构建K-means,对创建的数据库进行聚类
(三)完整代码:使用所有代码呈现一个完整的K-means算法。
(四)实验结果:可视化聚类结果。
处理数据
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_blobs
def create_self_build_data():
x,y = make_blobs(n_samples=1000,n_features=2,centers=[[-1,0],[0,1],[1,0],[0,-1]],cluster_std=[0.4,0.2,0.2,0.2],random_state=4426)
plt.figure()
plt.scatter(x[:,0],x[:,1])
plt.xlabel('x1')
plt.ylabel('x2')
plt.title('Build Data Visualization')
plt.savefig("Build Data Visualization.jpg")
plt.show()
return x
array([[ 0.13914954, -0.97685012],
[ 0.21049303, -0.9277677 ],
[ 0.00207858, -1.39111698],
...,
[-0.06234613, -0.8179036 ],
[ 0.13436981, 0.97366555],
[-0.21182717, 0.64720128]])
构建K-means算法
将K-means算法的构建内容分为以下三部分: 1、参数初始化 2、计算类簇中心 3、对样本进行类簇中心的归类
1、参数初始化
在K-means算法中,需要初始化的参数只有类簇中心的个数,我们使用类的形式书写代码,所以将初始化部分封装在init函数中,代码如下:
def __init__(self, n_clusters):
self.n_clusters = n_clusters
2、计算类簇中心
计算类簇中心的步骤在理论部分已经详细讨论过,首先需要随机初始化类簇中心,再计算每个样本点到初始化类簇中心的距离,选择距离最短的类簇中心作为该样本点的类簇,然后通过计算属于该类的样本点的平均值,选出新的样本中心,通过不停的迭代更新类簇中心,最后当满足条件时,停止跌代,返回最终的类簇中心的坐标。这里计算样本点到类簇中心的欧式距离使用cdist函数,该函数已在KNN章节中的实践部分详细讨论过,这里不再讨论。当计算出每个样本点与类簇中心的距离后,使用numpy的argmin函数返回每个样本与相距最短距离的类簇中心的索引值,这样就可以得到每轮迭代中样本点属于的类簇中心的索引。通过求每一个类簇中心的样本点平均值,得到新一轮的类簇中心,具体代码如下:
# import numpy as np
from scipy.spatial.distance import cdist
def fit(self, X, iter_max=100):
I = np.eye(self.n_clusters)
centers = X[np.random.choice(len(X), self.n_clusters, replace=False)]
for _ in range(iter_max):
prev_centers = np.copy(centers)
D = cdist(X, centers)
cluster_index_num = np.argmin(D, axis=1)
cluster_index = I[cluster_index_num]
centers = np.sum(X[:, None, :] * cluster_index[:, :, None], axis=0) / np.sum(cluster_index, axis=0)[:, None]
# visualize(X, centers, cluster_index_num)
if np.allclose(prev_centers, centers):
break
self.centers = centers
return centers
在上面代码中fit是封装计算类簇中心的函数,传入的参数分别是X和iter_max,X代表的是存储数据的数组,即上方加载mnist数据的data参数,而iter_max参数代表迭代的最高次数,但是不一定需要进行iter_max次计算,当满足条件时候,循环就会停止。这里的条件是当新一轮更新的类簇中心的坐标与上一轮类簇中心的坐标完全一致时,迭代结束,由下面的语句:
if np.allclose(prev_centers, centers):
break
3、对样本进行类簇中心的归类
该函数对传入的数据与最后得出的类簇中心进行欧式距离,而后通过argmin函数返回每个样本点所属于的索引,具体代码如下:
def predict(self, X):
D = cdist(X, self.centers)
return np.argmin(D, axis=1)
完整代码
import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial.distance import cdist
from sklearn.datasets.samples_generator import make_blobs
from sklearn.metrics import silhouette_score
def create_self_build_data():
x,y = make_blobs(n_samples=1000,n_features=2,centers=[[-1,0],[0,1],[1,0],[0,-1]],cluster_std=[0.4,0.2,0.2,0.2],random_state=4426)
plt.figure()
plt.scatter(x[:,0],x[:,1])
plt.xlabel('x1')
plt.ylabel('x2')
plt.title('Build Data Visualization')
plt.savefig("Build Data Visualization.jpg")
plt.show()
return x
class KMeans(object):
def __init__(self, n_clusters):
self.n_clusters = n_clusters
def fit(self, X, iter_max=100):
I = np.eye(self.n_clusters)
centers = X[np.random.choice(len(X), self.n_clusters, replace=False)]
for _ in range(iter_max):
prev_centers = np.copy(centers)
D = cdist(X, centers)
cluster_index_num = np.argmin(D, axis=1)
cluster_index = I[cluster_index_num]
centers = np.sum(X[:, None, :] * cluster_index[:, :, None], axis=0) / np.sum(cluster_index, axis=0)[:, None]
if np.allclose(prev_centers, centers):
break
self.centers = centers
return centers
def predict(self, X):
D = cdist(X, self.centers)
return np.argmin(D, axis=1)
实验结果
上述代码为K-means的完整代码,在该部分中,通过调用K-means类对创建的数据库进行聚类,并且通过使用不同的K值,使用SC轮廓系数评估其聚类结果。并可视化其聚类结果及不同的K值下评分的曲线图,具体代码如下:
def visualize(x,centers,res,i):
if i==1:
plt.figure(figsize=(20,10))
plt.subplot(3,4,i)
plt.scatter(x[:, 0], x[:, 1], c=res)
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=50)
plt.title('Kmeans for Building Data(k={})'.format(i))
if i ==12:
plt.savefig('Kmeans for Building_data.jpg')
plt.show()
if __name__ == '__main__':
data = create_self_build_data()
score = [0]
x =[]
for i in range(1,13):
k = KMeans(i)
centers = k.fit(data)
res = k.predict(data)
if not i==1:
score.append(silhouette_score(data,res))
visualize(data,centers,res,i)
x.append(i)
print(score)
plt.figure()
plt.xlabel("K")
plt.ylabel("Score")
plt.title("The effects of different K values on scoring")
plt.plot(x,score, c='r')
[0, 0.457780803218996, 0.5080853141953842, 0.6670756213897803, 0.5514994434711662, 0.4972075336548737, 0.5180406441059938, 0.4192441235077847, 0.32406038278980476, 0.4119750730007824, 0.32316498891725337, 0.31923830562280875]
对Mnist数据库进行K-means聚类
Mnist数据集
MNIST数据集数据库由60000个训练样本和10000个测试样本组成,每个样本都是一张28 * 28像素的灰度手写数字图片。 从官方网站: http://yann.lecun.com/exdb/mnist/guo 可以下载mnist数据集,其中一共4个文件,训练集、训练集标签、测试集、测试集标签:
其中数据集的图片如下图所示:
然而使用numpy函数库对mnist数据库的四个原始文件进行读取处理,要求代码工作量较大,在这里不要求大家掌握,所以使用sklearn数据库帮助我们加载mnist数据库,下面正式开始讲解我们的实例代码。
加载数据与实验结果
由于在的实例2中已经详细讲解过K-means算法的代码,这里不再进行重复讲解,直接使用上面的K-means代码进行聚类即可,在这一部分主要阐述如何加载Mnist数据,并对其聚类结果进行可视化。
加载数据
在上述的mnist数据库介绍中,数据库的原文件共有4个,我们使用sklearn函数库的fetch_mldata()函数对mnist数据库进行加载,但是要注意fetch_mldata函数处理的不是上述的4个源文件,而是使用sklearn函数库提供的mnist-original.mat文件,这个文件是sklearn在第一次加载数据集时会帮助我们下载的。但是由于现在fetch_mldata无法帮助我们下载这个文件,所以我们需要手动下载,下面提供了一个网盘地址供给大家下载: 链接:https://pan.baidu.com/s/1fe60R_ykcdvGp_ZhZGoIIQ 密码:o83d 当文件下载完成后,在当前存放代码地方,创建一个新文件夹名字命名为mldata,存放mnist-original.mat文件,然后就可以使用fetch_data函数对mnist数据集进行加载,当加载mnist数据后,使用PCA进行降维(在这里不对PCA算法进行讲解,具体代码到PCA章节查阅),方便下面的实验结果进行可视化。具体代码如下:
from sklearn.datasets import fetch_mldata
from sklearn.decomposition import PCA
import numpy as np
def create_data():
mnist = fetch_mldata('MNIST original', data_home='database/')
data = mnist.data
data = data.reshape(-1, 28 * 28)
pca = PCA(2)
data = pca.fit_transform(data)
return data
实验结果
上述代码为K-means的完整代码,在该部分中,通过调用K-means类对mnist函数进行聚类,并可视化其聚类结果,具体代码如下:
import matplotlib.pyplot as plt
def visualize(x,centers,res):
plt.scatter(x[:, 0], x[:, 1], c=res)
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=50)
plt.xlabel('x1')
plt.ylabel('x2')
plt.title('Kmeans for mnist')
plt.savefig('Kmeans for mnist database after PCA.jpg')
plt.show()
if __name__ == '__main__':
data = create_data()
k = KMeans(10)
centers = k.fit(data)
res = k.predict(data)
visualize(data,centers,res)
K-Means++算法
K-means算法的缺点
K-means算法有一个很大的问题,就是其对于聚类中心的初始化是从样本中随机选取K个样本点作为聚类中心,这样的初始化方式往往会让我们的算法陷入局部最优,而无法获得全局最优。
通常避免这种情况的简单方法是重复多次运行K-means算法,然后取一个平均结果,但是其实还有更加精妙而简单的做法,就是在初始化选取样本中心的时候尽可能让样本中心之间的两两距离尽可能地远,这样就可以避免上图中的局部最优的问题,而个方法就是K=means++的核心思想。
注意:K-means++算法只有在类簇中心初始化与K-means算法不同,其余算法步骤均相同。
K-menas++初始化类簇中心过程
步骤一:在数据集中随机选取一个样本点作为第一个簇中心C1;
步骤二:计算剩余样本点与所有类簇中心的最短欧式距离,令其表示为:
则样本点xi被选为下一个类簇中心的概率为:
当计算完所有剩余样本点与类簇中心的概率后选取概率最大的样本点作为下一个类簇中心。
步骤三:重复2直到选出k个类簇中心。
获取K-means算法和K-means++算法代码请查看全文
未经允许不得转载!Python实现K-means聚类算法及K-means++算法(附代码)