华中科技大学人工智能-机器学习-聚类

1、机器学习,聚类分析,简介 基本方法 分区 层次 基于密度 基于网格的方法,聚类概念,类、簇（ Cluster ） 数据对象的集合，集合中的对象满足：彼此足够相似；集合间的对象满足：彼此不相似 聚类分析 Birds of a feather flock together 物以类聚,无师学习 无监督学习 Numerical taxonomy Typology Partition,别名,简介 概念 聚类标准 相似度 应用 基本方法,聚类标准,sheep,dog,cat,shark,lizard,sparrow,viper,goldfish,frog,seagull,red mullet,是否存在肺,

2、sheep,dog,cat,shark,lizard,sparrow,viper,goldfish,frog,seagull,red mullet,居住环境,简介 概念 聚类标准 相似度 应用 基本方法,相似度,数值型数据 欧氏距离 Manhattan距离 Minkowski距离 Binary, Nominal, Ordinal etc. Jaccard系数 sim(pi, pj) = | pipj | / | pipj | 混合型数据,简介 概念 聚类标准 相似度 应用 基本方法,应用,Business Biology Identification of groups of Image pr

3、ocessing Gain distribution of data Web for information discovery Preprocessing step,简介 概念 聚类标准 相似度 应用 基本方法,基本方法,分区方法 层次方法 基于密度的方法 基于网格的方法 基于模型的方法 (类似分类),简介 基本方法 分区 层次 基于密度 基于网格,聚类方法 分区,给定 n个对象 数字k 指定聚类个数 判别函数 解决以下问题 n 个对象分到 k 个类中 所形成的类使得判别函数最优,简介 基本方法 分区 层次 基于密度 基于网格,分区算法 - PAM,k-medoid medoid: 类的代表

4、对象，居于类的中心 PAM的目标 找到 k 个medoids 形成 k 个类 (其它对象分配到最近的medoid代表的类中) 同时满足判别函数最小,简介 基本方法 分区 层次 基于密度 基于网格,分区算法 - PAM,搜索 right medoid,O1,O2,Ok,随机选择,Oi,Oh,Ok+1,On,1 m(Oj) = Oi ; d(Oj, Oh) = d(Oj,Ox) Cjih = d(Oj,Ox) - d(Oj,Oi) + 2 m(Oj) = Oi ; d(Oj, Oh) = d(Oj,Oh) Cjih = d(Oj,Oh) - d(Oj,Ox) -,Oj,简介 基本方法 分区 层次

5、基于密度 基于网格,分区算法 CLARANCE,n=5 k=3 numberlocal maxneighbor,简介 基本方法 分区 层次 基于密度 基于网格,分区算法 CLARANCE,PAM O(k(n-k)2) 每一轮迭代 CLARANCE 对结果质量影响不大,简介 基本方法 分区 层次 基于密度 基于网格,聚类方法 层次,n objects,k objects,n-k objects,1 object,1 object,1 object,简介 基本方法 分区 层次 基于密度 基于网格,聚类方法 密度,动机,Density,简介 基本方法 分区 层次 基于密度 基于网格,基于密度的算法

6、- DBSCAN,Radius Minpts =3,Core object: O M P R,简介 基本方法 分区 层次 基于密度 基于网格,基于密度的算法 - DBSCAN,Read one unclassified object o from D； inspect o o: not core object, then lable it noisy o: core object, then exec 3 lable o a new class ID co Add all objects in NEps(o) into List and lable them co； For each obje

7、ct p in List ； Inspect p Non-core: do nothing Core: for each object q in NEps(p) q is noisy: lable it co q is unclassified: lable it co and add it into List q is classified: do nothing,简介 基本方法 分区 层次 基于密度 基于网格,基于密度的算法 - DENCLUE,简介 基本方法 分区 层次 基于密度 基于网格,基于密度的算法 - DENCLUE,影响函数 密度函数,简介 基本方法 分区 层次 基于密度 基于

8、网格,基于密度的算法 - DENCLUE,基于中心点的聚类 给定 0，X*为数据集D的密度吸引子（ f(X*) = ），则由X*所吸引的数据点所构成的集合称以X*为中心的聚类，记做子集C。 （如果f(X*) ，则称X*所吸引的数据点为离群点） 任意形状的聚类 子集C的集合，满足不同子集间存在路径P，该路径上的每个点的密度函数值不小于,简介 基本方法 分区 层次 基于密度 基于网格,聚类方法 网格,将n维空间分割成单元格 目的 : 提高效率 聚类操作针对单元格而不是对象 决定算法耗时的不再是对象的数目，而是单元格的数目,简介 基本方法 分区 层次 基于密度 基于网格,基于网格的算法 - CLIQUE,搜索多维空间以及其子空间的所有类 利用了频繁项目集的概念 提出了类的最小描述方法,简介 基本方法 分区 层次 基于密度 基于网格,Clustering - CLIQUE,d-demensional space Number of intervals unit selectivity of a unit density threshold Dense unit Cluster Region maximal region minimal description of a cluster,简介 基本方法 分区 层次 基于密度 基于网格,Clustering - CLIQUE,Ste