机器学习

2024-07-06 15:59| 来源: 网络整理| 查看: 265

本节学习聚类分析，聚类属于无监督学习，其中聚类的方法有很多种常见的有K-means、层次聚类（Hierarchical clustering）、谱聚类（Spectral Clustering）等，在这里，上来不会直接介绍这些理论，需要一些基础知识铺垫，和前面一样，一上来就直接介绍聚类算法，显得太突兀，会简单介绍几种，然后重点介绍如何使用这些算法。

在知乎看到这个图，挺好的：

我们也按照这个来讲，只是讲的时候我会深入某个算法，把算法讲透：

1定义

聚类是数据挖掘中的概念，就是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。

1.2.聚类与分类的区别

Clustering (聚类)，简单地说就是把相似的东西分到一组，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。因此，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在Machine Learning中被称作unsupervised learning (无监督学习)。

Classification (分类)，对于一个classifier，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做supervised learning (监督学习)。

1.3.聚类的过程

数据准备：包括特征标准化和降维；特征选择：从最初的特征中选择最有效的特征,并将其存储于向量中；特征提取：通过对所选择的特征进行转换形成新的突出特征；聚类(或分组)：首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量，而后执行聚类或分组；聚类结果评估：是指对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。

1.4. 衡量聚类算法优劣的标准

处理大的数据集的能力；处理任意形状，包括有间隙的嵌套的数据的能力；算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序；处理数据噪声的能力；是否需要预先知道聚类个数，是否需要用户给出领域知识；算法处理有很多属性数据的能力，也就是对数据维数是否敏感。

2.聚类方法的分类

2.1.划分聚类方法

给定一个n个对象的合集，划分方法构建数据的k个分区，其中每个分区代表一个簇，并且k《 n，也就是说把数据划分为k个组，使的每个组至少包含一个对象。换就话说就是划分方法在数据集上进行一层划分，典型的，基本划分方法采取互斥的簇划分，即每个对象的必须恰好属于一组。

大部分划分方法是基于距离的，采用‘迭代的重定位技术’，例如k-均值和k-中心点算法

2.1.1 k-均值聚类

k-均值聚类的方式原理很简单，他是基于距离的，这个距离就是欧式距离，什么是欧式距离呢？其实他是我们二维和三维的距离的推广而已，例如在二维中有两点（2,3），（4,5）那么这两点的欧式距离就是：

$E = \sqrt{(2-4)^2 + (3-5)^2}$

在三维中的欧式距离为：两点（x1，y1，z1），（x2，y2，z2），则欧式距离为：

$E = \sqrt{(x1-x2)^2+(y1-y2)^2+(z1-z2)^2}$

欧式距离定义：

这是维基给的欧式距离的定义，详情请参考维基百科的欧氏距离

下面我们看看k-均值是如何工作的：

这里先给出形式化的语言描述，然后给出算法过程。k-均值是基于形心的技术，基于形心的划分技术使用簇 $C_i$ 的形心代表该簇，从概念上讲，簇的形心是他的中心点，形心可以用多种定义的方法，例如用分配给该簇的的对象（或点）的均值或中心点定义（其中均值就是k-均值为定义的，而中心就是k-中心定义的）。对象 $p\epsilon C_i$ 与该簇的代表 $C_i$ 之差用dist(p, $c_i$ )度量，其中dist(p, $c_i$ )是两个数据点的欧式距离，簇 $C_i$ 的质量可以用簇内的变差来度量，他是 $C_i$ 中所有对象和形心 $c_i$ 之间的的误差平方和（距离平方和），定义为：

$E = \sum_{i=1}^{k}\sum_{p\epsilon c_i}dist(p,c_i)^2$

其中，E是数据集中的所有对象的的误差平方和；p是空间的数据点，ci是簇 $C_i$ 的的形心，此时只要优化E，使E最可能的小，得到的簇将越紧凑。

k-均值的工作过程：

k-均值把簇的形心定义为簇内点的均值，他的处理流程如下，首先，在数据集D中随机的选择K个对象，每个对象代表代表一个簇的初始均值或者中心，对剩下的每个对象，根据与各个簇中心的的欧氏距离，将他分配到最相似的的簇，最相似其实就是距离形心最近的欧式距离了。簇中每加入一个对象就重新计算簇的均值距离，然后把中心更新为该均值。下面给出伪代码：

我们来看一下聚类的过程：

k-means的k就是最终聚集的簇数，这个要你事先自己指定。k-means在常见的机器学习算法中算是相当简单的，基本过程如下：

首先任取k个样本点作为k个簇的初始中心；对每一个样本点，计算它们与k个中心的距离，把它归入距离最小的中心所在的簇；等到所有的样本点归类完毕，重新计算k个簇的中心；重复以上过程直至样本点归入的簇不再变动。

k-means聚类分析的原理虽然简单，但缺点也比较明显：

首先聚成几类这个k值你要自己定，但在对数据一无所知的情况下你自己也不知道k应该定多少；初始质心也要自己选，而这个初始质心直接决定最终的聚类效果；每一次迭代都要重新计算各个点与质心的距离，然后排序，时间成本较高。

值得一提的是，计算距离的方式有很多种，不一定非得是笛卡尔距离；计算距离前要归一化。

2.1.2.k-中心：

k-中和k-均值很像，不同的是形心的更新选择，k-均值是按照欧式距离的均值进行更新形心的，而k-中心是按照真实的数据点进行更新的，遍历所有的数据点，找到误差平方和最小的那个中心点为数据中心点。

2.2. 层次聚类方法

层次聚类，是一种很直观的算法。顾名思义就是要一层一层地进行聚类，可以从下而上地把小的cluster合并聚集，也可以从上而下地将大的cluster进行分割。似乎一般用得比较多的是从下而上地聚集，因此这里我就只介绍这一种。

所谓从下而上地合并cluster，具体而言，就是每次找到距离最短的两个cluster，然后进行合并成一个大的cluster，直到全部合并为一个cluster。整个过程就是建立一个树结构，类似于下图。

那么，如何判断两个cluster之间的距离呢？一开始每个数据点独自作为一个类，它们的距离就是这两个点之间的距离。而对于包含不止一个数据点的 cluster，就可以选择多种方法了。最常用的，就是average-linkage，即计算两个cluster各自数据点的两两距离的平均值。类似的还有single-linkage/complete-linkage，选择两个cluster中距离最短/最长的一对数据点的距离作为类的距离。个人经验complete-linkage基本没用，single-linkage通过关注局域连接，可以得到一些形状奇特的cluster，但是因为太过极端，所以效果也不是太好。

层次聚类较大的优点，就是它一次性地得到了整个聚类的过程，只要得到了上面那样的聚类树，想要分多少个cluster都可以直接根据树结构来得到结果，改变 cluster数目不需要再次计算数据点的归属。层次聚类的缺点是计算量比较大，因为要每次都要计算多个cluster内所有数据点的两两距离。另外，由于层次聚类使用的是贪心算法，得到的显然只是局域最优，不一定就是全局最优，这可以通过加入随机效应解决，这就是另外的问题了。

下面给出，数据挖掘概念与技术的定义：

具体的详情请参看数据挖掘：概念与技术，这本书对聚类讲的很透彻。此书还介绍了层次聚类的BIRCH（利用层次结构的平衡迭代规约和聚类）、Chameleon（使用动态建模的多阶段聚类）、概率层次聚类等

2.3.基于密度的方法

划分和层次的方法旨在发现球状簇，他们很难形成任意形状的簇，因此无法根据数据的特征进行聚合，为了发现任意形状的簇，我们可以把簇看做数据空间中被稀疏区域分开的稠密区，这就是基于密度聚类的方法的主要策略，为了简单明了，我们先根据例子进行讲解概念：

首先需要解决的问题就是如何建立一个标准来去发现数据稠密区区域即什么是根据密度进行聚类？

假设有一个对象o（数据），他的密度可以使用靠近o的数据的数量度量，那么这个数量是如何怎么确定，有什么依据呢？

这里以DBSCAN（具有噪声应用的基于密度的空间聚类）为例：

DBSCAN的领域对象的确定是指一个用户指定的参数 $\varepsilon 0$ 用来指定每个对象的领域半径。对象o的 $\varepsilon$ 领域是以o为中心，以 $\varepsilon$ 为半径的空间，空间的大小用户可以设定，好空间大小确定了，那么密度上面是通过临近的数据个数进行确定，但是为多少合适了？这个用户可以根据实际情况设定，那么DBSCAN为用户提供了一个参数MinPts来指定稠密区的密度阈值。那么也就是说一个对象的 $\varepsilon$ 的领域至少包含MinPts个对象称为核心对象，核心对象是稠密区的支柱，下面还有一些名词，这里就在例子中介绍，我们根据例子在理解一下：

我们先看看图左的部分，上面我们定义了一个DBSCAN的两个参数，假如 $\varepsilon$ 是上图圆的半径，MinPts=3，这也就是只要园内的数据点数至少为c个，则以这个数据为圆心的数据即为核心对象，例如上图的m、p就是核心对象，而q就不是核心对象，因为q的领域内没达到 MinPts=3的要求，因此不是核心对象，这里的核心对象也是核心数据的意思，我们知道m，p都满足核心对象，那么核心对象的数据点称为该核心对象直接密度可达，例如m，q，而m、p是彼此的密度包含，我们称m，p为直接密度可达，而p，q称为间接密度可达，类似的r和s 是密度可达的，而o是从r密度可达的，因此o，r和s都是密度相连的，这就是密度的来源了，我们把使用密度相连的的闭包来发现联通的稠密区作为簇。

下面给出伪代码：

其他的密度聚类方法请参考数据挖掘概念与技术。

好，这节就到这里，这些是纯理论，以后遇到聚类项目在贴代码。

【本文地址】

机器学习

机器学习

今日新闻

推荐新闻