算法概括

机器学习有两种学习类型：

• 有监督学习：即数据点有已知的结果。
• 无监督学习：即数据点没有已知的结果，利用无标签的数据学习数据的分布或数据与数据之间的关系被称作无监督学习。
  注：
  ①有监督学习和无监督学习的最大区别在于数据是否有标签。
  ②无监督学习最常应用的场景是聚类和降维，聚类算法用于识别数据中未知的结构，降维则是使用数据中的结构特征来简化数据。

聚类（clustering）

聚类的概念

• 聚类就是根据数据的“相似性”将数据分为多类的过程。
• 聚类把各不相同的个体分割为有更多相似子集合的工作。
• 聚类生成的子集合称为簇。

聚类的要求

• 生成的簇内部的任意两个对象之间具有较高的相似度。
• 属于不同簇的两个对象间具有较高的相异度
  

聚类与分类的区别

之前学习过k近邻算法分类算法，分类和聚类听上去好像很相似，但是两者完全是不同的应用和原理。
例如，根据下图的四个属性进行预测某一输入的所属类别：

概括而来就是这样一个流程：

可以看出训练样本是有明确的标签的，数据点是有已知结果的，而聚类不同，聚类算法本身训练的样本就是无标签的，你不知道它属于哪一类，而把具有空间相近性、性质相似性的数据点归为一类，这就是聚类算法要做的事情。
还是上面的例子：

这个时候训练样本的标签被盖住了，我们必须从这四个属性入手，把样本聚合成不同的簇，每个簇中的数据点的属性最相似。
概括而来就是这样一个过程：

现在小结一下，分类和聚类的区别概括而来就是这样：

分类：学习/训练有监督，训练样本有明确标签。
聚类：学习/训练过程无监督，样本无明确标签。
聚类与分类的区别在于聚类不依赖于预先定义的类，没有预定义的类和样本——聚类是一种无监督的数据挖掘任务。

常见算法分类

• 划分聚类： 大部分方法是基于距离的聚类算法。如：K-Means、K-Medoids、CLARANS等。
• 层次聚类： 例如：BIRCH、CURE、CHAMELEON等。层次聚类可采用“自底向上”或“自顶向下”方案。在“自底向上”方案中，初始时每一个数据纪录都被视作一个单独的簇，接着再把那些相互邻近的簇合并成一个新的簇，直到所有的记录都在一个簇或者满足某个终止条件为止。
• 密度聚类： 该方法是基于（结点）密度的聚类算法，主要算法有：DBSCAN、OPTICS、DENCLUE等。只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。
• 网格聚类： 主要算法有：STING、CLIQUE、WAVE-CLUSTER。将数据空间按某种特征（属性）划分成网格，聚类处理以网格（单元）为基本单位。
  注：
  ①后边三种聚类不做介绍，主要以划分聚类中的K-Means算法作为本章学习重点。
  ②需要说明的是，这些算法本身无所谓优劣，而最终运用于数据的效果却存在好坏差异，这在很大程度上取决于数据使用者对于算法的选择是否得当。

聚类算法中存在的问题

• ①高维数据集中存在大量无关的属性，所有维中存在簇的可能性几乎为零。
• ②高维空间中数据较低维空间中数据分布稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此在高维空间中无法基于距离来构建簇。

距离度量

评估两个不同样本之间的“相似性”，通常使用的方法就是计算两个样本之间的“距离”，使用不同的方法计算样本间的距离关系到聚类结果的好坏。
大多数聚类分析是以相似性计算为基础的，同一个聚类中的个体模式相似，不在同一个聚类中的个体模式则相异。目前，相似性距离的计算都是基于向量的，也就是计算两个向量的距离，距离相近则相似度越大。
下面，介绍几种常见的距离计算方法。

闵可夫斯基距离

闵可夫斯基距离（Minkowski Distance）是一种常见的方法，用于衡量数值点之间距离。
假设
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1​,x2​,...,xn​）,Y（y1​,y2​,...,yn​)是n维空间的两个向量，那么，闵可夫斯基距离定义为：

d
i
s
t
（
X
,
Y
）
=
∑
k
=
1
n
∣
x
k
−
y
k
∣
p
p
dist（X,Y）=\sqrt[p]{\textstyle \sum_{k=1}^{n} |x_k-y_k|^p}
dist（X,Y）=p∑k=1n​∣xk​−yk​∣p​
注：该距离最常用的p是2和1，前者是欧几里得距离，后者是曼哈顿距离。当p趋近于无穷大时，闵可夫斯基距离转化为切比雪夫距离。

闵可夫斯基距离计算距离如下：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)
dist=np.linalg.norm(x-y,ord=4)#闵可夫斯基距离，此时p=4

欧式距离（欧几里得距离）

欧式距离（Euclidean Distance）最初用于计算欧几里得空间中两个点的距离。假设
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1​,x2​,...,xn​）,Y（y1​,y2​,...,yn​)是n维空间的两个向量，它们之间的欧几里得距离是：

d
i
s
t
（
X
,
Y
）
=
∑
k
=
1
n
(
x
k
−
y
k
)
2
p
dist（X,Y）=\sqrt[p]{\textstyle \sum_{k=1}^{n} (x_k-y_k)^2}
dist（X,Y）=p∑k=1n​(xk​−yk​)2​
n=2欧几里得距离就是平面上两个点的距离。如果欧式距离看作物品相似程度，那么距离越近就越相似，也就是说距离越小，相似度越大。

欧式距离计算举例如下：

import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=dis.pdist(X,metric='euclidean')
#或者直接按照闵可夫斯基距离的计算方式
dist=np.linalg.norm(x-y,ord=2)

曼哈顿距离

曼哈段距离也称为城市街区距离（City Block distance），或绝对距离。即在欧几里得空间的固定直角坐标系上两点所形成的线段对轴的投影距离总和。
坐标
(
x
1
,
y
1
)
(x_1,y_1)
(x1​,y1​)的点
P
1
P_1
P1​与坐标
(
x
2
,
y
2
)
(x_2,y_2)
(x2​,y2​)的点
P
2
P_2
P2​的曼哈顿距离为：

d
i
s
t
(
P
1
,
P
2
)
=
∣
x
1
−
x
2
∣
+
∣
y
1
−
y
2
∣
dist(P_1,P_2)=|x_1-x_2|+|y_1-y_2|
dist(P1​,P2​)=∣x1​−x2​∣+∣y1​−y2​∣

曼哈顿距离计算Python语句如下：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)
dist=np.linalg.norm(x-y,ord=1)

切比雪夫距离

闵可夫斯基距离定义中，当p=$+\infty$时，称为切比雪夫距离（Chebyshev Distance）。
假设
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1​,x2​,...,xn​）,Y（y1​,y2​,...,yn​)是n维空间的两个向量，它们之间的切比雪夫距离是：

d
i
s
t
(
X
,
Y
)
=
lim
⁡
n
→
∞
)
(
∑
i
=
1
n
∣
x
i
−
y
i
∣
k
)
1
k
=
max
⁡
(
∣
x
i
−
y
i
∣
)
,
1
≤
i
≤
n
dist(X,Y) = \lim_{n \to \infty})(\sum_{i=1}^{n}|x_i-y_i|^k)^\frac{1}{k} = \max(|x_i-y_i|), 1 \leq i \leq n
dist(X,Y)=n→∞lim​)(i=1∑n​∣xi​−yi​∣k)k1​=max(∣xi​−yi​∣),1≤i≤n

切比雪夫距离计算Python语句如下：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)
dist=np.linalg.norm(x-y,ord=np.inf)

皮尔逊相关系数

皮尔逊相关系数（Pearson Correlation Coeffient）即相关分析中的相关系数r，一般用于计算两个定距变量间联系的紧密程度，它的取值在[-1，+1]之间。
当相关系数为0时，X和Y两变量无线性关系（不代表没有除了线性关系外的其他关系）；当X的值增大，Y也增大，正相关关系，相关系数在0.00与1.00之间；当X的值增大，Y减小，负相关关系，相关系数在-1.00与0.00之间。相关系数的绝对值越大，相关性越强，相关系数越接近于1和-1，相关度越强，相关系数越接近于0，相关度越弱。
公式如下：

r
(
x
,
y
)
=
E
(
x
y
)
−
E
(
x
)
(
y
)
E
(
x
2
)
−
(
E
(
x
)
)
2
E
(
y
2
)
−
(
E
(
y
)
)
2
=
c
o
v
(
x
,
y
)
σ
x
σ
y
r(x,y) = \frac{E(xy)-E(x)(y)}{\sqrt[]{E(x^2)-(E(x))^2}{\sqrt[]{E(y^2)-(E(y))^2}}} = \frac{cov(x,y)}{\sigma_x\sigma_y}
r(x,y)=E(x2)−(E(x))2​E(y2)−(E(y))2​E(xy)−E(x)(y)​=σx​σy​cov(x,y)​

皮尔逊相关系数计算Python语句如下：

import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=1-dis.pdist(X,metric='correlation')

余弦相似度

余弦相似度就是两个向量之间的夹角的余弦值。假设
X
（
x
1
,
x
2
,
.
.
.
,
x
n
）
,
Y
（
y
1
,
y
2
,
.
.
.
,
y
n
)
X（x_1,x_2,...,x_n）,Y（y_1,y_2,...,y_n)
X（x1​,x2​,...,xn​）,Y（y1​,y2​,...,yn​)是n维空间的两个向量，它们之间的余弦相似度是：

cos
⁡
θ
=
X
Y
∣
X
∣
∣
Y
∣
\cos \theta = \frac{XY}{|X||Y|}
cosθ=∣X∣∣Y∣XY​
余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离向量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度。
夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越大表示两个向量的夹角越大。当两个向量的方向重合时余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

余弦相似度计算Python语句如下：

import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=1-dis.pdist(X,metric='cosine')

欧几里得vs余弦距离

• 欧几里得距离适合于基于坐标的度量。
• 余弦距离更适合那些出现位置不重要的数据，例如文本数据。
• 欧几里得距离对维度灾难更敏感。

杰卡德相似系数

Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度，只关心个体间共同具有的特征是否一致这个问题。假设集合 A和 B，两个集合的杰卡德相似系数表示如下：

J
(
A
,
B
)
=
∣
A
∩
B
∣
∣
A
∪
B
∣
J(A,B)= \frac {|A∩B|}{|A∪B|}
J(A,B)=∣A∪B∣∣A∩B∣​

杰卡德相似距离计算Python语句如下：

import numpy as np
import scipy.spatial.distance as dis
x=np.random.random(10)
y=np.random.random(10)
X=np.vstack([x,y])
dist=dis.pdist(X,metric='jaccard')

划分聚类

K-means聚类算法

算法原理

k-means算法以k为参数，把n个对象分为k个簇，使簇内具有较高的相似度，而簇间的相似度较低。
其处理过程如下:
①随机选择k个点作为初始的聚类中心。
②对于剩下的点，根据其与聚类中心的距离，将其归入最近的簇。
③对于每个簇，计算所有点的均值作为新的聚类中心。
④重复2、3直到聚类中心不再发生改变。

算法流程如下所示：

如下图所示为聚类A、B、C、D、E五个点的聚类中心的选取过程：

基本概念

要得到簇的个数，需要指定K值。
质心：均值，即向量各维取平均即可。
距离的度量：常用欧几里得距离和余弦相似度（先标准化）。
优化目标：
min
⁡
∑
i
=
1
K
∑
x
∈
C
i
d
i
s
t
(
c
i
,
x
)
2
\min \sum_{i=1}^{K}\sum_{x \in C_i}^{}dist(c_i,x)^2
min∑i=1K​∑x∈Ci​​dist(ci​,x)2

算法实例

题目背景

练习算法实例，要求做到：
1、理解程序中每个函数以及每个变量的含义；
2、掌握k-means算法的实现过程；
3、使用k-means算法对下表中的5个样本进行聚类（k=2）。

k-means的手动实现

import numpy as np
def kmeans(X, k, max_iter=300):
    # 随机选择k个初始质心
    centroids = X[np.random.choice(X.shape[0], k)]
    for i in range(max_iter):
        # 计算每个样本点到质心的距离，并分配到最近质心所在的簇中
        distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))
        labels = distances.argmin(axis=0)
        # 重新计算每个簇的质心
        new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])
        # 检查质心是否变化，若没有则退出
        if np.all(centroids == new_centroids):
            break
        centroids = new_centroids
    return labels, centroids
X=np.array([[170,70],[178,75],[100,100],[120,40],[10,0.1]])
labels,centroids=kmeans(X,k=2)
print("当k=3时,簇划分情况为：",labels)
print("当k=3时,质心为：\n",centroids)

sklearn库中K-means算法

scikit-learn模块提供了k-Means聚类方法，原型为：
class sklearn.cluster.KMeans(n_clusters=8, init=’k-means++’, n_init=10, max_iter=300, tol=0.0001, precompute_distances=’auto’, verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm=’auto’)
主要参数包括：

• n_clusters：整型，可选，默认参数值为8，聚类数量。
• init：‘k-means++’，‘random’或者ndarray之一，默认为’k-means++’。
  ’k-means++’： 以一种巧妙的方式选择k-均值聚类的初始集群中心，以加快收敛速度。
  ‘random’：从初始质心的数据中随机选取 k 观察 (行)。
  ndarray：给出形状 (n_clusters, n_features)的初始中心。
• n_init：整型，默认参数值为10。用不同的初始化质心运行算法的次数。由于k-Means是结果受初始值影响的局部最优的迭代算法，因此需要多跑几次以选择一个较好的聚类效果。
• max_iter：整型，默认参数值为300，最大的迭代次数。
• tol：浮点型，默认参数值为0.0001，最小容忍误差，当误差小于tol就会退出迭代。
• algorithm：可以是‘auto’，‘full’或者’elkan’之一，默认参数值为’auto’。’full’适合于EM类算法；’elkan’适合于三角形不等式，但暂不支持稀疏数据；而当设置为’auto’时，稠密数据用’elkan’，稀疏数据用’full’。
• random_state：整型，RandonState实例或None，默认参数值为None。具体如下：
  int：该参数用于设置随机数发生器的种子；
  RandonState instance：该参数是一个随机数发生器；
  None：使用np.random作为随机数发生器。

import numpy as np
from sklearn.cluster import KMeans
#使用k-means算法对数据进行聚类
X=np.array([[170,70],[178,75],[100,100],[120,40],[10,0.1]])
kmeans_model=KMeans(n_clusters=2,init="k-means++")
kmeans_model.fit(X)
print("当k=2时,簇划分情况为：",kmeans2_model.labels_)
print("当k=2时,质心为：\n",kmeans2_model.cluster_centers_)

聚类分析的度量

• 聚类分析的度量指标用于对聚类结果进行评判，分为内部指标和外部指标两大类：
  外部指标指用事先指定的聚类模型作为参考来评判聚类结果的好坏。
  内部指标是指不借助任何外部参考，只用参与聚类的样本评判聚类结果好坏。
• 聚类的目标是得到较高的簇内相似度和较低的簇间相似度，使得簇间的距离尽可能大，簇内样本与簇中心的距离尽可能小。
• 聚类得到的簇可以用聚类中心、簇大小、簇密度和簇描述等来表示：
  聚类中心是一个簇中所有样本点的均值(质心)。
  簇大小表示簇中所含样本的数量。
  簇密度表示簇中样本点的紧密程度。
  簇描述是簇中样本的业务特征。

聚类评价指标

簇内平方和（Inertia）

• 每个数据点
  x
  i
  x_i
  xi​距其聚簇中心
  C
  k
  C_k
  Ck​的距离平方和
  
  ∑
  i
  =
  1
  n
  (
  x
  i
  −
  C
  k
  )
  2
  \sum_{i=1}^{n}(x_i-C_k)^2
  i=1∑n​(xi​−Ck​)2
• 值越小表示聚簇越紧密。

轮廓系数（Silhouette Coefficient）

• 对每个数据点计算一个轮廓系数：
  a=此数据点到同簇中所有其他点的平均距离，凝聚度。
  b=此数据点到最近簇中所有点的平均距离，分离度。
  
  S
  =
  b
  −
  a
  m
  a
  x
  (
  a
  ,
  b
  )
  S=\frac{b-a}{max(a,b)}
  S=max(a,b)b−a​
• 将所有数据点的轮廓系数取平均值就得到一个总的评分。
• 取值在[-1,1]之间，值越大，聚类效果越好。

簇类个数k的调整（了解）

选择正确的聚簇数

• Inertia衡量点到聚簇中心的距离的值会随着K的增大而不断降低，只要聚簇密度在不断增大，也就是说簇分的越多，每个簇的特征会愈加明显。
• 小于真实K值时，下降幅度很大；超过真实K值时，下降趋于平缓。
  
  选择轮廓系数最大的K值。
  

相似性度量

相似系数：
两个仅包含二元属性的对象之间的相似性度量也称相似系数。
两个对象的比较有四种情况：f00 = x取0并且y取0的属性个数；f01 = x取0并且y取1的属性个数；f10 = x取1并且y取0的属性个数；f11 = x取1并且y取1的属性个数
简单匹配系数：
SMC = 值匹配的属性个数 / 属性个数== (f11 +f00) / (f01 + f10 + f11 + f00)
Jaccard（杰卡德）系数：
J = 匹配的个数 / 不涉及0-0匹配的属性个数 = (f11) / (f01 + f10 +f11)

初始聚类中心的选择

K-means算法的初值敏感，容易陷入局部最小值，同一个算法运行两次有可能得到不同的结果，所以建议初始选点可以根据多次交叉去做，选择多次中心点。

更聪明的K-Means初始化方法
①随机地选取一点作为起始点。
②计算每个点与已有聚簇中心点之间的最短距离，D(x)。
③按照
D
(
x
)
2
/
∑
D
(
x
)
2
D(x)^2/\sum_{}^{}D(x)^2
D(x)2/∑​D(x)2的概率Income选取下一个点。
Kmeans++（分配聚簇）
kmeans++是为了解决初始值敏感问题：与kmeans区别是选择质心的方式不一样。
①从数据集中间，任选一个点作为质心。
②把所有样本到质心距离计算出来，选择较远的距离（从离中心点第一远，第二远，第三远，第四远，第五远中，选一个距离），作为另外一个质心，从而解决了在较近的距离选择两个点。
③这里有缺陷，选择的第二点依赖第一个点，第三点前依赖前两点，第四点依赖前三点。每次选择点都要计算所有中心点，到所有点的距离。计算量有点大。

注：初始质心的选择和聚类簇数k的选择都会对聚类结果产生影响，它们的选择会导致不同的聚类效果，因此需要进行多次实验，选择最优的初始质心、聚类簇数k。在极端情况下，有时候会出现局部最优解问题，即算法陷入局部最优解，无法到达全局最优解。总的来说，KMeans算法具有一定的随机性。

K-Means算法评价

• 优点：
  ①算法简单，易于理解。
  ②对球形簇样本聚类效果好。
  ③二分k均值等变种算法运行良好，不受初始化问题的影响。
• 缺点：
  ①不能处理非球形簇、不同尺寸和不同密度的簇，存在局限性。
  ②对离群点、噪声敏感。
  ③数据比较大的时候，收敛会比较慢。