机器学习十讲——第五讲(聚类)
数学知识相关
凸函数:假设f(x)为多元函数,如果对任意t∈[0,1],均满足:。则称f(x)为凸函数。
Jensen不等式:如果f是凸函数,X是随机变量,则。
该不等式的另一种描述:。ai表示权重。取等号的条件是:f(xi)是常量。
凸函数图示:
聚类
本质:将数据集中相似的样本进行分组的过程。
簇:分组后每个组称为一个簇,每个簇的样本对应一个潜在的类别。样本没有类别标签,因此是聚类一种典型的无监督学习方法。
簇的条件:相同簇的样本之间距离较近;不同簇的样本之间距离较远。
聚类方法:层次聚类,K-Means,谱聚类等等。
算法介绍
K-Means模型:
起源:最初起源于信号处理,是一种比较流行的聚类方法。
数据集:,将样本划分为k个簇,每个簇中心为cj(1<=j<=k)。
优化目标:最小化所有样本点到所属簇中心的距离平方和(失真度量)。
模型求解:
公式中rij是离散形式,优化使用图示中的交替迭代法。
固定c,优化r:
优化目标:
不同的Ji(ri)相互独立,可以分别优化:
对于样本xi,对最近的中心j,rij=1,将其指派给最近的类。
固定r,优化c:
优化目标:
不同的Jj(cj)相互独立,分别优化,且均为二次凸函数:
分母(蓝色)表示cj这一类里总共有多少样本,分子(绿色)表示对应的第j类中每一个样本的求和。因此结果为第j类中心为j类样本均值。
K-Means算法流程:
1, 随机选择k个点作为初始中心。
2, Repeat:将每个样本指派到最近的中心,形成k个类;重新计算每个类的中心为该类样本均值。
3, 直到中心不发生变化。
高斯混合模型(GMM):
GMM求解:
应用到Jensen不等式,注意优化目标中是ln函数,在函数图像上显示为凹函数,因此原Jensen不等式表示中,将<=改为>=。(即第二行)
EM算法:
实例
使用不同的方式实现K-Means算法
本次实例多次使用了make_blobs生成随机数据集,下面对该方法进行参数介绍
#使用iterrows遍历实现K-Means算法 ##计算一个样本到中心的距离 import numpy as np def point_dist(x,c): #定义距离计算函数 return np.linalg.norm(x-c) ##使用iterrows方法遍历样本计算样本到中心的距离,定义一个函数方法实现K-Means算法 def k_means1(X,k): centers = X.sample(k).values #从数据集随机选择 K 个样本作为初始化的类中心,k 行 d 列 X_labels = np.zeros(len(X)) #样本的类别 error = 10e10 while(error > 1e-6): for i,x in X.iterrows():#指派样本类标签 X_labels[i] = np.argmin([point_dist(x,centers[i,:]) for i in range(k)]) centers_pre = centers centers = X.groupby(X_labels).mean().values #更新样本均值,即类中心 error = np.linalg.norm(centers_pre - centers)#计算error return X_labels, centers ##使用sklearn.datasets.make_blobs获取一个用于测试聚类算法的随机数据集 from sklearn import datasets import pandas as pd X, y = datasets.make_blobs(n_samples=5000, n_features=8, cluster_std = 0.5,centers=3,random_state=99) X_df = pd.DataFrame(X) ##在该数据集上使用定义好的函数方法运行K-Means聚类,用%time记录运行时间 %time labels,centers = k_means1(X_df,3) # for 循环
#使用apply遍历实现K-Means算法 def k_means2(X,k): #初始化 K 个中心,从原始数据中选择样本 centers = X.sample(k).values X_labels = np.zeros(len(X)) #样本的类别 error = 10e10 while(error > 1e-6): #********# X_labels = X.apply(lambda r : np.argmin([point_dist(r,centers[i,:]) for i in range(k)]),axis=1) centers_pre = centers centers = X.groupby(X_labels).mean().values #更新样本均值,即类中心 error = np.linalg.norm(centers_pre - centers)#计算error return X_labels, centers %time labels,centers = k_means2(X_df,3) # apply 运算
#使用矩阵运算方式实现K-Means算法 import pandas as pd import numpy as np def k_means(X,k): C = X.sample(k).values #从数据集随机选择 K 个样本作为初始化的类中心,k 行 d 列 X_labels = np.zeros(len(X)) #记录样本的类别 error = 10e10 #停止迭代的阈值 while(error > 1e-6): D = np.zeros((len(X),k)) #样本到每一个中心的距离,n 行 k 列 for i in range(k): D[:,i] = np.sqrt(np.sum(np.square(X - C[i,:]),axis=1)) #使用argmin方法将其指派到最近的类 labels = np.argmin(D,axis=1) C_pre = C temp_C = X.groupby(labels).mean() #更新样本均值,即类中心 C = np.zeros((k,X.shape[1])) for i in temp_C.index: C[i,:] = temp_C.loc[i,:].values if C.shape == C_pre.shape: error = np.linalg.norm(C_pre - C)#计算error else: print(C.shape, C_pre.shape) return labels, C %time labels,centers = k_means(X_df,3) # 矩阵运算
以上是三种实现K-Means算法的方式
聚类结果可视化
#可视化 ##设置颜色 color_dict = {0:"#E4007F",1:"#007979",2:"blue",3:"orange"} #洋红,深绿,蓝色,橘色 ##再次使用make_blobs随机生成二维数据集 from sklearn import datasets import matplotlib.pyplot as plt import pandas as pd %matplotlib inline X, y = datasets.make_blobs(n_samples=1000, n_features=2, cluster_std = 1.5,centers=4,random_state=999) X_df = pd.DataFrame(X,columns=["x1","x2"]) labels,centers= k_means(X_df,4) fig, ax = plt.subplots(figsize=(8, 8)) #设置图片大小 for i in range(len(centers)): ax.scatter(X_df[labels == i]["x1"],X_df[labels == i]["x2"],color=color_dict[i],s=50,alpha=0.4) ax.scatter(centers[int(i),0],centers[int(i),1],color="r",s=100,marker="+") plt.xlabel("$x_1$") plt.ylabel("$x_2$")
接下来是动画模式,之前的学习中使用过:
#使用动画展示K-Means聚类过程 ##更改之前的算法,增设记录过程对象 def k_means_steps(X,k): #初始化 K 个中心,从原始数据中选择样本 #********# samples_list = [] #记录每一个中间迭代中每一类样本 centers_list = [] #记录每一个中间迭代中每一类样本中心 #********# C = X.sample(k).values labels = np.zeros(len(X)) #样本的类别 error = 10e10 while(error > 1e-6): D = np.zeros((len(X),k)) #样本到每一个中心的距离 for i in range(k): D[:,i] = np.sqrt(np.sum(np.square(X - C[i,:]),axis=1)) labels = np.argmin(D,axis=1) C_pre = C C = X.groupby(labels).mean().values #更新样本均值,即类中心 #********# 记录当前迭代地每一类的样本集合和中心 samples,centers2 = [],[] for i in range(k): samples.append(X[labels == i]) centers2.append(C[i,:]) samples_list.append(samples) centers_list.append(centers2) #********# if C.shape == C_pre.shape: error = np.linalg.norm(C_pre - C)#计算error else: print(C.shape, C_pre.shape) return labels, C,samples_list,centers_list #********# 返回最终的聚类结果,聚类中心,每一步的聚类结果和聚类中心 ##使用matplotlib.animation动画模块 labels,centers,samples_list,centers_list= k_means_steps(X_df,4) fig, ax = plt.subplots(figsize=(8, 8)) samples_obj = [] centers_obj = [] def init_draw(): # 展现样本数据 ax.set_title("K-Means聚类过程:") for i in range(len(centers)): samples_obj.append(ax.scatter(samples_list[0][i]["x1"],samples_list[0][i]["x2"],color=color_dict[i],s=50,alpha=0.6)) centers_obj.append(ax.scatter(centers_list[0][i][0],centers_list[0][i][1],color="r",s=100,marker="+")) plt.xlabel("$x_1$") plt.ylabel("$x_2$") def update_draw(t): # 实现动画中每一帧的绘制函数,i为第几帧 ax.set_title("K-Means聚类过程:" + str(t)) samples,centers = samples_list[t],centers_list[t] for i in range(len(centers)): samples_obj[i].set_offsets(samples[i]) centers_obj[i].set_offsets(centers[i]) plt.close() #演示决策面动态变化 import matplotlib.animation as animation from IPython.display import HTML animator = animation.FuncAnimation(fig, update_draw, frames= range(1,len(centers_list)), init_func=init_draw,interval=2000) HTML(animator.to_jshtml())
运行截图仅展示个别步骤:
失真度量J的变化
优化目标中主要就是最小化失真度量,下面通过代码来看一看失真度量的变化
#失真度量J的可视化 ##再次更改方法,记录J import pandas as pd import numpy as np def k_means_inertia(X,k): #初始化 K 个中心,从原始数据中选择样本 C = X.sample(k).values labels = np.zeros(len(X)) #样本的类别 inertia_list = [] #*****记录优化目标****# error = 10e10 while(error > 1e-6): D = np.zeros((len(X),k)) #样本到每一个中心的距离 for i in range(k): D[:,i] = np.sqrt(np.sum(np.square(X - C[i,:]),axis=1)) labels = np.argmin(D,axis=1) #J的算法:每一个类到最近中心的距离的平方和 inertia_list.append(np.square(np.min(D,axis=1)).sum()) #****记录当前步骤的失真度量****# C_pre = C temp_C = X.groupby(labels).mean() #更新样本均值,即类中心 C = np.zeros((k,X.shape[1])) for i in range(len(temp_C)): C[i,:] = temp_C.loc[i,:].values if C.shape == C_pre.shape: error = np.linalg.norm(C_pre - C)#计算error return labels,C,inertia_list ##可视化 X, y = datasets.make_blobs(n_samples=1000, n_features=2, cluster_std=1,centers=3,random_state=99) X_df = pd.DataFrame(X,columns=["x1","x2"]) labels,centers,inertia_list = k_means_inertia(X_df,3) fig, ax = plt.subplots(figsize=(9, 6)) #设置图片大小 t = range(len(inertia_list)) plt.plot(t,inertia_list,c="#E4007F",marker="o",linestyle='dashed') plt.xlabel("t") plt.ylabel("inertia") plt.xticks(t) plt.title("K-Means算法优化目标的变化")
K-Means算法可以实现图像分割:
#加载一张测试图片,使用PIL.Image.Open打开图片,使用matplotlib.imshow将图片可视化 from PIL import Image fig, ax = plt.subplots(figsize=(6, 5)) #设置图片大小 path = './input/timg.jpg' img = Image.open(path) plt.imshow(img) plt.box(False) #去掉边框 plt.axis("off")#不显示坐标轴
#将该图片转换成表格形式 import pandas as pd def image_dataframe(image): #将图片转换成DataFrame,每个像素对应每一行,每一行包括三列 rbg_values = [] for i in range(image.size[0]): for j in range(image.size[1]): x,y,z= image.getpixel((i,j)) # 获取图片的每一个像素 (i,j)(i,j) 的 RBG 值 rbg_values.append([x,y,z]) return pd.DataFrame(rbg_values,columns=["R","B","G"]),img.size[0],img.size[1] img_df,m,n = image_dataframe(img) #输出 img_df.head()
#输出长,宽,总像素 print(m,n,m*n,len(img_df))
#使用K-Means算法进行聚类,2表示0,1标签 labels, _ = k_means(img_df,2) #将生成的灰度图可视化 fig, ax = plt.subplots(figsize=(6, 5)) #设置图片大小 labels = labels.reshape((m,n)) pic_new = Image.new("L",(m,n)) #根据类别向图片中添加灰度值 for i in range(m): for j in range(n): pic_new.putpixel((i,j),int(256/(labels[i][j] + 1))) plt.imshow(pic_new) plt.box(False) #去掉边框 plt.axis("off")#不显示坐标轴
#将像素聚类类别标签,转换成一张灰度图 def img_from_labels(labels,m,n): labels = labels.reshape((m,n)) pic_new = Image.new("L",(m,n)) #根据类别向图片中添加灰度值 for i in range(m): for j in range(n): pic_new.putpixel((i,j),int(256/(labels[i][j] + 1))) return pic_new #不同聚类数量k展示的效果不同 fig, ax = plt.subplots(figsize=(18, 10)) #设置图片大小 img = Image.open(path) #显示原图 plt.subplot(2,3,1) plt.title("原图") plt.imshow(img) plt.box(False) #去掉边框 plt.axis("off")#不显示坐标轴 for i in range(2,7): plt.subplot(2,3,i) plt.title("k=" + str(i)) labels, _ = k_means(img_df,i) pic_new = img_from_labels(labels,m,n) plt.imshow(pic_new) plt.box(False) #去掉边框 plt.axis("off")#不显示坐标轴
最后进行实战:K-Means算法实现中文新闻分类
#读取数据 import pandas as pd news = pd.read_csv("./input/chinese_news_cutted_train_utf8.csv",sep="\t",encoding="utf8") news.head()
#查看新闻分类和条数 news["分类"].value_counts()
#将新闻表示成向量格式 ##向量中每一个维度代表字典中的一个词,维度取值代表词在对应文档中的TF-IDF取值 ###使用的函数:sklearn.feature_extraction.text模块的TfidfVectorizer ####加载停用词 stop_words = [] file = open("./input/stopwords.txt") for line in file: stop_words.append(line.strip()) file.close() from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(stop_words=stop_words,min_df=0.01,max_df=0.5,max_features=500) news_vectors = vectorizer.fit_transform(news["分词文章"])
#最终转换的是一个稀疏矩阵 type(news_vectors)
#为了简便将其转换成稠密矩阵【实际中很少这么操作!!!】 news_df = pd.DataFrame(news_vectors.todense()) #输出前五列查看 news_df.head()
#使用K-Means聚类,个数设置成12(因为新闻一共有十二类) labels, _ = k_means(news_df,12) #新建labels保存结果 news["labels"] = labels
之后我们进行可视化展示:
#柱状图显示新闻聚类主题分布 fig, ax = plt.subplots(figsize=(18, 12)) #设置图片大小 cluster_topics = news.groupby(["labels"])["分类"].value_counts() for i in range(12): plt.subplot(3,4,i+1) plt.title("cluster " + str(i)) topic_dist = pd.Series(data=0,index = news["分类"].unique()) topic_dist += cluster_topics[i] topic_dist.plot(kind="bar") plt.xticks(rotation=45) plt.tight_layout()
#使用词云 ##使用groupby方法根据聚类结果对新闻进行分组 cluster_contents = news[["labels","分词文章"]].groupby(["labels"]) ##导入词云模块wordcloud, ./input/simfang.ttf是字体文件 from wordcloud import WordCloud stop_words_set = set(stop_words) cloud = WordCloud(font_path = './input/simfang.ttf',background_color='white', max_words=100,stopwords=stop_words_set,width=600,height=400) def series_to_word_list(ts): results = [] for words in ts.values: results.extend(words.split(" ")) return " ".join(results) ##遍历显示词云 fig, ax = plt.subplots(figsize=(18, 12)) #设置图片大小 for cluster, group in cluster_contents: plt.subplot(3,4,cluster+1) plt.title("cluster " + str(cluster)) wc = cloud.generate_from_text(series_to_word_list(group["分词文章"])) plt.imshow(wc) plt.axis("off") plt.tight_layout()
最后是本次实例中使用的python工具: