- 一、什么是无监督学习
- 二、聚类算法(无监督学习)
- 1、聚类算法的应用
- 2、K-Means算法
- 算法流程--图例
- 算法流程--文字描述
- K-means分离不佳簇问题
- K-means代价函数
- K-means的随机初始化
- 如何选取聚类数量K
- 代码实例(鸢尾花)
- 三、降维
- 1. 什么是降维
- 2. 主成分分析方法(principal components analysis，PCA)
- 文字方式描述PCA
- PCA过程(n维数据降到k维)
- 3. 压缩重现
- 4. 选择K值
- 5. 应用PCA的建议
无监督学习与监督学习的对比：
（1）无监督学习
我们有一组带标签的Training Set，希望通过训练得到一条拟合Training Set的决策边界。
【即有一系列标签，然后假设函数去拟合它】
（2）无监督学习
Training Set不带标签y，无监督学习的任务就是将这些无标签的数据输入算法中，找到一些隐含在数据中的结构。
【例如：聚类算法】
（1）市场分割
将客户分成不同人群，针对性产品销售
（2）社会关系网划分
在社交网络中找到关系密切的朋友
-
存在一些无标签的数据
目标是将上列数据分成两簇 -
先假定两个聚类中心点
-
根据距离对数据点进行划分(染色)
-
重新确定新的聚类重心点(两类样本的均值)
-
由新的聚类中心重新划分样本
-
重复5、6(进行迭代)，直到聚类中心不发生改变
- K-means的Input：
(1)K：聚类的个数
(2)Training Set：{x(1),x(2),…,x(m)}
- m表示训练集数据的个数
- x(i)是n维的，即训练集样本由n个特征feature
- 随机初始化K个聚类中心u1、u2、…、uk
然后重复以下步骤：
（1）对第1~m个样本，计算到K各聚类中心的距离||x(i)-u k||，将其划分(染色)给最接近该样本点的聚类中心【划分训练集各样本点】
（2）对于第1~K个聚类中心，u k=第k类样本的均值【移动聚类中心】
K-means分离不佳簇问题扩展：
若存在某个聚类中心并没有分类到样本点：
（1）删去该聚类中心–>K-1个分类【通常做法】
（2）重新随机初始化这个聚类中心
假设存在某一家服装厂，记录了客户的身高和体重；想要设计小、中、大三种尺寸的服装，该如何设计？
可以使用K-means将上图数据分成三类，再针对性的对各类样本进行尺寸设计。
c(i) ：第i个样本所属的簇的索引或序号
uk ：第k个聚类中心的位置
uc(i) ：第i个样本所属簇的聚类中心的位置
K-means的优化目标函数：
J(c,u)表示各样本点到样本所属簇聚类中心的距离，minJ(c,u)是希望各样本点到所属簇聚类中心距离达到最小
K-means算法过程就是在最小化目标函数J(c,u)
- 应该确保K
- 随机选取K个训练集样本
- 将k个聚类中心赋值为这K个训练集样本
对于不同的初始化，可能收敛到不同的局部最优
例如下图，你可能会收敛到三种不同的分类结果
为了避免K-means落到局部最优，应该进行多次随机初始化。
例如上图，进行了100次随机初始化，得到了很多种分类结果；接下来要做的就是在很多分类结果中选取代价函数最小的一个。
如何选取聚类数量K当K较小时，多次随机初始化优化效果会很好；
当K较大时，多次随机初始化效果不会很明显。
如下图，同一份数据可以划分成2类或者4类，这两种分类都可以说是正确的。因为这是无监督学习，因此不存在所谓的绝对正确答案。
在讨论K的选择时，一般会讨论到一个方法，叫作肘部法则
不断改变的K，画出代价函数J，根据图像选取合适的K。
如上图，在K=3时，代价函数下降缓慢，因此我们可以选择K=3。
但在实际应用中，代价函数图像并没有上述的那么"友好"，如下图：
你不知道该选择3还是4，或者是5；因此肘部法制在这里并不能很好的确定K的值。
此外，你可以通过分类的后续目的去考虑K值。例如，某厂家要根据客户身高、体重来设计不同大小的尺寸。
当K=3，可把尺寸设计为S、M和L；当K=5，可把尺寸设计为XS、S、M、L、XL。
此时可以通过背后的经济价值去考虑K=3还是5。
1、读入数据集
import pandas as pd#读入csv文件
import numpy as np#处理数据
import random #随机初始化需要使用
#导入数据集
iris = pd.read_csv("iris.csv",header=None)
iris.head(10)
数据头十行如下图所示
为了可视化，只考虑前两个特征
#读取鸢尾花的前两个特征 feature = iris.iloc[:,0:2] #转换成数组 feature = np.array(feature)
2、随机初始化，获得K个聚类中心
'''
dataset:数据集
K:聚类中心个数
'''
def create_centrois(dataset,K):
data = dataset[random.sample(range(0,len(dataset)),K)]
return data
random.sample(range(0,len(dataset)),K)：
随机产生K个数，范围从0到len(dataset)。代表选取数据集中的下标
3、计算欧式距离
def get_distance(dataset,centrois):
K = len(centrois)#聚类数
m = len(dataset)#样本个数
#计算各样本到K个聚类中心的聚类：m*K大小的二维数组，先初始化为0
distance = np.zeros((m,K))
#进行K轮循环，计算各样本点到第k个聚类中心的距离
for k in range(K):
#获取第k个聚类中心坐标
center = centrois[k]
#计算欧式距离
#tile(a,(x,y))-->将a沿x轴扩大x倍，y轴扩大y倍
#(tile作用就是将聚类中心坐标扩变的和数据集一样大，以进行逐位相减)
dis = np.tile(center,(m,1))-dataset
#平方
sqrDis = dis**2
#按行相加
sqrDisSum = sqrDis.sum(axis=1)
#赋值到distance的第k列
distance[:,k]=sqrDisSum
return distance
4、绘图函数
from matplotlib import pyplot as plt
'''
dataset：数据集
lab：分类结果(标签)
centers：K个聚类中心的坐标数组
dic_colors：设置颜色
'''
def draw_kmeans(dataset,lab,centers,dic_colors=None):
#清除画布
plt.cla()
#转换成一维数组
lab = lab.flatten()
#将标签转换成列表在通过集合去重
#val_labs表示目前有几类别，每个类别的标签
val_labs = set(lab.tolist())
#遍历集合val_labs
for i,val in enumerate(val_labs):
#获取标签位val的样本下标
index = np.where(lab==val)
#将这一类样本的坐标都存到一个数组里面
sub_dataset = dataset[index]
#散点图绘制(这里只有两个特征)
plt.scatter(sub_dataset[:,0],sub_dataset[:,1],s=14,color = dic_colors[i])
#绘制聚类样本中心
for i in range(np.shape(centers)[0]):
plt.scatter(centers[i,0],centers[i,1],s=200,color = "k",marker="+")
plt.show()
5、K-means函数
'''
dataset:数据集
K：聚类个数
iter:最大迭代次数(最多移动聚类中心次数)
draw:是否绘图
'''
def K_means(dataset,K,iter=20,dic_colors=None,draw=False):
#m：样本个数；n:样本维度
m,n = np.shape(dataset)
#随机初始化聚类中心
centrois = create_centrois(dataset,K)
#类别标签初始化位0，表示都属于一类
lab = np.zeros(m)
if draw:
#画出未分类时的数据图像
draw_kmeans(dataset,lab,centrois,dic_colors)
#迭代iter次，每次更新一次聚类中心
for i in range(iter):
#获得欧式距离
distance = get_distance(dataset,centrois)
#划分样本
#argmin返回最小值所在的序号(列)，axis=1按行比较
#最小距离所在的序号即当前所属标签
lab_new = np.argmin(distance,axis=1)
#目标函数值
cost = np.sum(np.min(distance,axis=1))/m
print("第%d次聚类目标函数值为%.2f"%(i,cost))
if draw:
#第i次聚类结果
draw_kmeans(dataset,lab,centrois,dic_colors)
#计算新的聚类中心
for k in range(K):
index = np.where(lab_new==k)[0]
#取均值
centrois[k,:] = np.mean(dataset[index,:],axis=0)
if draw:
#新值作为聚类中心，进行绘图
draw_kmeans(dataset,lab,centrois,dic_colors)
#聚类中心不变，则退出
if np.sum(lab_new-lab) == 0:
return lab_new
else:
#聚类中心移动，进入下一次迭代
lab = lab_new
#返回分类结果
return lab
6、调用
K_means(feature,3,20,['red','green','blue'],False)
聚类结果：
真实的聚类结果：
7、完整代码
import pandas as pd#读入csv文件
import numpy as np#处理数据
import random #随机初始化需要使用
#导入数据集
iris = pd.read_csv("iris.csv",header=None)
iris.head(10)
#读取鸢尾花的前两个特征
feature = iris.iloc[:,0:2]
#转换成数组
feature = np.array(feature)
'''
dataset:数据集
K:聚类中心个数
'''
def create_centrois(dataset,K):
data = dataset[random.sample(range(0,len(dataset)),K)]
return data
def get_distance(dataset,centrois):
K = len(centrois)#聚类数
m = len(dataset)#样本个数
#计算各样本到K个聚类中心的聚类：m*K大小的二维数组，先初始化为0
distance = np.zeros((m,K))
#进行K轮循环，计算各样本点到第k个聚类中心的距离
for k in range(K):
#获取第k个聚类中心坐标
center = centrois[k]
#计算欧式距离
#tile(a,(x,y))-->将a沿x轴扩大x倍，y轴扩大y倍
#(tile作用就是将聚类中心坐标扩变的和数据集一样大，以进行逐位相减)
dis = np.tile(center,(m,1))-dataset
#平方
sqrDis = dis**2
#按行相加
sqrDisSum = sqrDis.sum(axis=1)
#赋值到distance的第k列
distance[:,k]=sqrDisSum
return distance
from matplotlib import pyplot as plt
'''
dataset：数据集
lab：分类结果(标签)
centers：K个聚类中心的坐标数组
dic_colors：设置颜色
'''
def draw_kmeans(dataset,lab,centers,dic_colors=None):
#清除画布
plt.cla()
#转换成一维数组
lab = lab.flatten()
#将标签转换成列表在通过集合去重
#val_labs表示目前有几类别，每个类别的标签
val_labs = set(lab.tolist())
#遍历集合val_labs
for i,val in enumerate(val_labs):
#获取标签位val的样本下标
index = np.where(lab==val)
#将这一类样本的坐标都存到一个数组里面
sub_dataset = dataset[index]
#散点图绘制(这里只有两个特征)
plt.scatter(sub_dataset[:,0],sub_dataset[:,1],s=14,color = dic_colors[i])
#绘制聚类样本中心
for i in range(np.shape(centers)[0]):
plt.scatter(centers[i,0],centers[i,1],s=200,color = "k",marker="+")
plt.show()
'''
dataset:数据集
K：聚类个数
iter:最大迭代次数(最多移动聚类中心次数)
draw:是否绘图
'''
def K_means(dataset,K,iter=20,dic_colors=None,draw=False):
#m：样本个数；n:样本维度
m,n = np.shape(dataset)
#随机初始化聚类中心
centrois = create_centrois(dataset,K)
#类别标签初始化位0，表示都属于一类
lab = np.zeros(m)
if draw:
#画出未分类时的数据图像
draw_kmeans(dataset,lab,centrois,dic_colors)
#迭代iter次，每次更新一次聚类中心
for i in range(iter):
#获得欧式距离
distance = get_distance(dataset,centrois)
#划分样本
#argmin返回最小值所在的序号(列)，axis=1按行比较
#最小距离所在的序号即当前所属标签
lab_new = np.argmin(distance,axis=1)
#目标函数值
cost = np.sum(np.min(distance,axis=1))/m
print("第%d次聚类目标函数值为%.2f"%(i,cost))
if draw:
#第i次聚类结果
draw_kmeans(dataset,lab,centrois,dic_colors)
#计算新的聚类中心
for k in range(K):
index = np.where(lab_new==k)[0]
#取均值
centrois[k,:] = np.mean(dataset[index,:],axis=0)
if draw:
#新值作为聚类中心，进行绘图
draw_kmeans(dataset,lab,centrois,dic_colors)
#聚类中心不变，则退出
if np.sum(lab_new-lab) == 0:
return lab_new
else:
#聚类中心移动，进入下一次迭代
lab = lab_new
#返回分类结果
return lab
if __name__=="__main__":
K_means(feature,3,20,['red','green','blue'],False)
三、降维
1. 什么是降维
例如存在两个特征x1，x2，x1表示该对象的英寸长度，x2表示该对象的厘米长度。
我们可以通过降维，将二维数据降成一维数据。只通过一个特征来表示对象的长度
降维意味着什么呢？
现在对于第i个样本x(i)，可以需要二维的数据才能表示。降维后意味着仅需要一维数据z(i)就可以表示x(i)，如下图。【x(i)→z(i)】
降维后，只需要一个值就可以指定在二维图中直线上的位置。
2. 主成分分析方法(principal components analysis，PCA)三维降成二维的例子：
图中的三维数据大致都处于一个平面，因此可以将此投影在一个二维平面上，从而降为二维的数据。
【三维投影到面，二维投影到线】
对于二维的数据降维，其实就是找到一条一维的投影(线)；各样本到该投影的距离最小。
所以，PCA做的就是找一条低纬平面，然后将数据投影在上面，使各样本到该投影的长度平方(投影误差)最小
对于2维到1维:我们需要找到一个向量u(1)【u(1)是正是负都可以，即方向不重要，投影误差最小即可】
对于高纬的数据：
从n维降到k维：找到k个向量:u(1),u(2),…,u(k)；我们要将数据投影到这k个向量展开的线性子空间上。
PCA过程(n维数据降到k维)PCA与线性回归
(1)他们想缩小的误差，在方向上不同。线性回归是缩小在x轴投影上的误差；PCA是缩小到投影线的误差。
(2)线性回归有特殊的值y，而PCA钟的变量都是平等对待的。
1、 在使用PCA之前需要对数据进行预处理，与监督学习的特征缩放相同。
（1）对于每个feature，减去其对应的均值【期望变成0】
(2)若各feature取值范围跨度差距大，除于max-min或者标准差
2、计算协方差矩阵(covariance matrix)
∑是一个n*n的矩阵
（1）前面的∑表示希腊字母σ的大写，表示协方差；后面的是求和符号。两者不相同
（2）特征缩放后期望为0，所以协方差就是两个输入的内积
3、 计算协方差矩阵(Sigma)的特征向量。
下图是octave代码
S对应的是奇异值分解中的奇异值矩阵，奇异值类似方阵中的特征值，是表示特征值向量重要程度的一个东西。S中的矩阵是按照奇异值递减排序的，所以取前k个就能得到最重要的k个向量。这k个向量作为我们降维后要用的特征向量，这k个特征向量蕴含了原来的特征的绝大部分，所以用他们来代替而不损伤太多信息。
4、奇异值分解后，从特征向量中选取前K个特征向量；得到一个n*k的矩阵，称为为U_reduce矩阵
5、降维
将U_reduce转置乘于输入x(i)，得到一个k*1矩阵，从而实现降维。
在PCA中我们将n维的输入x降到了k维的z，那能否通过k维的z返回到原来的n维x呢？
降维过程如下图所示：
U是酉矩阵，即UUT=1，上图式子右边同时乘于U得到：x_approx =U_reduce*z
4. 选择K值关于什么是x_approx：
（1）首先z是x投影到k维平面上的坐标。例如三维降到二维，z是在二维平面上的坐标
（2）我们逆向从z推导x，逆推的是x在n维空间中的z维平面上的坐标，这个坐标就是x_approx举个实例:x_approx就是下图图(b)坐标，而不是逆推到图(a)中的坐标
Average squared projection erro:投影后的平均均方误差。这个误差可以看作投影过后与原数据的差异程度，误差过大则原数据之间的关系信息很多都丢失了。所以我们希望Average squared projection erro越小越好
Total variation in data:训练集的总方差,也可以看作与原点之间的距离。
选择K值时希望能够满足下面的条件：
也可以不选择0.01，当我们讨论选择k时，不是直接选择k，而是要选择0.01这个数字或者其他数字。
这里选择了0.01，用术语说是保留了99%的方差特性。或者用另一种PCA的说法是99%的差异值被保留下来了。
大于等于85%的值都是比较典型的，95%-99%是比较常用的。
选择实现过程
从k=1开始计算这个数值，若不等式不成立则让k=2，k=3……，假设到k=17时满足了不等式则用17作为k值。
但是这种选择算法效率并不高，好在奇异值分解svd可以让这个事好算很多
SVD会返回三个值，其中S是一个对角矩阵，对于给定的k，我们可以将不等式左部进行替换，如下图：
从而验证下图式子即可:
选择满足不等式的最小k值即可
这样就可以只调用一次svd函数得到S矩阵，迭代计算S矩阵中的数值
5. 应用PCA的建议通常运用PCA对监督学习算法进行加速。
例如下图，在监督学习原始训练集数据中，输入x是10000维的数据，数量级很大训练过程会很复杂；可以通过PCA降维成1000维的数据集，降低了训练的复杂性。
PCA做的是寻找x到z的映射，对于测试集中的样本，也应该经过PCA降维后再输入到假设模型中。
PCA的应用：
（1）能进行压缩，减少存储空间
（2）加快算法速度
（3）可视化数据
PCA的错误用法：去防止过拟合：
推荐使用正则化来防止过拟合
在使用PCA前应该先考虑完整的原始数据是否能满足你的需要；当内存不够或训练速度过慢才应该考虑PCA。
