聚类分析(ppt)

1、2021-5-6高级人工智能 史忠植1 知识发现（数据挖掘知识发现（数据挖掘) ) 第五章第五章 史忠植史忠植 中国科学院计算技术研究所 聚类分析聚类分析 clustering analysis clustering analysis 2021-5-6高级人工智能 史忠植2 内容提要内容提要 一、概述一、概述 二、相似性度量二、相似性度量 三、三、划分方法划分方法 四、四、层次聚类方法层次聚类方法 五、五、基于密度的聚类基于密度的聚类 六、六、基于网格方法基于网格方法 七、七、基于模型方法基于模型方法 八、八、蚁群聚类方法蚁群聚类方法 十、粒度计算十、粒度计算 十一、实例分析与计算机实现十一、

2、实例分析与计算机实现 概概 述述 l无监督学习不要求对数据进行事先标定，在数据的分类结构未 知时，按照事物的某些属性，把事物聚集成类，使类间的相似 性尽量小，类内相似性尽量大。利用无监督学习期望能够发现 数据集中自身隐藏的内蕴结构信息。 l无监督学习也称聚类分析。 无监督学习源于许多研究领域，受 到很多应用需求的推动。例如， l在复杂网络分析中，人们希望发现具有内在紧密联系的社团 l在图像分析中，人们希望将图像分割成具有类似性质的区域 l在文本处理中，人们希望发现具有相同主题的文本子集 l在有损编码技术中，人们希望找到信息损失最小的编码 l在顾客行为分析中，人们希望发现消费方式类似的顾客群，以

3、 便制订有针对性的客户管理方式和提高营销效率。这些情况都 可以在适当的条件下归为聚类分析。 概概 述述 l “物以类聚，人以群分”。 l一般的聚类算法是先选择若干个模式点作为聚类的中心。 每一中心代表一个类别，按照某种相似性度量方法（如最 小距离方法）将各模式归于各聚类中心所代表的类别，形 成初始分类。然后由聚类准则判断初始分类是否合理，如 果不合理就修改分类，如此反复迭代运算，直到合理为止。 与监督学习不同，无监督法是边学习边分类，通过学习找 到相同的类别，然后将该类与其它类区分开。 聚类分析聚类分析 l聚类分析聚类分析(cluster analysis)是将样品个体或指标变量按其是将样品个

4、体或指标变量按其 具有的特性进行分类的一种统计分析方法。具有的特性进行分类的一种统计分析方法。 o对样品进行聚类，称为样品对样品进行聚类，称为样品(q型型)聚类分析。其目的是将聚类分析。其目的是将 分类不明确的样品按性质相似程度分成若干组，从而发分类不明确的样品按性质相似程度分成若干组，从而发 现同类样品的共性和不同类样品间的差异。现同类样品的共性和不同类样品间的差异。 o对指标进行聚类，称为指标（对指标进行聚类，称为指标（r型）聚类分析。其目的是型）聚类分析。其目的是 将分类不明确的指标按性质相似程度分成若干组，从而将分类不明确的指标按性质相似程度分成若干组，从而 在尽量不损失信息的条件下，

5、用一组少量的指标来代替在尽量不损失信息的条件下，用一组少量的指标来代替 原来的多个指标（主成分分析？因子分析？）原来的多个指标（主成分分析？因子分析？） 典型的数据聚类基本步骤如下： l (1)对数据集进行表示和预处理，包括数据清洗、特征 选择或特征抽取； l (2)给定数据之间的相似度或相异度及其定义方法； l (3)根据相似度，对数据进行划分，即聚类； l (4)对聚类结果进行评估。 聚类分析聚类分析 相似性度量相似性度量 如何刻画样品如何刻画样品/（指标）变量间的亲疏（指标）变量间的亲疏 关系或相似程度？关系或相似程度？ 样品相似性的度量样品相似性的度量 变量相似性的度量变量相似性的度量

6、 相似系数度量相似系数度量 相似系数体现对象间的相似程度，反映样本之间相对于某 些属性的相似程度。确定相似系数有很多方法，这里列出 一些常用的方法，可以根据实际问题选择使用。 设 为被分类对象的全体，以 表示每一对象 的特征数据。 令xi, xjo, rij是xi和 xj之间的相似系数，满足以下条件： lrij=1 xi= xj lxi, xj, rij 0,1 lxi, xj, rij= rji 相似系数度量相似系数度量 . 1 ; 1 1 m k jkik ij jixx m ji r )(max 1 m k jkik ji xxm 其中，其中，m m为正数，满足为正数，满足 相似系数度量

7、相似系数度量 2、夹角余弦 两变量xi与xj看作p维空间的两个向量，这两个向量间的夹角余弦可用 下式进行计算 显然， cos ij 1。 相似系数度量相似系数度量 3相关系数 相关系数经常用来度量变量间的相似性。变量xi与xj的相 关系数定义为 显然也有， rij 1。 相似系数度量相似系数度量 4最大最小法 )( )( 1 1 m k jkik m k jkik ij xx xx r 5算术平均最小法算术平均最小法 )( )(2 1 1 m k jkik m k jkik ij xx xx r 相似系数度量相似系数度量 6几何平均最小法 7绝对值指数法绝对值指数法 )( 1 1 m k jk

8、ik m k jkik ij xx xx r 1 | m k jkik xx ij er 相似系数度量相似系数度量 8指数相似系数法 9绝对值倒数法绝对值倒数法 1 1 )( 2 2 m k s xx ij k jkik e m r | 1 1 ji xx m ji r m k jkik ij 相似系数度量相似系数度量 10绝对值减数法 12. 12. 贴近度法贴近度法 |1 1 m k jkikij xxcr 11非参数法非参数法 13. 专家打分法专家打分法 划分方法划分方法 划分聚类方法划分聚类方法(partitioning method，pam)是给定是给定 一个有一个有n个对象或元组

9、的的数据库构建个对象或元组的的数据库构建k个划分的个划分的 方法。每个划分为一个类（或簇），并且方法。每个划分为一个类（或簇），并且k n。 每个类至少包含一个对象，每个对象必须属于而每个类至少包含一个对象，每个对象必须属于而 且只能属于一个类且只能属于一个类(模糊划分计算除外模糊划分计算除外)。所形成。所形成 的聚类将使得一个客观划分标准最优化，从而使的聚类将使得一个客观划分标准最优化，从而使 得一个聚类中对象是得一个聚类中对象是“相似相似”的，而不同聚类中的，而不同聚类中 的对象是的对象是“不相似不相似”的的 k k均值聚类分析均值聚类分析 k均值法是麦奎因（macqueen，1967）提

10、出的，这种算 法的基本思想是将每一个样品分配给最近中心（均值）的 类中，具体的算法至少包括以下三个步骤： (1)从n个数据对象随机选取k个对象作为初始簇中心。 (2)计算每个簇的平均值，并用该平均值代表相应的簇。 (3)计算每个对象与这些中心对象的距离，并根据最小距离 重新对相应对象进行划分。 (4)转步骤(2)，重新计算每个(自变化)簇的平均值。这个过 程不断重复直到某个准则函数不再明显变化或者聚类的对 象不再变化为止。 k k均值聚类分析均值聚类分析 l【例】假定我们对a、b、c、d四个样品分别测量两个变 量和得到结果见表。 试将以上的样品聚成两类。 样品测量结果样品测量结果 k k均值聚

11、类分析均值聚类分析 第一步：按要求取k=2，为了实施均值法聚类，我们将这 些样品随意分成两类，比如（a、b）和（c、d），然后 计算这两个聚类的中心坐标，见下表所示。 中心坐标是通过原始数据计算得来的，比如（a、 b）类 的， 等等。 1 5( 1) 2 2 x k k均值聚类分析均值聚类分析 第二步：计算某个样品到各类中心的欧氏平方距离，然后 将该样品分配给最近的一类。对于样品有变动的类，重新 计算它们的中心坐标，为下一步聚类做准备。先计算a到 两个类的平方距离： 由于a到（a、b）的距离小于到（c、d）的距离，因此a 不用重新分配。计算b到两类的平方距离： k k均值聚类分析均值聚类分析

12、l由于b到（a、b）的距离大于到（c、d）的距离，因此b 要分配给（c、d）类，得到新的聚类是（a）和（b、c、 d）。更新中心坐标如下表所示。 更新后的中心坐标更新后的中心坐标 k k均值聚类分析均值聚类分析 第三步：再次检查每个样品，以决定是否需要重新分类。 计算各样品到各中心的距离平方，结果见下表。 l到现在为止，每个样品都已经分配给距离中心最近的类， 因此聚类过程到此结束。最终得到k=2的聚类结果是a独 自成一类，b、c、d聚成一类。 距离选择的原则距离选择的原则 一般说来，同一批数据采用不同的距离公式，会得到不同的分类结果。 产生不同结果的原因，主要是由于不同的距离公式的侧重点和实际

13、意义 都有不同。因此我们在进行聚类分析时，应注意距离公式的选择。通常 选择距离公式应注意遵循以下的基本原则： l（1）要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏 距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。 l（2）要综合考虑对样本观测数据的预处理和将要采用的聚类分析方 法。如在进行聚类分析之前已经对变量作了标准化处理，则通常就可 采用欧氏距离。 l（3）要考虑研究对象的特点和计算量的大小。样品间距离公式的选 择是一个比较复杂且带有一定主观性的问题，我们应根据研究对象的 特点不同做出具体分折。实际中，聚类分析前不妨试探性地多选择几 个距离公式分别进行聚类，然后对聚

14、类分析的结果进行对比分析，以 确定最合适的距离测度方法。 层次聚类方法层次聚类方法 （hierarchical method） l定义：对给定的数据进行层次的分解：定义：对给定的数据进行层次的分解： l分类：分类： 凝聚方法（凝聚方法（agglomerative）（自底向上）（自底向上） 思想：一开始将每个对象作为单独的一组，然后根据同类思想：一开始将每个对象作为单独的一组，然后根据同类 相近，异类相异的原则，合并对象，直到所有的组合并成相近，异类相异的原则，合并对象，直到所有的组合并成 一个，或达到一个终止条件为止。一个，或达到一个终止条件为止。 分裂方法（分裂方法（divisive）（自顶

15、向下）（自顶向下） 思想：一开始将所有的对象置于一类，在迭代的每一步中思想：一开始将所有的对象置于一类，在迭代的每一步中 ，一个类不断地分为更小的类，直到每个对象在单独的一，一个类不断地分为更小的类，直到每个对象在单独的一 个类中，或达到一个终止条件。个类中，或达到一个终止条件。 层次聚类方法层次聚类方法 （hierarchical method） l特点：特点： l类的个数不需事先定好类的个数不需事先定好 l需确定距离矩阵需确定距离矩阵 l运算量要大，适用于处理小样本数据运算量要大，适用于处理小样本数据 层次聚类方法层次聚类方法 l广泛采用的类间距离： l最小距离法（single linka

16、ge method） l极小异常值在实际中不多出现，避免极大值的影响 最短距离法最短距离法 1. 最短距离法 定义类与之间的距离为两类最近样品的距离，即为 设类与合并成一个新类记为，则任一类与的距离为 最短距离法最短距离法 l最短距离法进行聚类分析的步骤如下： （1）定义样品之间距离，计算样品的两两距离，得一距离 阵记为d（0） ，开始每个样品自成一类，显然这时dij = dij。 （2）找出距离最小元素，设为dpq，则将gp和gq合并成一个 新类，记为gr，即gr = gp，gq。 （3）按（5.12）计算新类与其它类的距离。 （4）重复（2）、（3）两步，直到所有元素。并成一类为 止。如果

17、某一步距离最小的元素不止一个，则对应这些 最小元素的类可以同时合并。 最短距离法最短距离法 l【例】设有六个样品，每个只测量一个指标，分别是1，2， 5，7，9，10，试用最短距离法将它们分类。 （1）样品采用绝对值距离，计算样品间的距离阵d（0） ， 见表 表表 最短距离法最短距离法 （2）d（0）中最小的元素是d12d561，于是将g1和g2合 并成g7，g5和g6合并成g8，并利用式计算新类与其 它类的距离d（1） ，见下表： 表表 最短距离法最短距离法 （3）在d（1）中最小值是d34d482，由于g4与g3合并， 又与g8合并，因此g3、g4、g8合并成一个新类g9，其与其 它类的距

18、离d（2） ，见下表： 表表 最短距离法最短距离法 （4）最后将g7和g9合并成g10，这时所有的六个样品聚为一类， 其过程终止。 上述聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。 这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在 后面讨论。 图图 最短距离聚类法的过程最短距离聚类法的过程 最大距离法最大距离法 l最大距离法（complete linkage method） l可能被极大值扭曲，删除这些值之后再聚类 最大距离法最大距离法 最大距离法最大距离法 l再找距离最小两类并类，直至所有的样品全归为一类为止。 可以看出最长距离法与最短距离法只有两点不同： l一是类与

19、类之间的距离定义不同； l另一是计算新类与其它类的距离所用的公式不同。 类平均距离法类平均距离法 l类平均距离法（average linkage method）类 间所有样本点的平均距离 l该法利用了所有样本的信息，被认为是较好的系统 聚类法 中间距离法中间距离法 3. 中间距离法 最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不 采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介 于两者之间的距离，称为中间距离法。 中间距离将类gp与gq类合并为类gr，则任意的类gk和gr的距离公式 为 (14 0) 设dkqdkp，如果采用最短距离法，则dkr = dkp，如果采用

20、最长距离法，则dkr = dkq。如图5.2所示，(5.15)式就是取它们（最长 距离与最短距离）的中间一点作为计算dkr的根据。 中间距离法中间距离法 l特别当 = 14，它表示取中间点算距离，公式为 图图 中间距离法中间距离法 重心法重心法 l重心法（重心法（centroid hierarchical method） l类的重心之间的距离类的重心之间的距离 l对异常值不敏感，结果更稳定对异常值不敏感，结果更稳定 重心法重心法 重心法 l l 重心法 重心法重心法 l 重心法重心法 l【例】针对例5.1的数据，试用重心法将它们聚类。 （1）样品采用欧氏距离，计算样品间的平方距离阵d2（0），

21、见下表所示。 表表 重心法 （2）d2（0）中最小的元素是d212d2561，于是将g1和g2合 并成g7，g5和g6合并成g8，并计算新类与其它类的距离得到距离阵 d2（1） ，见表 其中， 其它结果类似可以求得 重心法重心法 （3）在d2（1）中最小值是d2344，那么g3与g4合并一个新类g9，其 与与其它类的距离d2（2） ，见表： 表表 重心法重心法 （4）在中最小值是12.5，那么与合并一个新类，其与与 其它类的距离，见表： 重心法重心法 （5）最后将g7和g10合并成g11，这时所有的六个样品聚为一类，其 过程终止。 上述重心法聚类的可视化过程见下图所示，横坐标的刻度表示并类的

22、距离。 图图 重心聚类法的过程重心聚类法的过程 离差平方和法离差平方和法 l离差平方和法（离差平方和法（ward method） ld2=wmwkwl l即 l对异常值很敏感；对较大的类倾向产生较大的距离，从 而不易合并，较符合实际需要。 lklk m kl kl xxxx n nn d 2 cluster k cluster l cluster m 类平均法类平均法 类平均法类平均法 6. 可变类平均法 由于类平均法中没有反映出gp和gq之间的距离dpq的影响， 因此将类平均法进一步推广，如果将gp和gq合并为新类gr， 类gk与新并类gr的距离公式为： 其中是可变的且 l。 l (4)通过

23、随机采样消除异常数据，若一个簇增长太慢， 就删除该簇。 l (5)对局部的簇进行再聚类，落在每个新形成的聚类中 的代表点，则根据用户定义的收缩因子a收缩或向簇中心 移动。这些点将用于代表并描绘出聚类的边界。 l (6)对簇中的数据标记上相应簇标记。 lcure算法的时间复杂度为o(n)，最大问题是无法处理分 类属性。 rockrock算法算法 lguha等人于1999年提出了一个面向分类属性数据的聚类 算法rock guha et al. 2000。其突出贡献是采用公共近 邻（链接）数的全局信息作为评价数据点间相关性的度量 标准，而不是传统的基于两点间距离的局部度量函数。 l算法11.5 ro

24、ck算法 lprocedure cluster(s,k) l(1) begin l(2) link: = compute_links(s) l(3) for each ss do l(4) qs: = build_local_heap(link,s) l(5) q: = build_global_heap(s,q) rockrock算法算法 l(6) while size(q)k do l(7) u: = extract_max(q) l(8) v: = max(qu) l(9) delete(q,v) l(10) w: = merge(u,v) l(11) for each x qu qv

25、l(12) linkx,w:=linkx,u + linkx,v l(13) delete(qx,u); delete(qx,v) l(14) insert(qx,w,g(x,w);insert(qw,x,g(x,w) l(15) update(q,x,qx) l(16) rockrock算法算法 l(17) insert(q,w,qw) l(18) deallocate(qu); deallocate(qv) l(19) l(20) end l注意到算法中有两种队列，全局队列q和普通队列qi。算 法中compute_links(s)是预处理计算公共点的数量。 rockrock算法算法 lpr

26、ocedure compute_links(s) lbegin lcompute inlisti for every point i in s lset linki,j to be zero for all i,j lfor i: = 1 to n do l n: = inlisti; lfor j: = 1 to |n|-1 do l for l: = j+1 to |n| do l link nj, nl : = link nj, nl + 1 l lend rockrock算法算法 l在以往的算法中，两个对象之间的距离或相似性只与这两 个对象本身有关，而与其他对象无关。rock算法将这一

27、 局部运算扩展成一种全局运算，在计算两个对象之间的距 离或相似性时，不仅考虑两个对象本身，还考虑周围邻居 的影响，增强了算法的抗噪声能力。为了能够处理大规模 的数据，rock也采用随机抽样的方法。 基于密度的方法基于密度的方法 （density-based method） l主要有dbscan，optics法 l思想：思想： l只要临近区域的密度超过一定的阈值，就继续聚类 l特点：特点： l可以过滤噪声和孤立点outlier，发现任意形状的类 基于密度的方法基于密度的方法 （density-based method） l以空间中的一点为中心，单位体积内点的个数称为该点的密度。基于 密度的聚类（

28、density-basedclustering）根据空间密度的差别，把具 有相似密度的相邻的点作为一个聚类。密度聚类只要邻近区域的密度 (对象或数据点的数目)超过某个阈值，就能够继续聚类。 l也就是说，对给定类中的每个数据点，在一个给定的区域内必须至少 包含某个数目的点。这样，密度聚类方法就可以用来过滤“噪声”异 常点数据，发现任意形状的簇。 l 在密度聚类算法中，有基于高密度连接区域的dbscan(density- based spatial clustedng ofapplication with noise)算法、通过对象排 序识别聚类结构的optics(ordering points

29、to identify the clustering structure)算法和基于密度分布函数聚类的 denclue(densitybased clustering)算法。 dbscandbscan算法算法 ldbscan通过不断生长足够高密度区域来进行聚类，它能 从含有噪声的空间数据库中发现任意形状的聚类。 dbscan方法将一个聚类定义为一组“密度相连”的点集 。dbscan的基本思想涉及的一些概念如下： l (1)对象的一邻域：给定对象的半径内的区域。 l (2)核心点：一个对象的一邻域至少包含最小数目 (minpts)个对象，则称该对象为核心点。 l (3)直接密度可达：给定一组对象

30、集合d，如果p是在q的 一邻域内，而q是一个核心点，则称对象p从对象q出发是 直接密度可达的。 dbscandbscan算法算法 l (4)密度可达：如果存在一个对象链p1，p2，pm，其 中p1=p，且pm=q，对于pld，(1in)，pi+1是从p1关于 和minpts直接密度可达的，则对象p是从对象q关于和 minpts密度可达的。 l (5)密度相连：如果对象集合d中存在一个对象o，使得 对象p和q是从o关于和minpts密度可达的，则对象p和q 是关于和minpts密度相连的。 l (6)边界点：非核心点，是从某一核心点直接密度可达 的。 l (7)噪声：聚类结束时，不属于任何簇的点

31、。 dbscandbscan算法算法 ldbscan算法首先需要用户给定聚类对象的半径一邻域 和一邻域中最小包含的对象数minpts，然后算法检查某 个对象邻域中的对象数，如果对象数大于minpts，该 对象就是核心对象，就构建以该对象为核心的新簇。然后 ，反复寻找从这些核心对象出发在一邻域内的对象，这 个寻找过程可能会合并一些簇，直到没有新的对象可以添 加到任何簇中为止。一个基于密度的簇是基于密度可达性 的最大的密度相连对象的集合。不包含在任何簇中的对象 被认为是“噪声”。 基于网格的方法基于网格的方法 （grid-based method） l 网格聚类方法是将对象空间量化为有限数目的单元

32、，形成一个网格结 构，所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方 法的主要优点是处理速度快，其处理时间独立于数据对象的数目，只与 量化空间中每一维上的单元数目有关。 l 在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的 sting(statistical information grid-based method)算法、用小波转换 方法进行聚类的wavecluster方法和在高维数据空问基于网格和密度的 clique(clustering inquest)聚类方法。 l sting算法是一种基于网格的多分辨率聚类技术，它将空间区域划分 为矩形单元。针对不同级别的分辨

33、率，通常存在多个级别的矩形单元， 这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的 单元。关于每个网格单元属性的统计信息（用于回答查询）被预先计算 和存储 stingsting算法算法 l (1) 在层次结构中选定一层作为查询处理的开始点； (2) 对前层次的每个网格单元，计算出反映该单元与给定查询的关联 程度的置信度区间； (3) 从上面计算的置信度区间中标识每个网格单元是否与给定查询相 关； (4) 如果当前层是底层，则执行步骤(6)，否则执行步骤(5)； (5) 处理层次结构中的下一层，对于形成高层的相关网格单元执行步 骤(2)； (6) 如果查询要求被满足，则执行步骤(8

34、)；否则，执行步骤(7)； (7) 检索和进一步的处理落在相关单元中的数据，返回满足查询要求 的结果。执行步骤(9)； (8) 寻找相关网格的区域，返回满足查询要求的相关单元的区域。执 行步骤(9)； (9) 算法结束。 基于模型方法基于模型方法 （model-based method） l基于模型的聚类方法为每一个簇假定了一个模型，寻找数据对给定模 型的最佳拟合，它试图优化给定的数据和某些数学模型之间的适应性 ，基于模型的方法经常假设数据是根据潜在的概率分布生成的，算法 主要有统计学和神经网络两种。 l 1987年fisher提出了cobweb算法fisher，1987 。 cobweb是

35、一种流行的简单增量概念聚类算法，它的输入对象用分类属性一值对 来描述，cobweb以一个分类树的形式创建层次聚类。分类树与判 定树不同。分类树中的每个节点对应一个概念，包含该概念的一个概 率描述，概述被分在该节点下的对象。概率描述包括概念的概率和形 如p(ai=vij|ck)的条件概率，这里ai=vij 是属性一值对，ck是概念类(计 数被累计并存储在每个计算概率的节点)。这就与判定树不同，判定 树标记分支而非节点，而且采用逻辑描述符，而不是概率描述符。在 分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个 对象进行分类，采用了一个部分匹配函数来沿着“最佳”匹配节点的 路径在树中向下

36、移动。 cobwebcobweb方法方法 （model-based method） lcobweb采用分类效用作为启发式评估度量来帮助进行树的构造。 分类效用定义如下 l 这里n是在树的某个层次上形成一个划分cl，c2，cn的节点 、概念或类别的数目。其中： l (1)概率p(ai=vij|ck)表示类内相似性。该值越大，共享该属性一值对 的类成员比例就越大，更能预见该属性一值对是类成员。 l (2)概率p(ck|ai=vij)表示类间相异性。该值越大，在对照类中的对象 共享该属性一值对就越少，更能预见该属性一值对是类成员。 22 1ij ()()() n kiijkiij kij p cp

37、av |cp av n autoclassautoclass方法方法 lautoclass是一种基于贝叶斯理论的数据聚类算法 cheeseman et al.1996 , 通过对数据进行处理, 计算出每条数据属于每个类别的概率值, 将数据进 行聚类。 autoclass能对复杂数据进行精确的自 动聚类，可以事先设定好类别数目让autoclass自 动寻找,在寻找结束后, 能够得到每一条数据分别 属于每一类别的几率。autoclass的程序是由 cheeseman和stutz在1995年开发出来的。 autoclassautoclass方法方法 lautoclass具有以下的优点: l (1)

38、聚类的数据不需要预先给定数据的类别, 但是定义了 每个数据成员。 l (2) 可以处理连续型或是离散型数据.在autoclass中, 每 一组数据都以一个向量来表示, 其中每个分量分别代表不 同的属性, 这些属性数据可以是连续型或是离散型。 l (3) autoclass 要求将资料存成data file(存数据文件)与 header file(描述数据的文件)两部分, 如此可以让使用者 自由搭配data file 和header file 而节省输入数据的时间. l (4) 可以处理缺值数据。当一组数据中的某些属性值有 缺漏时, autoclass仍可将此组数据进行聚类。 autoclass

39、autoclass方法方法 lautoclass也存在以下缺点: l (1) autoclass概率模型的前提是各属性相互独立，而这 个假设在许多领域中是不成立的。 l (2)autoclass不是一个完全自动化的聚类算法, 需要主 观地决定数据的适当群数范围, 而此问题却是聚类的一大 难题。 l (3)使用autoclass处理数据时, 必须不断地重复假设与 测试, 并结合专业知识与程序, 才能得到良好的结果, 因而 要花费大量的时间。 l (4)没有提供一个先验标准来预测一组数据是否能够聚 类, 因而带有一定的臆断性。没有提供一个后验方法来评 估分类的结果是否可以信赖。 2021-5-6高

40、级人工智能 史忠植85 蚁群聚类方法蚁群聚类方法 l群体智能这个概念来自对蜜蜂和 蚂蚁可以进行直接通信或者间接 通信(通过改变局部环境)的主体， 这组主体能够合作进行分布问题 求解 。 l任何启发于群居性昆虫群体和其 它动物群体的集体行为而设计的 算法和分布式问题解决装置都称 为群体智能。 l群体智能在没有集中控制并且不 提供全局模型的前提下，为寻找 复杂的分布式问题的解决方案提 供了基础。 2021-5-6高级人工智能 史忠植86 群体智能的特点群体智能的特点 l分布式：能够适应当前网络环境下的工作状态 ; l鲁棒性：没有中心的控制与数据，个体的故障 不影响整个问题的求解; l扩充性：个体的

41、增加，系统的通信开销增加小 ; l简单性：个体简单，实现也比较简单。 2021-5-6高级人工智能 史忠植87 蚁群算法蚁群算法 蚁群寻食行为研究，相对应组合优化算法和通信网络 路由控制算法； 群体分工和任务分配行为研究，相对应多主体分工协 作算法； 巢穴组织和自组织行为及群体分类行为研究，相对应 数据分析和图的分割算法； 建巢和自装配行为研究，相对应模拟建巢算法； 群体合作搬运行为研究，相对应机器人合作搬运算法 。 2021-5-6高级人工智能 史忠植88 蚁群算法蚁群算法 所需解决的关键问题 蚁群算法 效率与理论； 由于没有标准的测试集，除了寻食模型，蚁卵聚类、 蚁群分工和蚁巢自装配等模型

42、都只处于证实阶段 理论和实验 ； 一个多主体自组织模型实验和测试平台 ； 对于追求效率的实际问题，如何既保持群体智能系统 的灵活性和鲁棒性等自组织特征又能保证系统的高效 率也是一个关键问题 ； 群体智能与分布式智能的智能主体研究相结合，将产 生新的智能主体协作、建模等算法和机制，提出网络 和网格环境的自适应多智能主体系统 。 2021-5-6高级人工智能 史忠植89 蚂蚁寻找最短路径原理蚂蚁寻找最短路径原理 a a）蚁群到达决策点。）蚁群到达决策点。b b）一些蚂蚁选择上方路径，一些蚂）一些蚂蚁选择上方路径，一些蚂 蚁选择下方路径。选择是随机的。蚁选择下方路径。选择是随机的。 c c）下方短路

43、径蚂蚁到达）下方短路径蚂蚁到达 相反方向的决策点的时相反方向的决策点的时 间早于选择上方长路径间早于选择上方长路径 的蚂蚁。的蚂蚁。 d d）短路径上外激素以较高的速度）短路径上外激素以较高的速度 积累。积累。 外激素多的短路径外激素多的短路径 将吸收更多的蚂蚁，将吸收更多的蚂蚁， 反过来，更多的蚂反过来，更多的蚂 蚁在短路径上会留蚁在短路径上会留 下更多的外激素，下更多的外激素， 加上外激素挥发效加上外激素挥发效 应，最后，蚁群都应，最后，蚁群都 选择了最短路径。选择了最短路径。 2021-5-6高级人工智能 史忠植90 蚁群算法蚁群算法 otherwise allowedj t t tp

44、k allowedk ikik ijij k ij 0 )( )( )( ij（t）为）为t时刻边时刻边e(i,j)上外激素的强度上外激素的强度 可见度可见度 ij ij为 为1/d1/dij ij 第第k k个蚂蚁从城市个蚂蚁从城市i i到城市到城市j j 的跃迁概率为：的跃迁概率为： 2021-5-6高级人工智能 史忠植91 一种基于蚁群算法的tsp问题分段 蚁群算法蚁群算法 求解算法 l相遇算法，提高了蚂蚁一次周游的质量， l然后将相遇算法与采用并行策略的分段算法 相结合，提出一种基于蚁群算法的tsp问题 分段求解算法。 l实验结果表明该算法有较好的有效性。 2021-5-6高级人工智能

45、 史忠植92 tsp蚁群算法蚁群算法 实例 lst70（tsplib） 677.88 677.1096 lchc144（中国144城市）30354.3 lkrob150 (tsplib) 26130 26127 2021-5-6高级人工智能 史忠植93 蚁群聚类算法蚁群聚类算法csicsi的研究的研究 csi聚类算法主要步骤； 基本模型简化：概率转换公式； 实验结果 。 2021-5-6高级人工智能 史忠植94 基于蚁群算法的聚类算法基于蚁群算法的聚类算法 主要步骤：主要步骤： 随机分布待聚类模式；随机分布待聚类模式； 每只蚂蚁计算当前对象在局部环境的群体相似度，并通每只蚂蚁计算当前对象在局部

46、环境的群体相似度，并通 过概率转换函数得到拾起或放下对象的概率，以这个概率过概率转换函数得到拾起或放下对象的概率，以这个概率 行动；行动； 经过群体大量的相互作用，最终得到若干聚类中心；经过群体大量的相互作用，最终得到若干聚类中心； 最后收集聚类结果。最后收集聚类结果。 2021-5-6高级人工智能 史忠植95 概率转换公式的简化概率转换公式的简化 2 1 1 )( fk k p p 2 2 fk f p d l基本模型 0)(0 / 1)(0)( / 1)(1 i ii i of kofofk kof pd kof kofofk of pp i ii i / 1)(0 / 1)(0)(1 0

47、)(1 l简化模型简化模型 2021-5-6高级人工智能 史忠植96 实验结果实验结果 2021-5-6高级人工智能 史忠植97 电信消费数据聚类分析实验结果比较电信消费数据聚类分析实验结果比较 303129282625272324221921181210151611201314 5 2 0 6 7 17 8 3 9 4 1 0 1,000 2,000 3,000 4,000 5,000 平均值 话费总计 群体智能聚类结果图表 7 0 2 29 5 16 1328 6 25 4 18 23 2715 20 9 26 8 11 14 1 3 1710 1922 2421 12 0 1, 000

48、2, 000 3, 000 4, 000 平均值 话费总计 km eans 30 聚类结果图表 5 15 2413 21 17 28 9 27 11 2 6 35 4 18 25 32 34 20 33 30 10 8 1 3 16 36 29 0 1, 000 2, 000 3, 000 4, 000 平均值 话费总计 so m 聚类结果图表 2021-5-6高级人工智能 史忠植98 基于群体智能的文档聚类算法基于群体智能的文档聚类算法csimcsim的研究的研究 为了处理聚类过程中出现的散点以及克服算法的一些随机 因素，更是为了提高算法的效率，我们将基于群体智能的 文档聚类算法与经典的k均

49、值算法相结合，对算法进行了 改进。 混合算法的过程是这样的：首先采用基于群体智能文档聚 类算法对聚类文档进行处理，得到初始的聚类中心个数和 聚类中心模板，然后运用k均值算法再次聚类。 这样，既保留了群体智能算法的自组织特征，又结合了k 均值算法的高效率，同时也克服了两种算法的弱点，如群 体智能算法的随机性和k均值算法的聚类中心个数的参数 预定及输入顺序敏感。我们将算法缩写为csim。 2021-5-6高级人工智能 史忠植99 基于群体智能的文档聚类算法基于群体智能的文档聚类算法csimcsim的研究的研究 数据 集 文档 数 维数类别来源 d1394833gold,coffee, sugar

50、reuters- 21578 d2323600gnp,livesto ck,sugar reuters- 21578 d31000 496footballfm365 网 站 2021-5-6高级人工智能 史忠植100 基于群体智能的文档聚类算法基于群体智能的文档聚类算法csimcsim的研究的研究 数据 集 聚类中 心个数 csim 正确率 k- means 正确 率 csi正 确率 csi 散 点 d16.51698.2%97.4%99.0%5.6% 81198.5%97.2%99.4%2.1% 91098.2%95.4%92.4%0.9% d281092.5%88.5%94.7%10% 这

51、个结果达到了这个结果达到了sonia系统所用文档聚类算法的水系统所用文档聚类算法的水 平，而平，而sonia的算法性能明显高于的算法性能明显高于scatter/gather和和 tfidf 方法。方法。 2021-5-6高级人工智能 史忠植101 七、粒度计算七、粒度计算 l粒度计算从广义上来说是一种看待客观世界的 世界观和方法论。 l粒度计算的基本思想就是使用粒而不是对象为 计算单元，使用粒、粒集以及粒间关系进行计 算或问题求解。 2021-5-6高级人工智能 史忠植102 粒度计算粒度计算 l1997年年lotfi a. zadeh 提出了粒度的概念，他认为在人类认知中存提出了粒度的概念，

52、他认为在人类认知中存 在三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到在三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到 从整体到部分的分解，而组织却是从部分到整体的集成，而因果关从整体到部分的分解，而组织却是从部分到整体的集成，而因果关 系涉及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、系涉及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、 相似性、邻近性与功能性集聚有关的事物。相似性、邻近性与功能性集聚有关的事物。 l粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关 粒度的理论、方法、技术

53、和工具的研究，主要用于处理不确定的、粒度的理论、方法、技术和工具的研究，主要用于处理不确定的、 模糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息模糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息 粒度理论、粗糙集理论、商空间理论、区间计算等的超集，另一方粒度理论、粗糙集理论、商空间理论、区间计算等的超集，另一方 面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中，面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中， 应用了分组、分类、聚类以及层次化手段的一切理论与方法均属于应用了分组、分类、聚类以及层次化手段的一切理论与方法均属于 粒度计算的范畴。信息粒度在粒度计

54、算，词计算，感知计算理论和粒度计算的范畴。信息粒度在粒度计算，词计算，感知计算理论和 精化自然语言中都有反映精化自然语言中都有反映 2021-5-6高级人工智能 史忠植103 粒度计算的必要性粒度计算的必要性 l从哲学的角度看从哲学的角度看 yager和filev指出“人类已经形成了世界就是一个粒度的观点”以及 “人们观察、度量、定义和推理的实体都是粒度” 。信息粒是一种抽象， 它如同数学中的“点”、“线”、“面”一样，在人类的思维和活动中 占有重要地位。 l从人工智能的角度看从人工智能的角度看 张钹院士指出“人类智能的公认特点，就是人们能从极不相同的粒度上 观察和分析同一问题。人们不仅能在不

55、同粒度的世界上进行问题求解， 而且能够很快地从一个粒度世界跳到另一个粒度的世界，往返自如，毫 无困难。这种处理不同世界的能力，正是人类问题求解的强有力的表 现” 。 2021-5-6高级人工智能 史忠植104 粒度计算的必要性粒度计算的必要性 l从优化论的角度来看从优化论的角度来看 粒度计算的理论与方法在观念上突破了传统优化思想的束缚，不再以数 学上的精确解为目标，即：需要的是很好地理解和刻画一个问题，而不 是沉溺于那些用处不大的细节信息上。粒度计算的方法不要求目标函数 和约束函数的连续性与凸性，甚至有时连解析表达式都不要求，而且对 计算中数据的不确定性也有很强地适应能力，计算速度也快，这些优

56、点 使粒度计算具有更广泛地应用前景，所以，粒度计算理论的研究对推动 优化领域的发展极其重要。 2021-5-6高级人工智能 史忠植105 粒度计算的必要性粒度计算的必要性 l从问题求解的角度看从问题求解的角度看 用粒度计算的观点来分析解决问题显得尤为重要，这样就不用局限于具 体对象的细节。除此之外，将复杂问题划分为一系列更容易管理和更小 的子任务，可以降低全局计算代价。 l从应用技术的角度看从应用技术的角度看 图像处理、语音与字符识别等，是计算机多媒体的核心技术。这些信息 处理质量的好坏直接依赖于分割的方法和技术，而粒度计算的研究或许 能够解决这一问题。 2021-5-6高级人工智能 史忠植106 粒度计