织梦网站后台打开空白,网站设计论文介绍,个人网站例子,wordpress调用上传文章目录1. 聚类基本概念1.1 相似度、距离1.2 类、簇1.3 类之间的距离2. 层次聚类3. K均值聚类3.1 模型3.2 策略3.3 算法3.4 算法特性4. sklearn.cluster4.1 sklearn.cluster.KMeans k均值聚类4.2 Hierarchical clustering 层次聚类聚类#xff1a;依据样本特征的相似度或距离…
文章目录1. 聚类基本概念1.1 相似度、距离1.2 类、簇1.3 类之间的距离2. 层次聚类3. K均值聚类3.1 模型3.2 策略3.3 算法3.4 算法特性4. sklearn.cluster4.1 sklearn.cluster.KMeans k均值聚类4.2 Hierarchical clustering 层次聚类聚类依据样本特征的相似度或距离将其归并到若干个“类”或“簇”的数据分析问题 聚类目的通过得到的类或簇来发现数据的特点或对数据进行处理在数据挖掘、模式识别等领域有着广泛的应用 聚类 属于无监督学习因为只是根据样本的相似度或距离将其进行归类而类或簇事先并不知道
1. 聚类基本概念
1.1 相似度、距离
有多种相似度或距离的定义相似度直接影响聚类的结果其选择很关键
闵可夫斯基距离 dij(∑k1m∣xki−xkj∣p)1pd_{ij} \bigg(\sum\limits_{k1}^m |x_{ki} - x_{kj}|^p \bigg)^{\frac{1}{p}}dij(k1∑m∣xki−xkj∣p)p1 , 距离越大相似度越小 p1p1p1, 曼哈顿距离 p2p2p2, 欧式距离 p∞p\inftyp∞, 切比雪夫距离dijmaxk∣xki−xkj∣d_{ij} \max\limits_k |x_{ki} - x_{kj}|dijkmax∣xki−xkj∣ 马哈拉诺比斯距离 考虑各个分量特征之间的相关性与各个分量的尺度无关距离越大相似度越小
dij[(xi−xj)TS−1(xi−xj)]1/2,S为样本协方差矩阵d_{ij}[(x_i-x_j)^TS^{-1}(x_i-x_j)]^{1/2}, \quad S 为样本协方差矩阵dij[(xi−xj)TS−1(xi−xj)]1/2,S为样本协方差矩阵 马氏距离是欧氏距离的推广。 相关系数其绝对值越接近1越相似越接近0越不相似 rij∑k1m(xki−xˉi)(xkj−xˉj)[∑k1m(xki−xˉi)2∑k1m(xkj−xˉj)2]1/2r_{ij}\frac{\sum\limits_{k1}^m(x_{ki }- \bar x_i)(x_{kj}- \bar x_j)}{\bigg[\sum\limits_{k1}^m(x_{ki }- \bar x_i)^2\sum\limits_{k1}^m(x_{kj}- \bar x_j)^2 \bigg]^{1/2}}rij[k1∑m(xki−xˉi)2k1∑m(xkj−xˉj)2]1/2k1∑m(xki−xˉi)(xkj−xˉj) 夹角余弦 夹角余弦越接近于1表示样本越相似越接近于0表示样本越不相似 sij∑k1mxkixkj[∑k1mxki2∑k1mxkj2]1/2s_{ij} \frac{\sum\limits_{k1}^m x_{ki}x_{kj}}{\bigg[ \sum\limits_{k1}^m x_{ki}^2 \sum\limits_{k1}^m x_{kj}^2\bigg]^{1/2}}sij[k1∑mxki2k1∑mxkj2]1/2k1∑mxkixkj 从距离的角度看A和B比A和C更相似从相关系数的角度看A和C比A和B更相似进行聚类时选择适合的距离或相似度非常重要
1.2 类、簇
聚类得到的类或簇本质是样本的子集如果假定一个样本只能属于一个类或类的交集为空集称为硬聚类hard clustering如果一个样本可以属于多个类或类的交集不为空集称为软聚类soft clustering
类、簇定义dij≤Td_{ij} \le Tdij≤T 最常用且能推出下面的1nG−1∑xj∈Gdij≤T\frac{1}{n_G-1}\sum\limits_{x_j \in G}d_{ij} \le TnG−11xj∈G∑dij≤T1nG(nG−1)∑xi∈G∑xj∈Gdij≤T,dij≤V\frac{1}{n_G(n_G-1)}\sum\limits_{x_i \in G}\sum\limits_{x_j \in G}d_{ij} \le T ,\quad d_{ij} \le VnG(nG−1)1xi∈G∑xj∈G∑dij≤T,dij≤V
类的特征
类的均值中心xˉG1nG∑i1nGxi\bar x_G \frac{1}{n_G}\sum\limits_{i1}^{n_G}x_ixˉGnG1i1∑nGxi类的直径DGmaxxi,xj∈GdijD_G \max\limits_{x_i,x_j \in G} d_{ij}DGxi,xj∈Gmaxdij类的样本散布矩阵AG∑i1nG(xi−xˉG)(xi−xˉG)TA_G\sum\limits_{i1}^{n_G}(x_i-\bar x_G)(x_i-\bar x_G)^TAGi1∑nG(xi−xˉG)(xi−xˉG)T类的样本协方差矩阵SG1m−1AG1m−1∑i1nG(xi−xˉG)(xi−xˉG)T,m样本维数S_G\frac{1}{m-1}A_G\frac{1}{m-1}\sum\limits_{i1}^{n_G}(x_i-\bar x_G)(x_i-\bar x_G)^T, m样本维数SGm−11AGm−11i1∑nG(xi−xˉG)(xi−xˉG)T,m样本维数
1.3 类之间的距离 最短距离或单连接Dpqmin{dij∣xi∈Gp,xj∈Gq}D_{pq} \min \{d_{ij}|x_i \in G_p,x_j \in G_q\}Dpqmin{dij∣xi∈Gp,xj∈Gq} 最长距离或完全连接Dpqmax{dij∣xi∈Gp,xj∈Gq}D_{pq} \max \{d_{ij}|x_i \in G_p,x_j \in G_q\}Dpqmax{dij∣xi∈Gp,xj∈Gq} 中心距离DpqdxˉpxˉqD_{pq} d_{\bar x_p\bar x_q}Dpqdxˉpxˉq 平均距离Dpq1npnq∑xi∈Gp∑xj∈GqdijD_{pq} \frac{1}{n_p n_q}\sum\limits_{x_i \in G_p}\sum\limits_{x_j \in G_q}d_{ij}Dpqnpnq1xi∈Gp∑xj∈Gq∑dij
2. 层次聚类
层次聚类 假设类别之间 存在层次结构将样本聚到层次化的类中层次聚类有聚合agglomerative或自下而上bottom-up聚类、分裂divisive或自上而下top-down聚类 两种方法每个样本只属于 一个类所以层次聚类属于 硬聚类
聚合聚类
将每个样本 各自分到一个类之后将相距最近的两类合并建立一个新的类重复上一步直到满足停止条件得到层次化的类别
分裂聚类
将所有样本分到一个类之后将已有类中相距最远的样本分到两个新的类重复上一步直到满足停止条件得到层次化的类别。
聚合聚类的具体过程如下
对给定的样本集合开始将每个样本分到一个类按照一定规则例如 类间距离最小将 最 满足规则条件的两个类进行合并反复上一步每次减少一个类直到满足停止条件如 所有样本聚为一类
聚合聚类需要预先确定三要素
1距离或相似度闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦2合并规则类间距离最小可以是 最短距离、最长距离、中心距离、平均距离3停止条件类的个数达到阈值极端情况类的个数是1、类的直径超过阈值
3. K均值聚类
k均值 聚类是基于样本集合划分的聚类算法
将样本集合划分为 k 个子集构成 k 个类将 n 个样本分到 k 个类中每个样本到其所属类的中心的距离最小每个样本只能属于一个类是硬聚类
3.1 模型
n 个样本 划分成 k 个类类之间的交集为空硬聚类
3.2 策略
策略通过损失函数的最小化 选取 最优的划分 或 函数 C∗C^*C∗
样本距离欧氏距离d(xi,xj)∣∣xi−xj∣∣2d(x_i,x_j)||x_i-x_j||^2d(xi,xj)∣∣xi−xj∣∣2损失函数样本与其类属的中心的距离总和 W(C)∑l1k∑C(i)l∣∣xi−xˉl∣∣2W(C) \sum\limits_{l1}^k\sum\limits_{C(i)l} ||x_i-\bar x_l||^2W(C)l1∑kC(i)l∑∣∣xi−xˉl∣∣2本质求解最优化问题 C∗arg minCW(C)arg minC∑l1k∑C(i)l∣∣xi−xˉl∣∣2C^* \argmin\limits_C W(C) \argmin\limits_C \sum\limits_{l1}^k\sum\limits_{C(i)l} ||x_i-\bar x_l||^2C∗CargminW(C)Cargminl1∑kC(i)l∑∣∣xi−xˉl∣∣2
n 个样本 划分成 k 个类组合数是指数级的其最优解求解是 NP 困难问题常用迭代求解
3.3 算法
k均值聚类 的算法是迭代的过程每次迭代包括两个步骤
首先随机选择 k 个类的中心选 k 个样本将其余样本逐个指派到与其最近的中心的类中得到一个聚类结果然后更新每个类的样本的均值作为类的新的中心重复以上步骤直到收敛
3.4 算法特性
1. 总体特点
基于划分的聚类方法类别数 k 事先指定以欧氏距离平方表示样本之间的距离以中心或样本的 均值 表示类别以 样本 和 其所属类的中心 之间的 距离的总和 为最优化目标函数得到的类别是平坦的、非层次化的是迭代算法不能 保证得到全局最优
2. 收敛性
k均值 聚类属于启发式方法不能 保证收敛到全局最优初始中心的选择 会 直接影响聚类结果类中心在聚类的过程中会发生移动但是往往不会移动太大因为在每一步样本被分到与其最近的中心的类中
3. 初始类的选择
选择不同的初始中心会得到不同的聚类结果初始中心的选择比如 可以用层次聚类对样本进行聚类得到k个类时停止。然后从每个类中选取一个与中心距离最近的点
4. 类别数k的选择
k 值需要预先指定而在实际应用中最优k值是不知道的解决方法尝试不同的k值检验聚类的质量推测最优的k值聚类结果的质量可以用类的平均直径来衡量一般地类别数变小时平均直径会增加类别数变大超过某个值以后平均直径会不变而这个值正是最优的k值可以采用二分查找快速找最优的k值 4. sklearn.cluster
sklearn.cluster 官网介绍了10种聚类算法。
4.1 sklearn.cluster.KMeans k均值聚类
sklearn.cluster.KMeans 官网参数介绍
class sklearn.cluster.KMeans(n_clusters8, initk-means, n_init10,
max_iter300, tol0.0001, precompute_distancesauto, verbose0,
random_stateNone, copy_xTrue, n_jobsNone, algorithmauto)主要参数 n_clusters, default8 类的个数即k值 init{‘k-means’, ‘random’} 初始中心选择默认选项更好 n_init, default10 多次初始化然后聚类最后取最好的聚类结果 max_iter, default300 单次聚类的最大迭代次数 tol, default1e-4 迭代停止精度 precompute_distances‘auto’ or bool, default’auto’ 预先计算距离 algorithm{“auto”, “full”, “elkan”}, default”auto” 迭代算法. The classical EM-style algorithm is “full”. The “elkan” variation is more efficient by using the triangle inequality, but currently doesn’t support sparse data. “auto” chooses “elkan” for dense data and “full” for sparse data. 代码示例
from sklearn.cluster import KMeans
import numpy as np
# 书上例题
X np.array([[0, 2], [0, 0], [1, 0], [5, 0], [5, 2]])
kms KMeans(n_clusters2).fit(X)
print(kms.labels_)
print(kms.cluster_centers_)运行结果
[0 0 0 1 1]
[[0.33333333 0.66666667][5. 1. ]]4.2 Hierarchical clustering 层次聚类
sklearn.cluster.AgglomerativeClustering
class sklearn.cluster.AgglomerativeClustering(n_clusters2, affinityeuclidean,
memoryNone, connectivityNone, compute_full_treeauto, linkageward,
distance_thresholdNone)官方代码示例
