基于自然最近邻的无参聚类算法研究

基于密度的聚类算法就解决了基于距离的算法只能发现凸形或球形数据簇而不能发现任意形状数据集的问题。

划分聚类算法

  • 基本思想

    假设此数据集包含 N 个数据对象,划分聚类算法的主要目的就是将其分为K个簇,这里的每一个簇就代表着一个聚类, K 应该小于 N。得到的这 K个簇一般必须满足一下条件:a.算法得到的每一个簇都必须至少含有一个数据对象;b.数据集中的每个数据对 象只能属于聚类结果中的一个类簇且必须属于其中一个类簇;对一个基于划分的聚类算法,首先给定一个参数 K 作为最后聚类结果簇的数目,然后随机的将数据集分成K个簇,再然后用不断迭代的方法来更新每个簇,使 后面得到的类簇比前一次的类簇效果更好,而这里所说的好就是:同一个类簇中的数据对象相似性越高越好,而不同类簇中的数据对象的相异性越高越好。

  • K-MEANS

  • PAM(Partitioning Around Medoid,围绕中点的划分)

  • 在对小中型数据集进行分析时,对类球形或凸型性数据的聚类效果很好。缺点是其需要聚类参数,也就是聚类数目 k,而且 K 的值是要对数据集有一定的认识才能被合理地设置;除此之外算在在一开始的聚类中心的随机选择和数据集本身包含的噪声都有可能导致最后的聚类结果不理想。而且基于划分的聚类算法对密度有差异的或者任意形状的数据集的聚类效果并不理想。

层次聚类算法

  • 基本思想

    将待处理的数据集进行一层一层的分解,将数据组织成若干组并形成一个相应的树状图然后进行聚类,一旦满足用户预先设定的条件,算法就结束。依据层次分解聚类形成过程的不同,又可以具体将层次分分为聚合层次聚类和分解层次聚类两种方案。聚合层次聚类的方法也称“自底向上”的方法,一开始每一个数对象都被当做一个原始聚类,然后对这些原始聚类逐层进行聚合,直至满足一定的终止条件为止。分解层次聚类也称“自顶向下”的方法,与前者相反,初始时将所有的对象都看成一个聚类,然后在每次循环中将其不断分解成多个更小的聚类,直至满足算法设定的终止条件或者每个类簇只包含一个数据对象。在以上两种层次聚类的方法中,一般都是算法设置最终聚类个数作为算法的终止条件,另一个终止条件是为了防止用户定义的聚类数不合理。

  • CURE 适用于任意形状分布的数据集,并且对噪声点不敏感

  • Chameleon

    不但考虑了数据对象之间的邻接关系,还考虑了数据内部的一些特性,即数据集内部数据对象之间的相似度,因此其能够自动地适应被合并簇的内部特征,具有较强的发现任意形状和大小簇的能力。算法首先将数据集构造出一个 K-最近邻图,再通过一个图划分算法将 K-最近邻图划分成大量的子图,且每个子图代表一个初始子簇, 最后再反复地合并子簇来找到真正的结果簇。

  • ROCK

  • BRICH

    它不但考虑了数据对象之间的邻接关系,还考虑了数据内部的一些特性,即数据集内部数据对象之间的相似度,因此其能够自动地适应被合并簇的内部特征,具有较强的发现任意形状和大小簇的能力。算法首先将数据集构造出一个 K-最近邻图,再通过一个图划分算法将K-最近邻图划分成大量的子图,且每个子图代表一个初始子簇,最后再反复地合并子簇来找到真正的结果簇。

基于密度的聚类算法

  • 基本思想

    如若一个范围中的数据对象的密度大于某个设定的阀值,就将此数据对象加到与其密度可达的簇中,也就是将密度大于某个阀值的相邻区域聚合成一个类,类与类之间是由密度小的区域分割的。即对进行聚类分析的数据集中的所有数据对象,在固定的半径区域内必须最少包含一定数目的数据对象,也就是密度要足够大才会被认为是一个簇。

  • DBSCAN DBSCAN算法的聚类效果和计算复杂度,与起始搜索点有紧密关系。若其实搜素点选择不好有可能导致计算复杂度很高,甚至导致聚类效果不理想。

  • DENCLUE

  • OPTIC

基于网格的聚类算法

  • 基本思想

    将数据集当做一个空间中的一大块区域,而数据集中的数据对象就是区域中的点,将对数据集中的数据对象的聚类处理转化为对抽象出来的区域中的数据点的聚类处理。

  • STING

  • CIQUE

  • WaveCluster

    主要优点是聚类处理速度很快,这是因为其聚类过程是以分割成的网格单元而不是以数据集的数据对象为基础,所以聚类速度并不会受到数据集大小而带来的太大影响,但是基于网格的聚类算法的聚类效率的提高的代价却是降低最后聚类结果的效果,有时候得不偿失

基于模型的聚类算法

  • 基本思想

    假设数据是根据潜在的概率分布生成的,所以假设数据集的每个聚类模型,然后在数据集中搜索适合相应模型的数据并将其归为一类。

  • 统计学算法

    • COBWEB
    • CLASSIT
  • 神经网络算法

聚类分析的评价标准

  1. 是否具有对大数据集的处理能力

  2. 是否具有对高维数据的处理能力

  3. 数据分布形状不规则的处理能力

    目前已提出的大多数聚类算法都适用于凸型、类圆型且类簇的尺寸差不多的数据集。但是当数据集中数据类簇的大小尺寸不同或者簇与簇之间的密度分布不一样时,比如说流形数据集等,现目前的已有的聚类算法得出的聚类效果并不是很理想。而在我们处理的实际数据集中的数据分布往往都是随机任意分布的,形状也是各式各样的,所以聚类算法在处理数据分布不规则方面必须做更多的研究。目前基于密度的聚类算法一般都具有处理不规则分布的数据的能力,比如 CURE和 DBSCAN算法,但是却不具备处理密度分布不规则的情况。本文提出的聚类算法同时具有对形状和密度不规则分布数据的处理能力。

  4. 对异常值的处理能力

  5. 对输入数据记录的顺序不敏感

  6. 减少对先决知识或参数的依赖性

  7. 聚类结果具有可解释性和可用性


聚类分析的评估检验

“聚类有效性是指对聚类算法结果进行量化评估的方法,目前主要分为外部检验方法和内部检验方法两种”。外部检验方法是指利用已知数据准确分布的情况下,对一个聚类分析的结果进行检验,得出聚类结果的评价;内部检验方法则相反,是在不知数据分布的情况,仅通过数据集内部的自身的信息对聚类结果进行评价,看聚类结果是否能反映出数据集的簇分布结构。外部检验方法可以用于评价一个聚类算法是否适合处理某一类数据集,并对次算法的聚类准确率进行评估。