手记

盒马唠机器学习之聚类算法

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

        对于聚类算法有两难点,一是如何评价这个数据聚类也就是分蔟分得比较好,因为是无监督的学习你不知道这个数据该分成几类,而且类间成员是不是符合要们的要求。二是如何调参,因为我们都不知道如何评价这个数据聚类也就是分蔟分得比较好,自然我们就不知道如何调参使得聚类效果更好。

聚类与分类的区别

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

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


聚类算法分类

        (1)基于层次化聚类算法:又称树聚类算法,透过一种层次架构方式,反复将数据进行分裂或聚合。典型的有BIRCH算法,CURE算法。

        (2)基于划分式聚类算法:预先指定聚类数目或聚类中心,反复迭代逐步降低目标函数误差值直至收敛,得到最终结果。典型的有K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER。

        (3)基于模型的聚类算法:为每簇假定了一个模型,寻找数据对给定模型的最佳拟合,同一”类“的数据属于同一种概率分布,即假设数据是根据潜在的概率分布生成的。主要有基于统计学模型的方法和基于神经网络模型的方法,尤其以基于概率模型的方法居多。一个基于模型的算法可能通过构建反应数据点空间分布的密度函数来定位聚类。基于模型的聚类试图优化给定的数据和某些数据模型之间的适应性。典型的有SOM神经网络算法。

        (4)基于密度聚类算法:只要邻近区域的密度(对象或数据点的数目)超过某个阈值,就继续聚类。擅于解决不规则形状的聚类问题,典型的有DBSCAN算法、OPTICS算法、DENCLUE算法。

        (5)基于网格的聚类算法:基于网格的方法把对象空间量化为有限数目的单元,形成一个网格结构。所有的聚类操作都在这个网格结构(即量化空间)上进行。这种方法的主要优点是它的处理 速度很快,其处理速度独立于数据对象的数目,只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。经常与基于密度的算法结合使用。典型的有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。

        还有一些基于模糊的聚类方法,基于粒子的聚类方法等等,这里就不一一介绍了。接下来我会介绍K-Means聚类和DBSCAN聚类算法。

K-MEANS算法

        算法步骤:

            (1)要得到蔟的个数,首先我们需要指定K值,也就是随机给定K个聚类中心点。

            (2)计算每个数据点到中心点的距离,数据点距离哪个中心点最近就划分到哪一类中。常用欧几里得距         离和余弦相似度(先标准化)去做距离衡量标准。

            (3)计算每一类质心(均值,即向量各维度做平均即可)作为新的中心点。 

            (4)重复以上步骤,直到每一类质心在每次迭代后变化不大为止。也可以多次随机初始化中心点,然后         选择运行结果最好的一个。 

        下图演示了K-Means进行分类的过程:

 

        随机给定了3个聚类中心点,通过聚类中心点一步一步的迭代将数据分成了3蔟。

        K-Means聚类算法优点:简单,快速,适合常规数据集。

        K-Means聚类算法缺点:K值难确定,复杂度与样本呈线性关系,很难发现任意形状的簇。

DBSCAN算法

        介绍几个需要用到的概念:

            核心对象:若某个点的密度达到算法设定的阈值则其为核心点。(即 r 邻域内点的数量不小于 minPts)

            r-邻域的距离阈值:设定的半径r。

            直接密度可达:若某点p在点q的 r 邻域内,且q是核心点则p-q直接密度可达。

            密度可达:若有一个点的序列q0、 q1、 …qk,对任意qi-qi-1是直接密度可达的,则称从q0到qk密度可          达,这实际上是直接密度可达的“传播”。

            密度相连:若从某核心点p出发,点q和点k都是密度可达的,则称点q和点k是密度相连的。

            边界点:属于某一个类的非核心点,不能发展下线了

            噪声点:不属于任何一个类簇的点,从任何一个核心点出发都是密度不可达的。

        通过下图来解释上面的概念:


        我们设定minPts为4,半径为r。

        以A点位中心的r-领域内有4个点,所以A为核心点。所有的红色点是密度可达,其中相邻的点是直接密度可达的。B和D是边界点,因为以B,D点为中心其r-领域内的点小于4个点。N点到哪个点都不是密度可达的,所以它是噪声点也就是离群点。

        算法步骤:


            (1)首先确定半径r和minPts. 从一个没有被访问过的任意数据点开始,以这个点为中心,r为半径的圆内        包含的点的数量是否大于或等于minPts,如果大于或等于minPts则改点被标记为central point,反之则会被          标记为noise point。 

            (2)重复1的步骤,如果一个noise point存在于某个central point为半径的圆内,则这个点被标记为边         缘点,反之仍为noise point。重复步骤1,知道所有的点都被访问过。 

        参数选择:

            半径r:可以根据K距离来设定,要找突变点(就是d(k)突然变大)。

            K距离:给定数据集P={p(i); i=0,1,…n},计算点P(i)到集合D的子集S中所有点之间的距离,距离按照从小          到大的顺序排序,d(k)就被称为k-距离。

            MinPts: k-距离中k的值,一般取的小一些,多次尝试。

       DBSCAN聚类算法优点: 不需要指定簇个数,擅长找到离群点(检测任务),可以发现任意形状的簇,两个参数就够了。

        DBSCAN聚类算法缺点:高维数据有些困难(可以做降维),Sklearn中效率很慢(数据削减策略),参数难以选择(参数对结果的影响非常大)。

   

Python代码:

        https://github.com/ChunhuiMa/Machine-Learning-study/upload

原文出处

0人推荐
随时随地看视频
慕课网APP