一些聚类算法的总结.ppt

1、聚 类 算 法,一 CLIQUE算法,(1)找到对应于每个属性的一维空间中的所有稠密区域，这 是稠密的一维单元的集合。 (2)k=2。 (3)repeat。 (4)由稠密的k-1维单元产生所有的候选稠密单元k维单元。 (5)删除小于阈值的单元。 (6)k=k+1 (7)until不存在稠密k维单元。 (8)通过取所有邻近的、高密度的单元并发现簇。 (9)使用一个小组描述簇中单元的属性值域的不等式概括每一个簇,二 改进的CLIQUE优化算法,1.NEW-CLIQUE算法 (1)自适应网格划分,(2)提高算法效率 CLIQUE算法类似于发现频繁项目集的Apriori算法。做出改进：对于算法中的候选

2、项目集的产生不是由Lk-1连接剪枝后产生的，而是扫描数据库时产生的，对于每条数据产生候选集同时，运用函数运算生产联合候选项目集的关键字，计算密度。对于L3及其以上的频繁集都使用Apriori-Otid(Lk)算法进行处理。 2.带约束条件的CON-CLIQUE算法 根据约束条件施加的对象范围，可以分为四类： (1)全局约束。 (2)聚类级约束。(如关于每个类中拥有的数据点的数量) (3)特征级约束，如数据满足某种特征则进行聚类。 (4)实例级约束，针对数据对象或数据对象之间的约束，如 部分带有类编号、特定数据项间的关系、空间数据位置的相邻关系，数据按照某种结构或位置进行排列，如图像中的像素信息

3、（x，y，o）。,算法基本思路： (1)首先扫描一遍数据集D，在k个1-维空间上聚类 (2)在k个1-维空间上聚类中选择类的数目最小的维dmin (3)在dmin施加约束条件，得到dmin上的条件稠密单元 (4)利用属性dmin上的条件稠密单元和其它在(k-1)个1-维空 间上稠密单元生成候选稠密单元 (5)后继的步骤同CLIQUE算法 3.CAG-CLIQUE算法 采用基于约束条件的聚类技术、自适应网格技术、边界调整技术对算法进行改进。 算法框架： (1)扫描一遍数据集D，在K个1-维空间上约束聚类。 (2)在k个1-维空间聚类中选择类的数目最小的维dmin。,(3)在d上施加约束条件，然后

4、利用自适应网格方法得到dmin 上的条件稠密单元。 (4)利用属性dmin上的条件稠密单元和其他在k-1个1-维空间 上稠密单元，采用自适应网格方法，生成候选稠密单元。 (5)后继的步骤同自适应网格CLIQUE算法。 左边界修正算法: bound_adjacent_left(u1,u2) begin 将u1.1到u2.r的区间划分成间隔为x/的区间 将u1,u2中的点填入相应的区间 for u=最右边的网格 to 最左边网格 step一个网格 if（u划分阈值） Left_bound=u.l if(u划分阈值),break end return left_bound end,三 基于差异度的多

5、维模糊聚类,1.定义 有效数据集V中任意元组Vj，若Vj非空，且Vj对应于结果集R中某一项Rj，则称Vj为有效元组，V中所有有效元组Vj的集合成为有效数据集 对有效数据集中某数值指标Tj中任一数值v，若v属于Sk(Sk为Tj上的某值区间)，则称v所在的元组为区间Sk的有效元组 ，所有 的集合称为区间Sk上的有效数据集。 2.区间的模糊评价集 数值指标中第i区间Si对结果集中第j聚类中心 的模糊隶属关系可以用隶属度 来表示：,若Rj不包含在 的结果集中，则 =0； 的集合称为Si的模糊评价集EVi。 3.差异度Qi,j 数值指标中第i区间Si和第j区间Sj之间的最大差异度Qi,j是指Si和Sj的区间模糊评价集EVi和EVj间的隶属度差值的最大值，即 4.区间的合并与分解规则 若某指标值中相邻两区间的差异度Qi,i+1小于最小差异度Omin，则将两区间合并。 若某指标值域中某区间中两子区间的差异度Qi,i+1大于最大差异度Omin，则将该区间分解。,5.算法过程: 对指标进行聚类分析的过程就是不断进行区间合并和分解的