1、2023-5-22高级人工智能 史忠植1知识发现（数据挖掘知识发现（数据挖掘)第五章第五章 史忠植史忠植 中国科学院计算技术研究所 聚类分析聚类分析 Clustering Analysis Clustering Analysis 2023-5-22高级人工智能 史忠植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=xjlxi,xj,rij 0,1lxi,xj,rij=rji相似系数度量相似系数度量 .1;11mkjkikijjixxMjir )(max1mkjkikjixxM 其中，其中，M M为正数，满足为正数，满足相似系数度量相似系数度量2、夹角余弦两变量Xi与Xj看作p维空间的两个向量，这两个向量间的夹角余弦可用下式进行计算 显然，cos ij 1。相似系数度量相似系数度量3相关系数相关系数经常用来度量变量间
7、的相似性。变量Xi与Xj的相关系数定义为 显然也有，rij 1。相似系数度量相似系数度量4最大最小法 )()(11mkjkikmkjkikijxxxxr5算术平均最小法算术平均最小法 )()(211mkjkikmkjkikijxxxxr相似系数度量相似系数度量6几何平均最小法 7绝对值指数法绝对值指数法 )(11mkjkikmkjkikijxxxxr 1|mkjkikxxijer相似系数度量相似系数度量8指数相似系数法 9绝对值倒数法绝对值倒数法 11)(22mksxxijkjkikemr|11jixxMjirmkjkikij相似系数度量相似系数度量10绝对值减数法 12.12.贴近度法贴近度
8、法|11mkjkikijxxcr11非参数法非参数法 13.专家打分法专家打分法 划分方法划分方法 划分聚类方法划分聚类方法(partitioning method，PAM)是给定是给定一个有一个有n个对象或元组的的数据库构建个对象或元组的的数据库构建k个划分的个划分的方法。每个划分为一个类（或簇），并且方法。每个划分为一个类（或簇），并且k n。每个类至少包含一个对象，每个对象必须属于而每个类至少包含一个对象，每个对象必须属于而且只能属于一个类且只能属于一个类(模糊划分计算除外模糊划分计算除外)。所形成。所形成的聚类将使得一个客观划分标准最优化，从而使的聚类将使得一个客观划分标准最优化，从而
9、使得一个聚类中对象是得一个聚类中对象是“相似相似”的，而不同聚类中的，而不同聚类中的对象是的对象是“不相似不相似”的的K K均值聚类分析均值聚类分析 K均值法是麦奎因（MacQueen，1967）提出的，这种算法的基本思想是将每一个样品分配给最近中心（均值）的类中，具体的算法至少包括以下三个步骤：(1)从n个数据对象随机选取k个对象作为初始簇中心。(2)计算每个簇的平均值，并用该平均值代表相应的簇。(3)计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。(4)转步骤(2)，重新计算每个(自变化)簇的平均值。这个过程不断重复直到某个准则函数不再明显变化或者聚类的对象不再变化
10、为止。K K均值聚类分析均值聚类分析 l【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表。试将以上的样品聚成两类。样品测量结果样品测量结果K K均值聚类分析均值聚类分析 第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见下表所示。中心坐标是通过原始数据计算得来的，比如（A、B）类的，等等。15(1)22X K K均值聚类分析均值聚类分析 第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的
11、平方距离：由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：K K均值聚类分析均值聚类分析 l由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如下表所示。更新后的中心坐标更新后的中心坐标K K均值聚类分析均值聚类分析 第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，结果见下表。l到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。距离选择的原则距离选择的原则 一般说
12、来，同一批数据采用不同的距离公式，会得到不同的分类结果。产生不同结果的原因，主要是由于不同的距离公式的侧重点和实际意义都有不同。因此我们在进行聚类分析时，应注意距离公式的选择。通常选择距离公式应注意遵循以下的基本原则：l（1）要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。l（2）要综合考虑对样本观测数据的预处理和将要采用的聚类分析方法。如在进行聚类分析之前已经对变量作了标准化处理，则通常就可采用欧氏距离。l（3）要考虑研究对象的特点和计算量的大小。样品间距离公式的选择是一个比较复杂且带有一定主观性的问题，我们应根据研究对象的
13、特点不同做出具体分折。实际中，聚类分析前不妨试探性地多选择几个距离公式分别进行聚类，然后对聚类分析的结果进行对比分析，以确定最合适的距离测度方法。层次聚类方法层次聚类方法（hierarchical method）l定义：对给定的数据进行层次的分解：定义：对给定的数据进行层次的分解：l分类：分类：凝聚方法（凝聚方法（agglomerative）（自底向上）（自底向上）思想：一开始将每个对象作为单独的一组，然后根据同类思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。一
14、个，或达到一个终止条件为止。分裂方法（分裂方法（divisive）（自顶向下）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。个类中，或达到一个终止条件。层次聚类方法层次聚类方法（hierarchical method）l特点：特点：l类的个数不需事先定好类的个数不需事先定好l需确定距离矩阵需确定距离矩阵l运算量要大，适用于处理小样本数据运算量要大，适用于处理小样本数据 层次聚类方法层次聚类方法l广泛采用
15、的类间距离：l最小距离法（single linkage method）l极小异常值在实际中不多出现，避免极大值的影响 最短距离法最短距离法1.最短距离法定义类与之间的距离为两类最近样品的距离，即为设类与合并成一个新类记为，则任一类与的距离为 最短距离法最短距离法l最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离 阵记为D（0），开始每个样品自成一类，显然这时Dij=dij。（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个 新类，记为Gr，即Gr=Gp，Gq。（3）按（5.12）计算新类与其它类的距离。（4）重复（2）、（3）两步，直到所有元素。
16、并成一类为 止。如果某一步距离最小的元素不止一个，则对应这些 最小元素的类可以同时合并。最短距离法最短距离法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，其与其它类的距离D（2），见
17、下表：表表最短距离法最短距离法（4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程终止。上述聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。图图 最短距离聚类法的过程最短距离聚类法的过程最大距离法最大距离法l最大距离法（complete linkage method）l可能被极大值扭曲，删除这些值之后再聚类最大距离法最大距离法最大距离法最大距离法l再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同：l一是类与类之间的距离定义不同；l另一是计算新类与其它类的
18、距离所用的公式不同。类平均距离法类平均距离法l类平均距离法（average linkage method）类间所有样本点的平均距离l该法利用了所有样本的信息，被认为是较好的系统聚类法中间距离法中间距离法3.中间距离法最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介于两者之间的距离，称为中间距离法。中间距离将类Gp与Gq类合并为类Gr，则任意的类Gk和Gr的距离公式为 (14 0)设DkqDkp，如果采用最短距离法，则Dkr=Dkp，如果采用最长距离法，则Dkr=Dkq。如图5.2所示，(5.15)式就是取它们（最长距离与最
19、短距离）的中间一点作为计算Dkr的根据。中间距离法中间距离法l特别当=14，它表示取中间点算距离，公式为 图图 中间距离法中间距离法重心法重心法l重心法（重心法（centroid hierarchical method）l类的重心之间的距离类的重心之间的距离l对异常值不敏感，结果更稳定对异常值不敏感，结果更稳定 重心法重心法重心法l l 重心法重心法重心法l 重心法重心法l【例】针对例5.1的数据，试用重心法将它们聚类。（1）样品采用欧氏距离，计算样品间的平方距离阵D2（0），见下表所示。表表重心法（2）D2（0）中最小的元素是D212D2561，于是将G1和G2合并成G7，G5和G6合并成G
20、8，并计算新类与其它类的距离得到距离阵D2（1），见表 其中，其它结果类似可以求得 重心法重心法（3）在D2（1）中最小值是D2344，那么G3与G4合并一个新类G9，其与与其它类的距离D2（2），见表：表表重心法重心法（4）在中最小值是12.5，那么与合并一个新类，其与与其它类的距离，见表：重心法重心法（5）最后将G7和G10合并成G11，这时所有的六个样品聚为一类，其过程终止。上述重心法聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。图图 重心聚类法的过程重心聚类法的过程离差平方和法离差平方和法l离差平方和法（离差平方和法（ward method）lD2=WMWKWLl即l对异常值
21、很敏感；对较大的类倾向产生较大的距离，从而不易合并，较符合实际需要。LKLKMkLKLXXXXnnnD2Cluster KCluster LCluster M类平均法类平均法类平均法类平均法6.可变类平均法由于类平均法中没有反映出Gp和Gq之间的距离Dpq的影响，因此将类平均法进一步推广，如果将Gp和Gq合并为新类Gr，类Gk与新并类Gr的距离公式为：其中是可变的且 l。l (4)通过随机采样消除异常数据，若一个簇增长太慢，就删除该簇。l (5)对局部的簇进行再聚类，落在每个新形成的聚类中的代表点，则根据用户定义的收缩因子a收缩或向簇中心移动。这些点将用于代表并描绘出聚类的边界。l (6)对簇
22、中的数据标记上相应簇标记。lCURE算法的时间复杂度为O(n)，最大问题是无法处理分类属性。ROCKROCK算法算法lGuha等人于1999年提出了一个面向分类属性数据的聚类算法ROCK Guha et al.2000。其突出贡献是采用公共近邻（链接）数的全局信息作为评价数据点间相关性的度量标准，而不是传统的基于两点间距离的局部度量函数。l算法11.5 ROCK算法lProcedure cluster(S,k)l(1)beginl(2)link:=compute_links(S)l(3)for each sS dol(4)qs:=build_local_heap(link,s)l(5)Q:=b
23、uild_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 l(12)linkx,w:=linkx,u+linkx,vl(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
24、)l(18)deallocate(qu);deallocate(qv)l(19)l(20)endl注意到算法中有两种队列，全局队列Q和普通队列qi。算法中compute_links(S)是预处理计算公共点的数量。ROCKROCK算法算法lprocedure compute_links(S)lbeginlCompute inlisti for every point I in SlSet linkI,j to be zero for all i,jlfor i:=1 to n do l N:=inlisti;lfor j:=1 to|N|-1 dol for l:=j+1 to|N|dol li
25、nk Nj,Nl:=link Nj,Nl +1llendROCKROCK算法算法l在以往的算法中，两个对象之间的距离或相似性只与这两个对象本身有关，而与其他对象无关。ROCK算法将这一局部运算扩展成一种全局运算，在计算两个对象之间的距离或相似性时，不仅考虑两个对象本身，还考虑周围邻居的影响，增强了算法的抗噪声能力。为了能够处理大规模的数据，ROCK也采用随机抽样的方法。基于密度的方法基于密度的方法（density-based method）l主要有DBSCAN，OPTICS法l思想：思想：l只要临近区域的密度超过一定的阈值，就继续聚类l特点：特点：l可以过滤噪声和孤立点outlier，发现任意
26、形状的类基于密度的方法基于密度的方法（density-based method）l以空间中的一点为中心，单位体积内点的个数称为该点的密度。基于密度的聚类（density-basedclustering）根据空间密度的差别，把具有相似密度的相邻的点作为一个聚类。密度聚类只要邻近区域的密度(对象或数据点的数目)超过某个阈值，就能够继续聚类。l也就是说，对给定类中的每个数据点，在一个给定的区域内必须至少包含某个数目的点。这样，密度聚类方法就可以用来过滤“噪声”异常点数据，发现任意形状的簇。l 在密度聚类算法中，有基于高密度连接区域的DBSCAN(Density-based Spatial Clust
27、edng ofApplication with Noise)算法、通过对象排序识别聚类结构的OPTICS(Ordering Points To Identify the Clustering Structure)算法和基于密度分布函数聚类的DENCLUE(DENsitybased CLUstEring)算法。DBSCANDBSCAN算法算法lDBSCAN通过不断生长足够高密度区域来进行聚类，它能从含有噪声的空间数据库中发现任意形状的聚类。DBSCAN方法将一个聚类定义为一组“密度相连”的点集。DBSCAN的基本思想涉及的一些概念如下：l (1)对象的一邻域：给定对象的半径内的区域。l (2)核
28、心点：一个对象的一邻域至少包含最小数目(MinPts)个对象，则称该对象为核心点。l (3)直接密度可达：给定一组对象集合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)边
29、界点：非核心点，是从某一核心点直接密度可达的。l (7)噪声：聚类结束时，不属于任何簇的点。DBSCANDBSCAN算法算法lDBSCAN算法首先需要用户给定聚类对象的半径一邻域和一邻域中最小包含的对象数MinPts，然后算法检查某个对象邻域中的对象数，如果对象数大于MinPts，该对象就是核心对象，就构建以该对象为核心的新簇。然后，反复寻找从这些核心对象出发在一邻域内的对象，这个寻找过程可能会合并一些簇，直到没有新的对象可以添加到任何簇中为止。一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。基于网格的方法基于网格的方法（grid-based
30、 method）l 网格聚类方法是将对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，只与量化空间中每一维上的单元数目有关。l 在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的STING(STatistical INformation Grid-based method)算法、用小波转换方法进行聚类的WaveCluster方法和在高维数据空问基于网格和密度的CLIQUE(Clustering InQUEst)聚类方法。l STING算法是一种基于网格的多分辨率聚类技术，
31、它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（用于回答查询）被预先计算和存储STINGSTING算法算法l (1)在层次结构中选定一层作为查询处理的开始点；(2)对前层次的每个网格单元，计算出反映该单元与给定查询的关联程度的置信度区间；(3)从上面计算的置信度区间中标识每个网格单元是否与给定查询相关；(4)如果当前层是底层，则执行步骤(6)，否则执行步骤(5)；(5)处理层次结构中的下一层，对于形成高层的相关网格单元执行步骤(2)；(6)如果查询要求被满足，则执行
32、步骤(8)；否则，执行步骤(7)；(7)检索和进一步的处理落在相关单元中的数据，返回满足查询要求的结果。执行步骤(9)；(8)寻找相关网格的区域，返回满足查询要求的相关单元的区域。执行步骤(9)；(9)算法结束。基于模型方法基于模型方法（model-based method）l基于模型的聚类方法为每一个簇假定了一个模型，寻找数据对给定模型的最佳拟合，它试图优化给定的数据和某些数学模型之间的适应性，基于模型的方法经常假设数据是根据潜在的概率分布生成的，算法主要有统计学和神经网络两种。l 1987年Fisher提出了COBWEB算法Fisher，1987。COBWEB是一种流行的简单增量概念聚类算
33、法，它的输入对象用分类属性一值对来描述，COBWEB以一个分类树的形式创建层次聚类。分类树与判定树不同。分类树中的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。概率描述包括概念的概率和形如P(Ai=Vij|Ck)的条件概率，这里Ai=Vij 是属性一值对，Ck是概念类(计数被累计并存储在每个计算概率的节点)。这就与判定树不同，判定树标记分支而非节点，而且采用逻辑描述符，而不是概率描述符。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数来沿着“最佳”匹配节点的路径在树中向下移动。COBWEBCOBWEB方法方法（mod
34、el-based method）lCOBWEB采用分类效用作为启发式评估度量来帮助进行树的构造。分类效用定义如下l 这里n是在树的某个层次上形成一个划分Cl，C2，Cn的节点、概念或类别的数目。其中：l (1)概率P(Ai=Vij|Ck)表示类内相似性。该值越大，共享该属性一值对的类成员比例就越大，更能预见该属性一值对是类成员。l (2)概率P(Ck|Ai=Vij)表示类间相异性。该值越大，在对照类中的对象共享该属性一值对就越少，更能预见该属性一值对是类成员。221ij()()()nkiijkiijkijP CP AV|CP AVn AutoClassAutoClass方法方法lAutoCla
35、ss是一种基于贝叶斯理论的数据聚类算法Cheeseman et al.1996,通过对数据进行处理,计算出每条数据属于每个类别的概率值,将数据进行聚类。AutoClass能对复杂数据进行精确的自动聚类，可以事先设定好类别数目让AutoClass自动寻找,在寻找结束后,能够得到每一条数据分别属于每一类别的几率。AutoClass的程序是由Cheeseman和Stutz在1995年开发出来的。AutoClassAutoClass方法方法lAutoClass具有以下的优点:l (1)聚类的数据不需要预先给定数据的类别,但是定义了每个数据成员。l (2)可以处理连续型或是离散型数据.在AutoClas
36、s中,每一组数据都以一个向量来表示,其中每个分量分别代表不同的属性,这些属性数据可以是连续型或是离散型。l (3)AutoClass 要求将资料存成Data File(存数据文件)与Header File(描述数据的文件)两部分,如此可以让使用者自由搭配Data File 和Header File 而节省输入数据的时间.l (4)可以处理缺值数据。当一组数据中的某些属性值有缺漏时,AutoClass仍可将此组数据进行聚类。AutoClassAutoClass方法方法lAutoClass也存在以下缺点:l (1)AutoClass概率模型的前提是各属性相互独立，而这个假设在许多领域中是不成立的。
37、l (2)AutoClass不是一个完全自动化的聚类算法,需要主观地决定数据的适当群数范围,而此问题却是聚类的一大难题。l (3)使用AutoClass处理数据时,必须不断地重复假设与测试,并结合专业知识与程序,才能得到良好的结果,因而要花费大量的时间。l (4)没有提供一个先验标准来预测一组数据是否能够聚类,因而带有一定的臆断性。没有提供一个后验方法来评估分类的结果是否可以信赖。2023-5-22高级人工智能 史忠植85蚁群聚类方法蚁群聚类方法l群体智能这个概念来自对蜜蜂和蚂蚁可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解。l任何启发于群居性昆虫群体
38、和其它动物群体的集体行为而设计的算法和分布式问题解决装置都称为群体智能。l群体智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。2023-5-22高级人工智能 史忠植86群体智能的特点群体智能的特点 l分布式：能够适应当前网络环境下的工作状态;l鲁棒性：没有中心的控制与数据，个体的故障不影响整个问题的求解;l扩充性：个体的增加，系统的通信开销增加小;l简单性：个体简单，实现也比较简单。2023-5-22高级人工智能 史忠植87蚁群算法蚁群算法蚁群寻食行为研究，相对应组合优化算法和通信网络路由控制算法；群体分工和任务分配行为研究，相对应多主体分工协作算法；
39、巢穴组织和自组织行为及群体分类行为研究，相对应数据分析和图的分割算法；建巢和自装配行为研究，相对应模拟建巢算法；群体合作搬运行为研究，相对应机器人合作搬运算法。2023-5-22高级人工智能 史忠植88蚁群算法蚁群算法所需解决的关键问题 蚁群算法 效率与理论；由于没有标准的测试集，除了寻食模型，蚁卵聚类、蚁群分工和蚁巢自装配等模型都只处于证实阶段 理论和实验；一个多主体自组织模型实验和测试平台；对于追求效率的实际问题，如何既保持群体智能系统的灵活性和鲁棒性等自组织特征又能保证系统的高效率也是一个关键问题；群体智能与分布式智能的智能主体研究相结合，将产生新的智能主体协作、建模等算法和机制，提出网
40、络和网格环境的自适应多智能主体系统。2023-5-22高级人工智能 史忠植89蚂蚁寻找最短路径原理蚂蚁寻找最短路径原理A A）蚁群到达决策点。）蚁群到达决策点。B B）一些蚂蚁选择上方路径，一些蚂）一些蚂蚁选择上方路径，一些蚂蚁选择下方路径。选择是随机的。蚁选择下方路径。选择是随机的。C C）下方短路径蚂蚁到达）下方短路径蚂蚁到达相反方向的决策点的时相反方向的决策点的时间早于选择上方长路径间早于选择上方长路径的蚂蚁。的蚂蚁。D D）短路径上外激素以较高的速度）短路径上外激素以较高的速度积累。积累。外激素多的短路径外激素多的短路径将吸收更多的蚂蚁，将吸收更多的蚂蚁，反过来，更多的蚂反过来，更多的
41、蚂蚁在短路径上会留蚁在短路径上会留下更多的外激素，下更多的外激素，加上外激素挥发效加上外激素挥发效应，最后，蚁群都应，最后，蚁群都选择了最短路径。选择了最短路径。2023-5-22高级人工智能 史忠植90蚁群算法蚁群算法otherwiseallowedjtttpkallowedkikikijijkij0)()()(ij（t）为）为t时刻边时刻边e(i,j)上外激素的强度上外激素的强度可见度可见度 ijij为为1/d1/dijij 第第k k个蚂蚁从城市个蚂蚁从城市i i到城市到城市j j 的跃迁概率为：的跃迁概率为：2023-5-22高级人工智能 史忠植91一种基于蚁群算法的TSP问题分段蚁群
42、算法蚁群算法求解算法l相遇算法，提高了蚂蚁一次周游的质量，l然后将相遇算法与采用并行策略的分段算法相结合，提出一种基于蚁群算法的TSP问题分段求解算法。l实验结果表明该算法有较好的有效性。2023-5-22高级人工智能 史忠植92TSP蚁群算法蚁群算法实例lST70（TSPLIB）677.88 677.1096lCHC144（中国144城市）30354.3lkroB150 (TSPLIB)26130 261272023-5-22高级人工智能 史忠植93蚁群聚类算法蚁群聚类算法CSICSI的研究的研究CSI聚类算法主要步骤；基本模型简化：概率转换公式；实验结果。2023-5-22高级人工智能 史
43、忠植94基于蚁群算法的聚类算法基于蚁群算法的聚类算法主要步骤：主要步骤：随机分布待聚类模式；随机分布待聚类模式；每只蚂蚁计算当前对象在局部环境的群体相似度，并通每只蚂蚁计算当前对象在局部环境的群体相似度，并通过概率转换函数得到拾起或放下对象的概率，以这个概率过概率转换函数得到拾起或放下对象的概率，以这个概率行动；行动；经过群体大量的相互作用，最终得到若干聚类中心；经过群体大量的相互作用，最终得到若干聚类中心；最后收集聚类结果。最后收集聚类结果。2023-5-22高级人工智能 史忠植95概率转换公式的简化概率转换公式的简化211)(fkkpp22fkfpdl基本模型0)(0/1)(0)(/1)(
44、1iiiiofkofofkkofPdkofkofofkofPpiiii/1)(0/1)(0)(10)(1l简化模型简化模型2023-5-22高级人工智能 史忠植96实验结果实验结果 2023-5-22高级人工智能 史忠植97电信消费数据聚类分析实验结果比较电信消费数据聚类分析实验结果比较 303129282625272324221921181210151611201314 5 2 0 6 7 17 8 3 9 4 101,0002,0003,0004,0005,000平均值 话费总计群体智能聚类结果图表7 0 2 29 5 16 1328 6 25 4 18 23 2715 20 9 26 8
45、 11 14 1 3 1710 1922 2421 1201,0002,0003,0004,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 2901,0002,0003,0004,000平均值 话费总计SO M 聚类结果图表2023-5-22高级人工智能 史忠植98基于群体智能的文档聚类算法基于群体智能的文档聚类算法CSIMCSIM的研究的研究为了处理聚类过程中出现的散点以及克服算法的一些随机因素，更是为了提高算法的效率，我们将基于群体智能的文
46、档聚类算法与经典的K均值算法相结合，对算法进行了改进。混合算法的过程是这样的：首先采用基于群体智能文档聚类算法对聚类文档进行处理，得到初始的聚类中心个数和聚类中心模板，然后运用K均值算法再次聚类。这样，既保留了群体智能算法的自组织特征，又结合了K均值算法的高效率，同时也克服了两种算法的弱点，如群体智能算法的随机性和K均值算法的聚类中心个数的参数预定及输入顺序敏感。我们将算法缩写为CSIM。2023-5-22高级人工智能 史忠植99基于群体智能的文档聚类算法基于群体智能的文档聚类算法CSIMCSIM的研究的研究数据集文档数维数类别来源D1394833Gold,Coffee,SugarReuter
47、s-21578 D2323600GNP,Livestock,SugarReuters-21578 D31000 496FootballFM365 网站2023-5-22高级人工智能 史忠植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%这个结果达到了这个结果达到了SONIA系统所用文档聚类算法的水
48、系统所用文档聚类算法的水平，而平，而SONIA的算法性能明显高于的算法性能明显高于Scatter/Gather和和 TFIDF 方法。方法。2023-5-22高级人工智能 史忠植101七、粒度计算七、粒度计算l粒度计算从广义上来说是一种看待客观世界的世界观和方法论。l粒度计算的基本思想就是使用粒而不是对象为计算单元，使用粒、粒集以及粒间关系进行计算或问题求解。2023-5-22高级人工智能 史忠植102粒度计算粒度计算l1997年年Lotfi A.Zadeh 提出了粒度的概念，他认为在人类认知中存提出了粒度的概念，他认为在人类认知中存在三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到在
49、三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到从整体到部分的分解，而组织却是从部分到整体的集成，而因果关从整体到部分的分解，而组织却是从部分到整体的集成，而因果关系涉及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、系涉及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、相似性、邻近性与功能性集聚有关的事物。相似性、邻近性与功能性集聚有关的事物。l粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究，主要用于处理不确定的、粒度的理论、方法、技术和工具的研究，主要用于处理不确定的
50、、模糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息模糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息粒度理论、粗糙集理论、商空间理论、区间计算等的超集，另一方粒度理论、粗糙集理论、商空间理论、区间计算等的超集，另一方面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中，面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中，应用了分组、分类、聚类以及层次化手段的一切理论与方法均属于应用了分组、分类、聚类以及层次化手段的一切理论与方法均属于粒度计算的范畴。信息粒度在粒度计算，词计算，感知计算理论和粒度计算的范畴。信息粒度在粒度计算，词计算，感知计算理论和精化自然语言中都有
