聚类(Clustering)
发布网友
发布时间：2022-09-14 17:02
共1个回答
热心网友
时间：2024-03-15 23:39
· 聚类（clustering）
· 降维（dimensionality rection）
· 异常检测（outlier detection）
· 推荐系统（recommendation system）
监督学习（supervised learning） ：训练样本带有信息标记，利用已有的训练样本信息学习数据的规律预测未知的新样本标签
· 回归分析（regression）
· 分类（classification）
聚类 ：物以类聚。按照某一个特定的标准（比如距离），把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不再同一个簇内的数据对象的差异性也尽可能的大。
簇 （或类cluster）：子集合。最大化簇内的相似性；最小化簇与簇之间的相似性。
聚类可以作为一个单独过程，用于寻找数据内在分布结构，也可以作为其他学习任务前驱过程。
聚类和分类的区别：聚类是无监督学习任务，不知道真实的样本标记，只把相似度搞得样本聚合在一起；分类是监督学习任务，利用已知的样本标记训练学习器预测未知样本的类别。
聚类相似度度量： 几何距离
几种距离度量方法：
· 欧式距离（Euclidean distance）:p=2的Minkowski距离，
· Minkowoski距离：
· 曼哈顿距离 （Manhattan distance）:p=1的Minkowski距离
· 夹角余弦 ：
` 相关系数 （Pearson correlation coefficient）： ,等式右面的x其实是 （x方向的均值），y其实是 （y方向的均值）,对于这个表达式很不友好，所以在此说明一下。
聚类类别：
· 基于划分的聚类（partitioning based clustering）：k均值（K-means）, Mean shift
· 层次聚类（hierarchical clustering）：Agglomerative clustering, BIRCH
· 密度聚类（density based clustering）：DBSCAN
· 基于模型的聚类（model based clustering）：高斯混合模型（GMM）
· Affinity propagation
· Spectral clustering
聚类原理：
划分聚类（partition based clustering）：给定包含N个点的数据集，划分法将构造K个分组；每个分组代表一个聚类，这里每个分组至少包含一个数据点，每个数据点属于且只属于一个分组；对于给定的K值，算法先给出一个初始化的分组方法，然后通过反复迭代的的方法改变分组，知道准则函数收敛。
K均值算法（Kmeans）:
` 给定样本集：D={ , .... }, k均值算法针对聚类所得簇：C={ , ... }
` 最小化平方差： ,其中： 簇 的质心，上面的2代表平方，下面的2代表范数2.
具体的K均值算法过程 ：
1. 随机选择K个对子女给，每个对象出事地代表了一个簇的质心，即选择K个初始质心；2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；3. 重新计算每个簇的平均值。这个过程不断重复，直到准则函数（误差的平方和SSE作为全局的目标函数）收敛，直到质心不发生明显的变化。
初始质心优化:Kmeans++：
输入：样本集D={ , ... } 聚类簇的数量K
选取初始质心的过程：
1. 随机从m个样本点中选择一个样本作为第一个簇的质心C1；2. 计算所有的样本点到质心C1的距离： ;3. 从每个点的概率分布 中随机选取一个点作为第二个质心C2。离C1越远的点，被选择的概率越大；4. 重新计算所有样本点到质心的距离；5. 重复上述过程，直到初始的K个质心被选择完成 ；按照Kmeans的算法步骤完成聚类。
输出：C= { , ... }
K均值算法（Kmean）的优缺点 ：
优点：1. 简单直观，抑郁理解实现；2. 复杂度相对比较低，在K不是很大的情况下，Kmeans的计算时间相对很短；3. Kmean会产生紧密度比较高的簇，反映了簇内样本围绕质心的紧密程度的一种算法。
缺点：1. 很难预测到准确的簇的数目；2. 对初始值设置很敏感（Kmeans++）；3. Kmeans主要发现圆形或者球形簇，对不同形状和密度的簇效果不好；4. Kmeans对噪声和离群值非常敏感（Kmeadians对噪声和离群值不敏感）
层次聚类（hierarchical clustering） ：
· 主要在不同层次对数据集进行逐层分解，直到满足某种条件为止；
· 先计算样本之间的距离。每次将距离最近的点合并到同一个类，然后再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成一个类。
· 自底向上（bottom-up）和自顶向下（top-down）两种方法：
top-down： 一开始每个个体都是一个初始的类，然后根据类与类之间的链接（linkage）寻找同类，最后形成一个最终的簇
bottom-up：一开始所有样本都属于一个大类，然后根据类与类之间的链接排除异己，打到聚类的目的。
类与类距离的计算方法 ：
最短距离法，最长距离法，中间距离法，平均距离法
最小距离：
最大距离：
平均距离：
单链接（single-linkage）:根据最小距离算法
全连接（complete-linkage）：根据最大距离算法
均链接（average-linkage）：根据平均距离算法
凝聚层次聚类具体算法流程：
1. 给定样本集，决定聚类簇距离度量函数以及聚类簇数目k；2. 将每个样本看作一类，计算两两之间的距离；3. 将距离最小的两个类合并成一个心类；4.重新计算心类与所有类之间的距离；5. 重复（3-4），知道达到所需要的簇的数目
层次聚类的优缺点：
优点：1.可以得到任意形状的簇，没有Kmeans对形状上的*；2. 可以发现类之间的层次关系；3.不要制定簇的数目
缺点：1. 通常来说，计算复杂度高（很多merge/split）；2.噪声对层次聚类也会产生很大影响；3.不适合打样本的聚类
密度聚类（density based clustering） :
` 基于密度的 方法的特点是不依赖于距离，而是依赖于密度，从而客服k均值只能发现“球形”聚簇的缺点
· 核心思想：只要一个区域中点的密度大于某个阈值，就把它加到与之相近的聚类中去
· 密度算法从样本密度的角度来考察样本的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果
· 对噪声和离群值的处理有效
· 经典算法：DBSCAN（density based spatial clutering of applications with noise）
DBSCAN 基于近邻域（neighborhood）参数（ ）刻画样本分布的 紧密程度的一种算法。
基本概念：
· 样本集： D={ }
` 阈值：
· ：对样本点 的 包括样本集中与 距离不大于 的样本
· 核心对象（core object）：如果 的 至少包含MinPts个样本，那么 就是一个核心对象 ,
假设MinPts=3,虚线标识为
·密度直达（directly density-reachable）:如果 位于 的 中，并且 是和新对象，那么 由 密度直达
· 密度可达（density-reachable）：对 ,如果存在一串样本点p1,p2.....pn = ，pn = ,且 由
` 密度直达,则称 由 密度可达
· 密度相连：存在样本集合中一点o,如果 和 均由O密度可达，那么 和 密度相连
上图中： 是核心对象，那么从 出发， 由 密度直达； 由 密度可达； 与 密度相连。
DBSCAN算法的过程：
1. 首先根据邻域参数（ ）确定样本集合D中所有的核心对象，存在集合P中。加入集合P的条件为 有不少于MinPts的样本数。
2. 然后从核心对象集合P中任意选取一个核心对象作为初始点，找出其密度可达的样本生成聚类簇，构成第一个聚类簇C1。
3. 将C1内多有核心对象从P中去除，再从更新后的核心对象集合任意选取下一个种子样本。
4. 重复（2-3），直到核心对象被全部选择完，也就是P为空集。
聚类算法总结：
基于划分的聚类：K均值（kmeans），kmeans++
层次聚类：Agglomerative聚类
密度聚类：DBSCAN
基于模型 的聚类：高斯混合模型（GMM）,这篇博客里咩有介绍
虽然稀里糊涂，但是先跟下来再说吧：
