各种密度聚类算法

1、什么是聚类？ 聚类： - 将一个对象的集合分割成几个类，每个类内的对象之间是相似的， 但与其他类的对象是不相似的。 评判聚类好坏的标准： 1 ，能够适用于大数 据量。 2 ，能应付不同的数据类型。 3 ，能够发现不同类型的聚类。 4 ， 使对专业知识的要求降到最低。 5 ，能应付脏数据。 6 ，对于数据不同的顺 序不敏感。 7 ，能应付很多类型的数据。 8 ，模型可解释，可使用。二， 聚类所基于的数据类型。聚类算法通常基于 “数据矩阵”和“ Dissimilarity 矩阵”。怎么样计算不同对象之间的距离？，数值连续的变量(体重，身高等)：度量单位的选取对于聚类的结果的很 重要的。例如将身高的

2、单位从米变为尺，将体重的单位从公斤变为磅将对聚类 的结果产生很大的影响。为了避免出现这种情况，我们必须将数据标准化：将 数据中的单位“去掉”。A, 计算绝对背离度。 B, 计算标准量度。 下面我们考虑怎样来计算两个对象之间的差异。 1 ，欧几里得距离。 2 ，曼 哈顿距离。这两种算法有共同之处： d(i,j)=0,d(i,i)=0, d(i,j)=d(j,i),d(i,j)=vi) 的值很小的话，我们就可以考虑 Oi 是个 outlier 。2， 基于距离的方法 ：如果一个记录的距离大于 d 的邻居的个数大于一个设定值 p 的话，就可以认 为这个记录是个 outlier 。换句话说， 就是这个

3、记录没有足够的邻居数目， 这 儿的邻居是根据距离来确定的。Index-based algorithm: 给定一个数据集， 这个算法检查每一个记录 o 的 d 半径的邻居个数，定义 M 为一个 outlier 的最大 d- 邻居个数，那么一旦 一个记录 o 有 M+1 个 d- 邻居，显然这个记录不是个 outlier 。Nest-loop algorithm:与上一个方法相比，它优点在于减少输入、出个数，提高储存效率Cell-based algorithm:这种方法是将数据集分成 c 个 cells, 每一个cell 有两层，第一层有 1 个 cell 的厚度，第二层有 2*sqrt(k) 个

4、 cell 的厚度。这个算法是一个 cell 一个 cell 地来找 outlier 。对于一个 cell, 我们计算三个量：在这个 cell 内的记录个数，在第一层的记录个数，在第 二层的记录的个数，分别用 cell_count ， cell_+_1_layer-count, cell_+_2_layer-count 。那么这个方法是怎样来计算 outlier 的呢？首先计算cell_+_1_layer-count ，如果它的值大于 M, 那么这个 cell 内的所有的记 录都不是 outlier ，如果它的值小于后者等于 M, 那么接着计算 cell_+_2_layer-count ，如果

5、它的值小于后者等于 M, 那么 cell 中所有的 记录都可以认为是 outlier 。否则我们按照 d- 邻居的方法来一个一个地检 查这层中的记录。3， 基于背离度的方法：这种方法是根据一个数据集中的主要特征来判定 outlier 的，那些与这个主 要特征背离很大的记录就被认为是一个 outlier 。Sequential exception technique: 给定一个有 n 个记录的数据集 S ，首 先建立它的一个记录子集序列， S1,S2,S3,Sm ， 这儿的 Sj 包含 Sj-1在这个序列中我们可以计算子集间的不相象性，下面介绍几个关键的概念。Eeception set: 它定义

6、为 outlier 的集合。Dissimilarity functuion: 这个函数计算在一个集合中记录的不相象性，如 果各个记录之间越象，那么这个值就越小，而记录之间背离读越大，则这个 值就越大。Cardinality function:它计算在给定的一个集合中记录的个数。Smoothing factor: 这个函数计算了从原集合 S 中去除一个子集后Dissimilarity 的减少值，那个减少的值最多的子集就是 outlier 。聚类的方法小节： 这篇文章很全面的介绍了聚类：包括 聚类的定义，聚类的应用，聚类的几 种常用的算法 , ， 最后还介绍了异常的检测。聚类的算法包括 分割的聚类方法 ，层次聚类，基于密度的方法，和基于 模型的方法。最近邻居和聚集( Nearest Neighbor and Clustering )距离近：在一些重要的属性上比较相似聚集( clustering )：是把相似的记录放在一起。用途聚集让用户在较高的层次上观察数据库。常被用来做商业上的 顾 客分片 ( segmentation )。找到不能与其他记录集合在一起的记录，做例外分析。最近邻居预测，距离相近的对象通常他