一，什么是聚类？聚类： - 将一个对象的集合分割成几个类，每个类内的对象之间是相似的，但与其他类的对象是不相似的。

评判聚类好坏的标准： 1 ，能够适用于大数据量。

2 ，能应付不同的数据类型。

3 ，能够发现不同类型的聚类。

4 ，使对专业知识的要求降到最低。

5 ，能应付脏数据。

6 ，对于数据不同的顺序不敏感。

7 ，能应付很多类型的数据。

8 ，模型可解释，可使用。

二，聚类所基于的数据类型。

聚类算法通常基于“数据矩阵”和“ Dissimilarity矩阵”。

怎么样计算不同对象之间的距离？1 ，数值连续的变量（体重，身高等）：度量单位的选取对于聚类的结果的很重要的。

例如将身高的单位从米变为尺，将体重的单位从公斤变为磅将对聚类的结果产生很大的影响。

为了避免出现这种情况，我们必须将数据标准化：将数据中的单位“去掉”。

A, 计算绝对背离度。

B, 计算标准量度。

下面我们考虑怎样来计算两个对象之间的差异。

1 ，欧几里得距离。

2 ，曼哈顿距离。

这两种算法有共同之处： d(i,j)>=0,d(i,i)=0,d(i,j)=d(j,i),d(i,j)=<d(i,h)+d(h,j) 。

3 ， Minkowski 距离。

这是上述两种算法的通式。

并且对于不同的变量，我们可以给它赋于不同的 weight.2 ，二元数据变量：如果还是用上面的方法来计算的话，肯定会出现错误。

这儿分两种情况，对称的与非对称的。

3 ， Nominal 变量： ( 例如红，黄，绿，蓝….)4 ， ordinal 变量（例如科长，处长，局长…. ）5 ， ratio-scaled 变量：6, 以上几种混合的变量（多数情况是这样的）：三，分割的的方法。

1，K 均值算法：给定类的个数 K ，将 n 个对象分到 K 个类中去，使得类内对象之间的相似性最大，而类之间的相似性最小。

缺点：产生类的大小相差不会很大，对于脏数据很敏感。

改进的算法： k—medoids 方法。

这儿选取一个对象叫做 mediod 来代替上面的中心的作用，这样的一个 medoid 就标识了这个类。

步骤：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 均值要大，一般只适合小数据量。

2 ， C lara 算法。

上次课提到 K-medoids 算法不适合于大数据量的计算。

这次课我们介绍 Clara 算法，这是一种基于采用的方法，它能够处理大量的数据。

Clara 算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用 K-medoids 算法得到最佳的 medoids 。

Clara 算法从实际数据中抽取多个采样，在每个采样上都用 K-medoids 算法得到相应的（O1,O2…Oi…Ok ），然后在这当中选取 E 最小的一个作为最终的结果。

Clara 算法的效率取决于采样的大小，一般不太可能得到最佳的结果。

在 Clara 算法的基础上，我们提出了 Clarans 的算法，与 Clara 算法不同的是：在 Clara 算法寻找最佳的 medoids 的过程中，采样都是不变的。

而Clarans 算法在每一次循环的过程中所采用的采样都是不一样的。

与上次课所讲的寻找最佳 medoids 的过程不同的是，必须人为地来限定循环的次数。

四，层次聚类层次聚类，就是把所有的记录层次聚类可以分为两种：凝聚的方式和分割的方式，取决于聚类层次结构的形成是自顶向下的还是自底向上的。

凝聚的方式：这是一种至底向上的方法，将每一条记录看作一个类，然后根据一些规则将他们聚合成越来越大的类，直到满足一些预先设定的条件。

大多数的层次聚类方法属于这一类。

分割的方式：这种自顶向下的方法是一个与凝聚的方式相反的过程，将整个数据库作为一个大的类，然后按照一些规则将这个类分成小的类，直到满足一些预定的条件，例如类的数目到了预定值，最近的两个类之间的最小距离大于设定值。

例 3 ：图 5 给出了对于集合 {a,b,c,d,e} 层次聚类两种方式的聚类过程。

从这个图我们可以看出，凝聚的方式是将每一个记录看作一个类，再按照一定的规则逐步将这些类合并。

举个例子，如果类 C1 和类 C2 之间的距离小于预定的最小距离，那么他们就会被合并为一个类，这儿两个类的距离是由两个类中距离最近的一对记录来确定的。

分割的方式则是先将所有的记录作为一个大的类，然后再根据一些规则将它进行分割，例如最近的两个记录之间的距离。

无论凝聚的方式还是分割方式，用户都可以根据自己的要求来设定所得类的个数。

层次聚类虽然比较简单，但是在选择凝聚或者分割点的时候经常会遇到一些困难，这个是非常关键的，因为一旦记录被凝聚或者分割以后，下一步的工作是建立在新形成的类的基础之上的。

因此，如果其中任何一步没有做好的话，就会影响最终聚类的结果。

这个方法并不是太好，因为要牵涉到很大数量的类和记录。

一个比较有前途的能够提高聚类质量的方向是将层次聚类和其它的聚类结合起来进行，下面我们会介绍一些这样的方法：1，叫做“Birth”,它首先把层次聚类的形成过程到结果看作一棵树，然后再用其他的聚类方法来进行修剪。

2 ，叫做“ Cure ”，他用一定数量的记录来代表一个类，然后将他们缩为类的中心。

3 ，叫做“ Rock ” , 它是基于类之间的联系将类合并。

4 ，叫做“ Chameleon ”，在层次聚类中寻找自动的模式。

1， Birch: 这是一种综合的层次聚类的方法，它介绍了两个概念，聚类特征和聚类特征树，它们是用来表示聚类的。

这些结构能够帮助聚类方法能运行得更快，能够处理大数据量。

下面我们来看一下上面提到的结构，一个聚类特征是由关于记录子集的三重总概变量组成。

假设在一个子类中有 N 个记录，那么这个子类的聚类特征就是CF=(N,LS,SS), 其中 LS 是 N 个点（记录）的直线相加， SS 是 N 个点的平方和相加。

一个聚类特征本质上是对于给定的子类的统计和，它记录了衡量一个子类的最关键的部分，用存储统计值代替了存储整个类的记录，提高了存储的效率。

一个聚类特征树是一个垂直平衡树，它为一个层次聚类存了各个步骤的聚类特征。

图 8.6 给出了一个例子，我们约定一个“非叶子节点”是有“孩子”的 , 这个“非叶子节点”记录了它的孩子的聚类特征。

一个聚类特征有两个变量——“分枝要素 B ”和“门限 T ”， B 限定了每个“非叶子节点”最多含有的孩子的个数， T 限定了存在叶节点的子类的最大半径，这两个参数影响了最后产生的树的大小。

那么“ Birch ”是怎样工作的呢？ 1 ，它扫描整个数据库一次，建立一个初始化的聚类特征树。

2 ，它用一个聚类算法来聚合这些叶节点。

在第一阶段，聚类特征树随着记录一个一个的加入而自动形成的：一个记录被放入那个离它最近的叶节点（类）中去。

如果放入以后这个子类的半径大于门限值 T 的话，那么这个叶节点就会被分割。

这个放入的信息也会传递到根节点中去。

聚类特征树的大小可以通过调节参数来改变，如果要存储的树需要的内存超过了主内存，那就要减小门限值重新建立一棵树，这个重建过程并不需要将整个记录扫描一次。

而是建立在老的树的叶节点的基础之上的。

因此，建立一个树记录需要被扫描一次，此外还有一些方法进一步扫描记录以提高聚类特征树的质量，当树建好以后，我们可以在第二阶段用其他的聚类算法了。

Birch 算法用可利用的资源产生最好的聚类，给定一限定的主内存，一个很重要的考虑是尽量减少从 I/O 请求所需要的时间。

Birch 算法用了多种聚类的技术，对数据库的一次扫描产生一个基本好的聚类，一次或者更多的附加扫描能够提高聚类的质量。

Birch 的效果怎么样？由于每一个节点只能有一定数量的“孩子”，实际产生的聚类特征树并不是自然生成的聚类。

而且，如果聚类生成的类不成球形的话，这种算法就运用得很好，因为它用半径或者直径来控制类的边界。

2， Cure:大多数的算法或者只能用于球状类和有相似大小的类上面，或者无法解决特例的问题。

Cure 算法则能够解决这些问题。

Cure 采用一种很新颖的层次聚类算法，这种方法是介于“基于中心”和“基于记录”的方法之间的。

一定数量的记录被选中，而不是用中心或者一个记录来代替整个类。

那些能代表这个类的几个记录 , 首先在一个类中选择几个较为分散的记录作为代表整个类的记录，然后用一个特别的 Fraction 将他们压缩到类的中心。

在每一步，那些有最大相似度的类就会被合并。

由于用了多个记录来代表类，使得这种算法能够很好地对付非球状的的类以及一些例外的情况结构。

那么，在大数据量的情况下能够在不牺牲聚类质量的情况下，对付大数据量进行得很好。

为了对付大数据量， Cure 用了随机抽取和分割的方法 :1，选取有 s 个记录的采样。

2，将这 s 个采样分割成 p 个部分，每个有 s/p 个记录。

3，将 s 个记录分成 s/pq 个类。

4，通过随机采样去除那些特例的情况。

5，将这些类进行聚类，五，基于密度的方法 :1,DBSCAN:这个方法将密度足够大的那部分记录组成类，这儿定义了几个新的名词：1，对于给定的记录，我们称在其半径 e 范围内的一个记录为这个记录的 e- 邻居。

2，如果一个记录的 e- 邻居个数超过一个最小值， MinPts 那么我们就将这个记录称做中心记录。

3，一个记录的集合 D, 我们说一个记录 p 是记录 q 的“ Directly density-reachable ”记录，如果 p 是 q 的 e- 邻居， ` 并且 q 是个中心记录。

4，对于这样的一个链p1,p2,…pn ，如果， p1=q,pn=p, 且 Pi+1 是 pi 的“ Directly density-reachable ”，那么我们就将 p 称做 q 的“ density-reachable ”。

5, 如果 p,q 都是一个记录 o 的“ density-reachable ”，那么就称 p,q “ density-connected ”。

根据上面的定义，我们怎样来发现类呢？首先扫描一下数据库，计算每一个点（记录）的 e- 邻居的个数，如果一个记录的 e- 邻居的个数大于一个门限值，那么就将这个记录叫做中心记录，这样一个新的以这个记录为中心的类就产生了。