网站轮播图片特效,广州做网站好的公司,网站建设的面试要求,淘宝上做网站权重1 聚类解决的问题
知识发现#xff0c;发现事物之间的潜在关系异常值检测特征提取 数据压缩的例子新闻自动分组、用户分群、图像分割、像素压缩等等 2 与监督学习比较
监督学习是需要给定X、Y#xff0c;X为特征#xff0c;Y为标签#xff0c;选择模型#xff0c;学习发现事物之间的潜在关系异常值检测特征提取 数据压缩的例子新闻自动分组、用户分群、图像分割、像素压缩等等 2 与监督学习比较
监督学习是需要给定X、YX为特征Y为标签选择模型学习目标函数最优化问题生成模型这个模型本质上是一组参数
无监督机器学习的数据只有X没有标签只根据X的相似度来做一些事情相似度的计算一般通过距离来度量。相似度高的聚类在一起进而可以对数据降维
3 聚类算法
主流的聚类算法可以分为两类划分聚类Partitioning Clustering和层次聚类Hierarchical Clustering。他们主要的区别是
划分聚类是一系列扁平的结构它们之间没有任何显式的结构来表名彼此的关联性。常见算法有K-means、K-medoids、Gaussian Mixture Model高斯混合模型、Spectral Clustering谱聚类、Centroid-based Clustering等层次聚类是具有层次结构的簇集合因此能够输出比划分聚类输出的无结构簇集合提供更丰富的信息。层次聚类可以认为是嵌套的划分聚类常见算法有Single-linkage、Complete-linkage、Connectivity-based Clustering等 4 相似度
X中的每一条数据都可以理解为多维空间中的一个点
相似度用点和点之间的距离衡量 欧氏距离 O p ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 ) O_p\sqrt {(x_1-x_2)^2(y_1-y_2)^2)} Op(x1−x2)2(y1−y2)2) ∣ x ∣ x 2 y 2 |x|\sqrt{x^2y^2} ∣x∣x2y2 明可夫斯基距离 d ( X , Y ) ( x 1 − y 1 ) p ( x 2 − y 2 ) p ( x 3 − y 3 ) p . . . ( x p − y p ) p p d(X,Y)\sqrt[p]{(x_1-y_1)^p(x_2-y_2)^p(x_3-y_3)^p...(x_p-y_p)^p} d(X,Y)p(x1−y1)p(x2−y2)p(x3−y3)p...(xp−yp)p p1时曼哈顿距离p2时欧氏距离p无穷切比雪夫距离哪个纬度值最大就是哪个差值作为距离 余弦距离 c o s θ a ⋅ b ∣ ∣ a ∣ ∣ ∣ ∣ b ∣ ∣ cos\theta\frac{a \cdot b} {||a||||b||} cosθ∣∣a∣∣∣∣b∣∣a⋅b c o s θ x 1 x 2 y 1 y 2 x 1 2 y 1 2 × x 2 2 y 2 2 cos\theta\frac{x_1x_2y_1y_2}{\sqrt{x_1^2y_1^2}\times \sqrt{x_2^2y_2^2}} cosθx12y12 ×x22y22 x1x2y1y2 拓展如何通过向量夹角理解不同“维度” 三角函数 sinx, cosx 的泰勒展开推导及两个巧妙应用_三角函数泰勒展开-CSDN博客 从图中很容易看出a/b/c之间的关系将a2b2-c^2作为一个判定因子Δ则Δ是abc三个变量的函数。对于同样一个角如果三角形边长过长则Δ会变动很大如果过小则Δ会变动很小也就是说没有归一化。为了消除边长的影响需要除以2ab保证Δ的范围在-1到1之间 为什么要用Δ除以2ab 根据三角形的公理两边之和大于第三边两边之差小于第三边得出abca-b那么c2的取值范围为(ab)2c2(a-b)2展开就是a2b22abc2a2b^2- 2ab于是判定因子Δa2b2-c^2的范围在-2ab到2ab之间这样就把Δ规范到了-1到1之间 cosθ(a2b2-c^2)/2ab 余弦距离在文本分类中使用很广余弦距离通过评价文章相似度 将文章分词将文章转变为词向量TFIDF逆文档频率如果将文章分词通过one-hot编码会产生稀疏的问题而TFIDF很好的解决了这个问题转换为词向量后将文章映射到高维空间变为一个向量文章之间的向量的余弦距离代表文章之间的相似度
4.1 文本相似度 TF-IDF TF在给定文档中某个词出现的概率即在谋篇文章中 某次出现的次数/谋篇文章的总次数。 DF语料库中包含某词的总文章数 IDFI 是inverse的意思代表某词在语料库中的重要程度为了减少经常用的词对于相似度的贡献比如“的”“是”这一类的词 TF-IDF: TF*IDF 4.2 数据相似度 Jaccard相似系数 主要用于计算符号度量或布尔值度量的个体间的相似度个体的特征属性由符号度量或者布尔值表示无法衡量差异具体值的大小只能获得“是否相同”这个结果所以Jaccard系数只判断个体间共同具有的特征是否一致的问题 用于网页去重、文本相似度分析 Pearson相关系数 线性相关系数对数据分布要求较高 理解pearson相关系数首先要理解协方差Covariance协方差是反映两个随机变量相关程度的指标如果一个变量跟随另一个变量同时变大或者变小那么这两个变量的协方差就是正值反之相反公式 pearson公式 范围-1 到 1 缺点 1与样本数量有关如果n过小很有可能出现接近1n过大可能小于1且显著性检测时采用t检验要求数据来自正态分布样本过小可能导致要求不满足 2从含义上看如果出现X11, 1向量其标准差为0分母为0所以无法计算pearson相关系数 应用 1求两样品的不同特征之间的相关系数从而用于降维 2根据相关度进行聚类 与余弦的联系 pearson相关系数实际上是做了标准化的cospearson是余弦相似度在维度缺失情况下的一种改进如何理解皮尔逊相关系数Pearson Correlation Coefficient
5 K-means聚类
5.1 基本思想
先给定K个划分迭代样本与簇的隶属关系每次都比之前一次好一些迭代若干次后就能得到比较好的结果
5.2 步骤
初始化选择K个初始的簇中心怎么选分配逐个计算每个样本到中心的距离将样本归属到距离最小的那个簇中心的簇中更新每个簇内部计算平均值更新簇中心迭代重复步骤2和步骤3知道满足停止条件比如集群中心不再显著变化或者达到设定的迭代次数 5.3 K-means特点
优点 简单效果不错 缺点 对异常值敏感计算距离时我们使用L2距离的平方。这样对离群点很敏感会把中心点拉偏对初始值敏感对某些分布聚类效果不好
5.4 K-means的变种 K-medoids针对K-means的缺点改进 计算新的簇中心的时候不再选择均值而是选择中位数抗噪能力得到加强为避免平方计算对离群点的敏感把平方变成绝对值限制聚类中心点必须来自数据点 求中心点的计算方法由原来的直接计算重心变成计算完重心后在重心附近找一个数据点作为新的中心点K-medoids重拟合步骤直接求平均的K-means要复杂一些 二分K-means K-means的损失函数 每个点到中心点位置的MSE分别计算四个簇的MSE会发现有两个簇的MSE很小一个簇的MSE很大选择合并簇中心点比较近MSE很小的簇切分簇中心离其他簇中心比较远MSE比较大的簇重新进行K-means聚类 K-means 现在目前的模型基本使用的是K-meansK-means改变初始中心点的位置 目标初始化簇中心点稍微远一些步骤1随机选择第一个中心点 2计算每个样本到第一个中心点的距离3将距离转化为概率4概率化选择
5.5 K-means的损失函数
K-means的理论基础是假设各簇之间符合同方差的高斯分布模型 通过最大似然估计得到K-means的迭代方法这个函数是个非凸函数根据初始值不同只能得到局部最优解
5.6 K的选择
K值的选择是执行K均值聚类时需要仔细考虑的问题选择的不合适可能导致聚类结果不准确或不具有实际意义
5.6.1 肘部法Elbow Method
Kn的时候损失函数为0
K1的时候损失函数原始数据的方差
所以K应选择一个最佳的拐点肘部法 5.6.2 轮廓系数Silhouette Coefficient
轮廓系数结合了聚类的凝聚度Cohesion和分离度Separation用于评估聚类的结果
簇内距离同一簇内其他点到某个点的距离的平局值簇间距离某个点到其他簇每个点的平均值 最终目的是为了使簇内部距离最小化簇间距离最大化。所以SC越靠近1说明b越大于a即外部距离大内部距离小说明分类效果越好
然而当我们根据不同的K计算出几个SC值差不多时并不是盲目选更大的SC如下面的例子 n_clusters 2 SC : 0.7049
n_clusters 3SC : 0.5882
n_clusters 4SC : 0.6505
n_clusters 5SC : 0.5637
n_clusters 6SC: 0.4504
每次聚类后每个样本得到一个轮廓系数当SC1时说明这个点与周围簇距离较远结果非常好当SC0时说明这个点可能处在两个簇的边界上当值为负时该点可能被误分
从上面结果来说K取2和4其实都不错但可以从下图看出K取2的话第0簇的宽度远宽于第1簇也就是说黑色数量比绿色多太多而K取4的话每个簇其差别不大。所以选K4更好 5.6.3 误差平方和SSE
误差平方和The sum of squares due to error:真实值和误差值的差的平方再求整体和 例如数据-0.2、0.4、-0.8、1.3、-0.7为真实值和误差值的差 SSE是松散度的衡量所以SSE越小越好。随着聚类迭代其值越来越小知道最后区域稳定
5.6.4 CH系数Calinski-Harabasz Index
CH系数类别内部数据的协方差越小越好类别之间的协方差越大越好这样的Calinski-Harabasz分数s会高分数s高则聚类效果好。 **换句话说类别内部数据的距离平方和越小越好类别之间的距离平方和越大越好** 其中tr为矩阵的迹Bk是类别之间的协方差矩阵Wk是类别内部数据的协方差矩阵m是训练集样本数量k是类别数量
5.6.5 小结
SSE误差平方和越小越好肘部法下降突然变缓时即认为是最佳K值SC系数取值为[-1, 1]其值越大越好CH系数分数S高则聚类效果越好CH需要达到的目的用尽量少的类别聚类尽量多的样本同时获取较好的聚类效果
6 Canopy聚类
Canopy聚类只进行一次划分聚类是基于距离阈值进行的快速聚类算法而这些阈值通常需要进行调整以得到满意的聚类结果。实际应用中适合K-means聚类结合使用一般是先用Canopy聚类将K值计算出来然后用K-means进行迭代 Canopy聚类步骤
设置超参数T1、T2 T1T2while D 非空 随机产生d属于D作为中心点计算所有点到d的距离所有距离t1的点归属于d的中心点从D中删除d及距离小于t2的点
聚类效果 7 层次聚类 层次聚类Hierarchical Clustering是聚类算法的一种通过计算不同类别的数据点间的相似度来创建一颗有层次的嵌套聚类树在聚类树中不同类别的原始数据点是树的最低层树的顶层是一个聚类的根节点创建聚类树有自上而下和自下而上分列两种方法。7.1 层次聚类的步骤
假设有6个样本点A/B/C/D/E/F层次聚类步骤如下
最开始假设每个样本点是一个簇计算每个样本间的相似度也就是距离得到一个相似矩阵寻找各个类之间的最近的两个类即若B、C的相似度最高合并簇B和C现在变为A,BC,D,E,F更新簇类间的相似矩阵若BC和D相似度最高归为一个簇类则变为A,BCD,E,F更新簇类间的相似矩阵若簇类E和F的相似度最高归为一类则变为A,BCD,EF重复第四步簇类BCD和EF相似度最高合并为一个簇则变为A,BCDEF最后合并A,BCDEF为一个簇类结束 7.2 层次聚类算法分类 自顶向下 先上图 自顶乡下的层次聚类最开始所有的对象均属于一个cluster每次按一定的准则将某个cluster划分为多个cluster如此往复直至每个数据点均属于一个cluster 自底向上 自底向上是将每个数据点看做一个簇每次计算相似度合并如此循环下去直至属于一个簇为止
7.3 层次聚类相关模型
7.3.1 Single-Linkage算法 此算法是构造一个棵二叉树用叶节点代表数据而二叉树的每一个内部节点代表一个聚类这是一个自下而上的聚类。
7.3.2 Complete-Linkage算法 与Single-Linkage算法相似Complete-Linkage的迭代思想是一样的不同的是合并类时Single-Linkage是用两个类中距离最小的两个点作为类之间的距离而Complete-Linkage恰恰相反用距离最远的两个数据点之间的距离作为两个类之间的距离
8 密度聚类
前面介绍了划分聚类和层次聚类算法下面介绍密度聚类算法DB-SCAN算法
DB-SCAN是一个基于密度的聚类。在聚类不规则形态的点如果用K-means效果不会很好。而通过DB-SCAN就可很好地把同一密度区域的点聚在一起 8.1 关键概念 核心对象Core Object也就是密度达到一定程度的点 若 xj 的∈ - 邻域至少包含 MinPts 个样本即 则 是一个核心对象 密度直达directly-density-reachable密度可达directly-reachable核心对象之间可以是密度直达或密度可达 密度相连density-connected所有密度可达的和点点就是构成密度相连 对xi和xj若存在xk使得xi与xj均由xk密度可达则称xi和xj密度相连 8.2 算法伪代码 这个过程用直白的语言描述就是
对于一个数据集先规定最少点密度 MinPts 和半径范围。先找出核心对象如果在半径范围内点密度大于 MinPts则这个点是核心对象。把所有的核心对象放到一个集合中。从这个核心对象集合中随机找一个核心对象判断其它的数据点与它是否密度直达如果是则归入聚类簇中。继续判断其它点与聚类簇中的点是否密度直达直到把所有的点都检查完毕这时候归入聚类簇中的所有点是一个密度聚类。
