聚类算法

数据聚类算法可以分为  结构性和分散性。

结构性算法：利用以前成功使用过的聚类器进行分类
分散型算法：一次确定所有分类。

结构性算法可以从上至下或者从下至上双向进行计算。


从下至上： 算法从每个对象作为单独分类开始，不断融合其中相近的对象。
从上之下： 算法则是把所有对象作为一个整体分类，然后逐渐分小。


分割式聚类算法：是一次性确定要产生的类别，这种算法也已应用于从下至上聚类算法。

基于密度的聚类算法：是为了挖掘有任意形状特性的类别而发明的。此算法把一个类别视为数据集中大于某阈值的一个区域。
                             DBSCAN和OPTICS是两个典型的算法。

许多聚类算法在执行之前，需要指定从输入数据集中产生的分类个数。除非事先准备好一个合适的值，否则必须决定一个大概值，关于这个问题已经有一些现成的技术。

聚类分析步骤：
一：距离测量
        结构性聚类中，关键性的一步就是要选择测量的距离。
   一个简单的测量就是使用曼哈顿距离，它相当于每个变量的绝对差值之和
       常见的距离测量方法：
            欧式距离（2-norm距离）
            曼哈顿距离（Manhattan distance, 1-norm距离）
            infinity norm
            马氏距离
            余弦相似性
            汉明距离

二：机构性聚类

      在已经得到距离值之后，元素间可以被联系起来。通过分离和融合可以构建一个结构。传统上，表示的方法是树形数据结构， 然后对该结构进行修剪。
      树的根节点表示一个包含所有项目的类别，树叶表示与个别的项目相关的类别。

      层次聚类算法：自底向上聚集型的，即从叶子节点开始，最终汇聚到根节点；或者
                           自顶向下分裂型的，即从根节点开始，递归的向下分裂。

     任意非负值的函数都可以用于衡量一对观测值之间的相似度。决定一个类别是否分裂或者合并的是一个连动的标准，它是两两观测值之间距离的函数。

     在一个指定高度上切割此树，可以得到一个相应精度的分类。

三：分散性聚类  
     K-均值法及衍生算法：

     K-均值法聚类
     K-均值算法表示以空间中k个点为中心进行聚类，对最靠近他们的对象归类。
     例如：数据集合为三维，聚类以两点：X =(x1, x2, x3),Y =(y1, y2, y3)。中心点Z变为Z =(z1, z2, z3)，其中z1 = (x1 + y1)/2，z2 = (x2 + y2)/2，z3 = (x3 + y3)/2。
     算法归纳:
              选择聚类的个数k.
              任意产生k个聚类，然后确定聚类中心，或者直接生成k个中心。
               对每个点确定其聚类中心点。
               再计算其聚类新中心。
               重复以上步骤直到满足收敛要求。(通常就是确定的中心点不再改变).
       该算法的最大优势在于简洁和快速。劣势在于对于一些结果并不能够满足需要，因为结果往往需要随机点的选择非常巧合。

四：聚类算法分类
    划分法：
               划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，
                     K
             （1） 每一个分组至少包含一个数据纪录；
             （2） 每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；
               对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次
               好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。
              使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；
 
    层次法：
              层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。
             具体又可分为“自底向上”和“自顶向下”两种方案。
              例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个
              组，直到所有的记录组成一个分组或者某个条件满足为止。
              代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；

    密度算法:
               基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是
               基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
               这个方法的指导思想就是，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。
               代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

    网格算法:
              基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的
              单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分
              为多少个单元有关。
              代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

   模型算法:
             基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据
             集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所
             决定的。
             通常有两种尝试方向：统计的方案和神经网络的方案。

    K-MEANS:
              k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不
              同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
              k-means 算法的工作过程说明如下：
                            首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度
                          （距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；
                           然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛止。
                           一般都采用均方差作为标准测度函数. k个聚类具有以下特点：
                                                                                各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

     K-MEDOIDS：
               K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。
               改进的算法：
                  k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。
                 K-medoids和K-means不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前cluster中所有数据点的平均值
                  K- medoids算法中，我们将从当前cluster 中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点。
                步骤：
                     1，任意选取K个对象作为medoids（O1,O2,…Oi…Ok）。
                           以下是循环的：
                     2，将余下的对象分到各个类中去（根据与medoid最相近的原则）；
                     3，对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个medoids就改变了，下面就再转到2。
                     4，这样循环直到K个medoids固定下来。
                    这种算法对于脏数据和异常数据不敏感，但计算量显然要比K均值要大，一般只适合小数据量。

       Clara：
                  上面提到K-medoids算法不适合于大数据量的计算。Clara算法，这是一种基于采样的方法，它能够处理大量的数据。
                   Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。
                   Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1, O2 … Oi … Ok），然后在这当中选取
                   E最小的一个作为最终的结果。

        Clarans：
                  Clara算法的效率取决于采样的大小，一般不太可能得到最佳的结果。
                  在Clara算法的基础上，又提出了Clarans的算法，与Clara算法不同的是：在Clara算法寻找最佳的medoids的过程中，采样都是不变
                  的。而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。
                  与上面所讲的寻找最佳medoids的过程不同的是，必须人为地来限定循环的次数。

五：应用
        聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。
       作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力
        放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。