成都企业模板建站,做电子商城网站注意事项,wordpress缓存类,舟山论坛网站建设#x1f4d5;参考#xff1a;西瓜书ysu老师课件博客#xff08;3#xff09;聚类算法之DBSCAN算法 - 知乎 (zhihu.com) 目录
1.聚类任务 2.聚类算法的实现
2.1 划分式聚类方法
2.1.1 k均值算法
k均值算法基本原理#xff1a;
k均值算法算法流程#xff1a;
2.2 基于…参考西瓜书ysu老师课件博客3聚类算法之DBSCAN算法 - 知乎 (zhihu.com) 目录
1.聚类任务 2.聚类算法的实现
2.1 划分式聚类方法
2.1.1 k均值算法
k均值算法基本原理
k均值算法算法流程
2.2 基于密度聚类方法
2.2.1 DBSCAN DBSCAN的基本概念 DBSCAN算法定义
2.3 基于层次聚类方法
2.3.1 AGNES
AGNES算法流程 【涉及到的英文单词】
无监督学习 unsupervised learning
聚类 clustering
簇 cluster
簇标记 cluster label
有效性指标 validity index
簇内相似度 intra-cluster similarity
簇间相似度 inter-cluster similarity
外部指标 external index
内部指标 internal index
基于原型的聚类 prototype-based clustering
基于密度的聚类 density-based clustering
噪声 noise
异常 anomaly
DBSCAN Density-Based Spatial Clustering of Applications with Noise
AGNES Agglomerative Nesting 1.聚类任务
【聚类任务的引入】 在“无监督学习” (unsupervised learning) 中训练样本的标记信息是未知的。目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律为进一步的数据分析提供基础。此类任务中研究最多、应用最广的是“聚类”。 【什么是聚类】 聚类试图将数据集中的样本划分为若干个通常是不相交的子集每个子集称为一个“簇”。 通过这样的划分每个簇可能对应一些潜在的概念类别如“浅色瓜”、“深色瓜”、“有籽瓜”、“无籽瓜”......
【注】这些概念对聚类算法而言是未知的。聚类过程仅能自动形成簇结构簇所对应的概念语义需由使用者来把握和命名。
接下来谈一下聚类算法的聚类指标——性能度量 聚类性能度量亦称为聚类“有效性指标”validity index。 与监督学习中的性能度量作用类似对聚类结果我们需要通过某种性能度量来评估其好坏另一方面若明确了最终将要使用的性能度量则可直接将其作为聚类过程的优化目标。
聚类是将样本集D划分为若干互不相交的子集即样本簇。那么什么样的聚类结果比较好呢
直观上我们希望“物以类聚”即同一簇的样本尽可能彼此相似不同簇的样本尽可能不同。 也就是聚类结果的“簇内相似度”intra-cluster similarity高且“簇间相似度”inter-cluster similarity低这样的聚类效果较好。 【聚类性能度量】 外部指标external index将聚类结果与某个“参考模型” 进行比较 内部指标internal index直接考察聚类结果而不使用任何参考模型 【外部指标】 【内部指标】 补充距离计算 2.聚类算法的实现
【原型聚类】 “原型”是指样本空间中具有代表性的点。 原型聚类此类算法假设聚类结构能通过一组原型刻画在现实聚类任务中极为常用。 2.1 划分式聚类方法 基于划分的聚类方法 给定一个数据集 D其包含有 n 个数据对象用一个划分方法来构建数据的 k 个划分每一个划分表示一个类且 k≤n。 2.1.1 k均值算法
k均值算法基本原理 随机选取k个点作为初始的聚类中心点根据每个样本到聚类中心点之间的距离把样本归类到相距它距离最近的聚类中心代表的类中再计算样本均值。 若相邻的两个聚类中心无变化结束迭代如若不然不断重复进行该过程。 k均值算法算法流程
1.选取质心 随机选择 k 个初始质心其中 k 是用户指定的参数即所期望的簇的个数。 2.分配数据点 对于样本中的数据对象根据它们与聚类中心的距离按距离最近的准则将它们划分到距离它们最近的聚类中心形成一个簇。 3.更新聚类中心 根据指派到簇的点将每个簇的质心更新为该簇所有点的平均值。 4.判断是否结束 判断聚类中心的值是否发生变化若改变则重复执行上述步骤若不变则输出结果。 2.2 基于密度聚类方法 密度聚类亦称“基于密度的聚类”density-based clustering此类算法假设聚类结构能通过样本分布的紧密程度确定。 通常情况下密度聚类算法从样本密度的角度来考察样本之间的可连接性并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
基于密度聚类方法的代表算法是DBSCAN。
2.2.1 DBSCAN DBSCAN(Density-Based Spatial Clustering of Applications with Noise具有噪声的基于密度的聚类方法)基于一组“邻域”参数 (ϵ,MinPts) 来刻画样本分布的紧密程度。 DBSCAN的基本概念 邻域就是以为圆心为半径画一个圆在圆内的样本点构成这个邻域 核心对象如果的邻域内的样本点的个数超过了MinPts这是一个数值那么这个就是一个核b 密度直达如果在的邻域内且是核心对象那么就称和密度直达。但是反过来不一定成立因为前提条件是是核心对象所以密度直达不满足对称性。 密度可达就是一系列密度直达的样本点传递使密度可达密度可达的前提是这些点密度直达密度直达的前提是这些点是核心对象所以密度可达的点都是核心对象并且具不满足对称性。 看图理解 画图理解我的建议是直接看大佬的文
3聚类算法之DBSCAN算法 - 知乎 (zhihu.com) MinPts5的意思是如果的邻域内有≥5个样本点那么就是一个核心对象。 DBSCAN算法定义 D中不属于任何簇的样本被认为是噪声 (noise)或异常(anomaly) 样本。 那么如何从数据集D 中找出满足以上性质的聚类簇呢?
DBSCAN算法先任选数据集中的一个核心对象为“种子”再由此出发确定相应的聚类簇。
1.找核心对象 根据 (ϵ,MinPts) 对 n 个对象进行搜索寻找所有的核心对象构成核心对象集合。 2.成簇 根据上述的核心对象寻找 D 中所有密度相连的样本构成簇若上述核心对象已被访问则剔除出去。 3.重复 重复上述过程直至核心对象集合为空。 其它问题 异常点问题一些异常样本点或者说少量游离于簇外的样本点这些点不在任何一个核心对象在周围在DBSCAN中我们一般将这些样本点标记为噪音点。距离度量问题即如何计算某样本和核心对象样本的距离。在DBSCAN中一般采用最近邻思想采用某一种距离度量来衡量样本距离比如欧式距离、曼哈顿距离等。数据点优先级分配问题例如某些样本可能到两个核心对象的距离都小于 ϵ 但是这两个核心对象由于不是密度直达又不属于同一个聚类簇那么如果界定这个样本的类别呢一般来说此时 DBSCAN采用先来后到先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。 这个是大佬的博客里的3聚类算法之DBSCAN算法 - 知乎 (zhihu.com)
2.3 基于层次聚类方法 层次聚类试图在不同层次对数据集进行划分从而形成树形的聚类结构。 数据集的划分可以采用“自底向上”的聚合策略也可采用“自顶向下”的分拆策略。因此可分为聚合层次聚类与划分层次聚类。 聚合层次聚类采用自底向上的策略。开始时 , 每个样本对象自己就是一个类 , 称为原子聚类 , 然后根据这些样本之间的相似性 , 将这些样本对象 ( 原子聚类 ) 进行合并。划分层次聚类采用自顶向下的策略它首先将所有对象置于同一个簇中然后逐渐细分为越来越小的簇直到每个对象自成一簇或者达到了某个终止条件。该种方法一般较少使用。 2.3.1 AGNES
AGNES是一种采用自底向上聚合策略的层次聚类算法。 它先将数据集中的每个样本看作一个初始聚类簇然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并该过程不断重复直至达到预设的聚类簇个数。 这里的关键是如何计算聚类簇之间的距离。
实际上每个簇是一个样本集合因此只需采用关于集合的某种距离即可。 AGNES算法流程
给定包含 n 个对象的数据集 D 聚类簇距离度量函数 d聚类簇数为 k。
1.计算所有样本间的距离 使用度量函数 d 计算所有样本间的距离。 2.更新聚类簇及样本间距离 将距离最近的两个聚类簇进行合并计算合并后的聚类簇间的距离。 3.重复 重复上述过程直至聚类簇数为设定的参数 k。
