聚类算法 朱钦圣
聚类算法 朱钦圣
目录 1、聚类算法简介 2、K-means?算法 3、DBSCAN:算法 4、层次聚类算法
1、聚类算法简介 2、K-means算法 3、DBSCAN算法 4、层次聚类算法 目录
聚类算法简介 1 简单介绍聚类算法
聚类算法简介 1 简单介绍聚类算法
聚类算法简介 定义 定义(wiki) 聚类就是按照某个特定标准（如距离 Cluster analysis is the task of 准则)把一个数据集分割成不同的类 grouping a set of objects in such a 或簇，使得同一个簇内的数据对象 way that objects in the same 的相似性尽可能大，同时不在同一 group(called a cluster)are more 个簇中的数据对象的差异性也尽可 similar (in some sense)to each 能地大。 other than to those in other groups(clusters)
聚类算法简介 定义（wiki） Cluster analysis is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters) 定义 聚类就是按照某个特定标准(如距离 准则)把一个数据集分割成不同的类 或簇，使得同一个簇内的数据对象 的相似性尽可能大，同时不在同一 个簇中的数据对象的差异性也尽可 能地大
聚类任务 聚类目标：将数据集中的样本划分为若干个通常不 相交的子集（"簇”，cluster）. 聚类既可以作为一个单独过程（用于找寻数据内在 的分布结构)，也可作为分类等其他学习任务的前 驱过程
聚类任务 聚类目标：将数据集中的样本划分为若干个通常不 相交的子集（“簇” ，cluster）. 聚类既可以作为一个单独过程（用于找寻数据内在 的分布结构），也可作为分类等其他学习任务的前 驱过程
非监督学习：输入数据没 聚类和分类的区别 有被标记，也没有确定的 结果。样本数据类别未知 需要根据样本间的相似性 对样本集进行分类（聚类 clustering)试图使类内 聚类通常又被称为无监督学习，与监督学习不同，在聚 差距最小化，类间差距最 类中那些表示数据类别的分类或者分组信息是没有的。 大化。通俗点将就是实际 应用中，不少情况下无法 聚类，简单地说就是把相似的东西分到一组，聚类的时 预先知道样本的标签，也 候，我们并不关心某一类是什么，我们需要实现的目标 就是说没有训练样本对应 只是把相似的东西聚到一起。 的类别，因而只能从原先 没有样本标签的样本集开 一个聚类算法通常只需要知道如何计算相似度就可以开 始学习分类器设计。 始工作了，因此聚类通常并不需要使用训练数据进行学 习，这在机器学习中被称作无监督学习。 不需训练，无标签
聚类和分类的区别 聚类通常又被称为无监督学习，与监督学习不同，在聚 类中那些表示数据类别的分类或者分组信息是没有的。 聚类，简单地说就是把相似的东西分到一组，聚类的时 候，我们并不关心某一类是什么，我们需要实现的目标 只是把相似的东西聚到一起。 一个聚类算法通常只需要知道如何计算相似度就可以开 始工作了，因此聚类通常并不需要使用训练数据进行学 习，这在机器学习中被称作无监督学习。 不需训练，无标签 非监督学习：输入数据没 有被标记，也没有确定的 结果。样本数据类别未知， 需要根据样本间的相似性 对样本集进行分类（聚类， clustering）试图使类内 差距最小化，类间差距最 大化。通俗点将就是实际 应用中，不少情况下无法 预先知道样本的标签，也 就是说没有训练样本对应 的类别，因而只能从原先 没有样本标签的样本集开 始学习分类器设计
监督学习(supervised learning):从给定的训练数据 集中学习出一个函数（模型参 聚类和分类的区别 数)，当新的数据到来时，可 以根据这个函数预测结果。监 督学习的训练集要求包括输入 输出，也可以说是特征和目标 训练集中的目标是由人标注的。 监督学习就是最常见的分类 Classification(分类)，对于一个classifier,通常需要你告 (注意和聚类区分)问题，通 诉它“这个东西被分为某某类”这样一些例子，理想情况 过已有的训练样本（即已知数 下，一个classifier会从它得到的训练集中进行“学习”， 据及其对应的输出)去训练得 从而具备对未知数据进行分类的能力，这种提供训练数 到一个最优模型，再利用这个 据的过程通常叫做监督学习。 模型将所有的输入映射为相应 的输出，对输出进行简单的判 需要训练，有标签 断从而实现分类的目的。也就 具有了对未知数据分类的能力。 监督学习的目标往往是让计算 机去学习我们已经创建好的分 类系统（模型）
聚类和分类的区别 Classification (分类)，对于一个classifier，通常需要你告 诉它“这个东西被分为某某类”这样一些例子，理想情况 下，一个 classifier 会从它得到的训练集中进行“学习” ， 从而具备对未知数据进行分类的能力，这种提供训练数 据的过程通常叫做监督学习。 需要训练，有标签 监督学习 （ supervised learning）：从给定的训练数据 集中学习出一个函数（模型参 数），当新的数据到来时，可 以根据这个函数预测结果。监 督学习的训练集要求包括输入 输出，也可以说是特征和目标。 训练集中的目标是由人标注的。 监督学习就是最常见的分类 （注意和聚类区分）问题，通 过已有的训练样本（即已知数 据及其对应的输出）去训练得 到一个最优模型，再利用这个 模型将所有的输入映射为相应 的输出，对输出进行简单的判 断从而实现分类的目的。也就 具有了对未知数据分类的能力。 监督学习的目标往往是让计算 机去学习我们已经创建好的分 类系统（模型）
计算相似度：距离 非负性 闵可夫斯基距离(Minkowski distance): di.st(x,xi）≥0 7 同一性 dist(r,c）= (②- dist(x,x）=0当且仅当xi=xj p=2:欧氏距离(Euclidean distance) 对称性 p=1:曼哈顿距离(Manhattan distance), dist(zi;xi)=dist(i,i) 直递性 dist(zi,i)<dist(xi,xk)+dist(k,xi)
非负性 同一性 对称性 当且仅当 直递性 计算相似度：距离
聚类算法的分类 基于质心的聚类 密度聚类 层次聚类 基于分布的聚类 在基于密度的聚类中 基于连通性的聚类（也 在基于质心的聚类中 聚类被定义为密度高于 称为层次聚类)基于对 与统计最密切相关的聚 聚类由中心向量表示， 数据集其余部分的区域。 象的核心思想，即与附 该中心向量可能不一定 这些稀疏区域中的对象 近对象的关系比与远处 类模型基于分布模型。 是数据集的成员。当簇 通常被认为是噪声和边 的对象更相关。这些算 然后可以轻松地将群集 定义为最可能属于同一 的数量固定为k时，k 界点。 法根据距离将“对象”连 means聚类给出形式定 接起来形成“簇”。群集 分布的对象。这种方法 义作为优化问题：找到k 最流行的基于密度的聚 可以主要通过连接群集 的一个方便的特性是， 个簇中心并将对象分配 类方法是DBSCAN。与 部分所需的最大距离来 它非常类似于生成人工 许多较新的方法相比， 数据集的方式：通过从 到最近的簇中心，使得 描述。在不同的距离处， 与簇的平方距离最小化。 它具有明确定义的“密度 将形成不同的簇，其可 分布中抽样随机对象。 可达性”的群集模型。 以使用树状图来表示
层次聚类 基于连通性的聚类（也 称为层次聚类）基于对 象的核心思想，即与附 近对象的关系比与远处 的对象更相关。这些算 法根据距离将“对象”连 接起来形成“簇”。群集 可以主要通过连接群集 部分所需的最大距离来 描述。在不同的距离处， 将形成不同的簇，其可 以使用树状图来表示 基于分布的聚类 与统计最密切相关的聚 类模型基于分布模型。 然后可以轻松地将群集 定义为最可能属于同一 分布的对象。这种方法 的一个方便的特性是， 它非常类似于生成人工 数据集的方式：通过从 分布中抽样随机对象。 密度聚类 在基于密度的聚类中， 聚类被定义为密度高于 数据集其余部分的区域。 这些稀疏区域中的对象 通常被认为是噪声和边 界点。 最流行的基于密度的聚 类方法是DBSCAN。与 许多较新的方法相比， 它具有明确定义的“密度 可达性”的群集模型。 基于质心的聚类 在基于质心的聚类中， 聚类由中心向量表示， 该中心向量可能不一定 是数据集的成员。当簇 的数量固定为k时，k - means聚类给出形式定 义作为优化问题：找到k 个簇中心并将对象分配 到最近的簇中心，使得 与簇的平方距离最小化。 聚类算法的分类
K-means?算法 2 K-means?算法的原理与流程
K -means算法 2 K -means算法的原理与流程