Unsupervised Learning

Presentation on theme: "Unsupervised Learning"— Presentation transcript:

1 Unsupervised Learning
高级人工智能 第十一章 无监督学习 Unsupervised Learning 史忠植 中国科学院计算技术研究所 2019/1/2 高级人工智能 史忠植

2 内容提要 一、概述 二、相似性度量 三、划分方法 四、层次聚类方法 五、基于密度的聚类 六、基于网格方法 七、基于模型方法 八、蚁群聚类方法
十、粒度计算 2019/1/2 高级人工智能 史忠植

3 概 述 无监督学习不要求对数据进行事先标定，在数据的分类结构未知时，按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内相似性尽量大。利用无监督学习期望能够发现数据集中自身隐藏的内蕴结构信息。 无监督学习也称聚类分析。 无监督学习源于许多研究领域，受到很多应用需求的推动。

4 概 述 “物以类聚，人以群分”。 一般的聚类算法是先选择若干个模式点作为聚类的中心。每一中心代表一个类别，按照某种相似性度量方法（如最小距离方法）将各模式归于各聚类中心所代表的类别，形成初始分类。然后由聚类准则判断初始分类是否合理，如果不合理就修改分类，如此反复迭代运算，直到合理为止。与监督学习不同，无监督法是边学习边分类，通过学习找到相同的类别，然后将该类与其它类区分开。

5 聚类分析 聚类分析(cluster analysis)是将样品个体或指标变量按其具有的特性进行分类的一种统计分析方法。
对样品进行聚类，称为样品(Q型)聚类分析。其目的是将分类不明确的样品按性质相似程度分成若干组，从而发现同类样品的共性和不同类样品间的差异。 对指标进行聚类，称为指标（R型）聚类分析。其目的是将分类不明确的指标按性质相似程度分成若干组，从而在尽量不损失信息的条件下，用一组少量的指标来代替原来的多个指标（主成分分析？因子分析？）

6 聚类分析 典型的数据聚类基本步骤如下： (1)对数据集进行表示和预处理，包括数据清洗、特征选择或特征抽取；
(2)给定数据之间的相似度或相异度及其定义方法； (3)根据相似度，对数据进行划分，即聚类； (4)对聚类结果进行评估。

7 相似性度量 如何刻画样品/（指标）变量间的亲疏关系或相似程度？ 样品相似性的度量 变量相似性的度量

8 相似系数度量 相似系数体现对象间的相似程度，反映样本之间相对于某些属性的相似程度。确定相似系数有很多方法，这里列出一些常用的方法，可以根据实际问题选择使用。 设 为被分类对象的全体，以 表示每一对象 的特征数据。令xi, xjO, rij是xi和 xj之间的相似系数，满足以下条件： rij=1  xi= xj xi, xj, rij [0,1] xi, xj, rij= rji

9 相似系数度量 其中，M为正数，满足

10 相似系数度量 两变量Xi与Xj看作p维空间的两个向量，这两个向量间的夹角余弦可用下式进行计算 2、夹角余弦
显然，∣cos  ij∣  1。

11 相似系数度量 3．相关系数 相关系数经常用来度量变量间的相似性。变量Xi与Xj的相关系数定义为 显然也有，∣rij∣  1。

12 相似系数度量 4．最大最小法 5．算术平均最小法

13 相似系数度量 6．几何平均最小法 7．绝对值指数法

14 相似系数度量 8．指数相似系数法 9．绝对值倒数法

15 相似系数度量 10．绝对值减数法 12. 贴近度法 11．非参数法 13. 专家打分法

16 划分方法 划分聚类方法(partitioning method，PAM)是给定一个有n个对象或元组的的数据库构建k个划分的方法。每个划分为一个类（或簇），并且kn。每个类至少包含一个对象，每个对象必须属于而且只能属于一个类(模糊划分计算除外)。所形成的聚类将使得一个客观划分标准最优化，从而使得一个聚类中对象是“相似”的，而不同聚类中的对象是“不相似”的

17 K均值聚类分析 K均值法是麦奎因（MacQueen，1967）提出的，这种算法的基本思想是将每一个样品分配给最近中心（均值）的类中，具体的算法至少包括以下三个步骤： (1)从n个数据对象随机选取k个对象作为初始簇中心。 (2)计算每个簇的平均值，并用该平均值代表相应的簇。 (3)计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。 (4)转步骤(2)，重新计算每个(自变化)簇的平均值。这个过程不断重复直到某个准则函数不再明显变化或者聚类的对象不再变化为止。

18 K均值聚类分析 【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表。 试将以上的样品聚成两类。 样品测量结果

19 K均值聚类分析 第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见下表所示。 中心坐标是通过原始数据计算得来的，比如（A、 B）类的， 等等。

20 K均值聚类分析 第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离： 由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：

21 K均值聚类分析 由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如下表所示。 更新后的中心坐标

22 K均值聚类分析 第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，结果见下表。
到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。

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

24 华南师范大学教育信息技术学院 XuXiaodong Lab 2003 Seminar
K-NN算法 联系每一个数据点到它的“K最邻近区” 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

25 K-Nearest Neighbor Graph
K-NN算法 K-Nearest Neighbor Graph 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

26 Nearest Neighbor Graph
K-NN算法 Nearest Neighbor Graph 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

27 Nearest Neighbor Graph
K-NN算法 Nearest Neighbor Graph 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

28 华南师范大学教育信息技术学院 XuXiaodong Lab 2003 Seminar
KNN（K最近邻）算法 (聚类文档) 该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下： 1:根据特征项集合重新描述训练文本向量 2:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

29 华南师范大学教育信息技术学院 XuXiaodong Lab 2003 Seminar
KNN（K最近邻）算法 (聚类文档) 3: 在训练文本集中选出与新文本最相似的 K 个文本，计算公式为： 其中，最相似标准的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整。 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

30 华南师范大学教育信息技术学院 XuXiaodong Lab 2003 Seminar
KNN（K最近邻）算法 (聚类文档) 4:在新文本的 K 个邻居中，依次计算每类的权重，计算公式如下： 其中， 为新文本的特征向量， 为相似度计算公式，与上一步骤的计算公式相同，而 为类别属性函数，即，如果 属于类 ，那么函数值为1，否则为0。 5:比较类的权重，将文本分到权重最大的那个类别中。 华南师范大学教育信息技术学院 XuXiaodong Lab Seminar

31 层次聚类方法 （hierarchical method）
定义：对给定的数据进行层次的分解： 分类： 凝聚方法（agglomerative）（自底向上） 思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。 分裂方法（divisive）（自顶向下） 思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。

32 层次聚类方法 （hierarchical method）
特点： 类的个数不需事先定好 需确定距离矩阵 运算量要大，适用于处理小样本数据

33 层次聚类方法 广泛采用的类间距离： 最小距离法（single linkage method） 极小异常值在实际中不多出现，避免极大值的影响

34 最短距离法 1. 最短距离法 定义类与之间的距离为两类最近样品的距离，即为 设类与合并成一个新类记为，则任一类与的距离为

35 最短距离法 最短距离法进行聚类分析的步骤如下： （1）定义样品之间距离，计算样品的两两距离，得一距离
阵记为D（0） ，开始每个样品自成一类，显然这时Dij = dij。 （2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个 新类，记为Gr，即Gr = ｛Gp，Gq｝。 （3）按（5.12）计算新类与其它类的距离。 （4）重复（2）、（3）两步，直到所有元素。并成一类为 止。如果某一步距离最小的元素不止一个，则对应这些 最小元素的类可以同时合并。

36 最短距离法 【例5.1】设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。
（1）样品采用绝对值距离，计算样品间的距离阵D（0） ，见表 表

37 最短距离法 （2）D（0）中最小的元素是D12＝D56＝1，于是将G1和G2合 表
并成G7，G5和G6合并成G8，并利用（5.12）式计算新类与其 它类的距离D（1） ，见下表： 表

38 最短距离法 （3）在D（1）中最小值是D34＝D48＝2，由于G4与G3合并， 表
又与G8合并，因此G3、G4、G8合并成一个新类G9，其与其 它类的距离D（2） ，见下表： 表

39 最短距离法 （4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程终止。 图 最短距离聚类法的过程
上述聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。 图 最短距离聚类法的过程

40 层次聚类方法 最大距离法（complete linkage method） 可能被极大值扭曲，删除这些值之后再聚类

41 最长距离法 最长距离法

42 最长距离法 再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同： 一是类与类之间的距离定义不同；
另一是计算新类与其它类的距离所用的公式不同。

43 层次聚类方法 类平均距离法（average linkage method）类间所有样本点的平均距离
该法利用了所有样本的信息，被认为是较好的系统聚类法

44 中间距离法 3. 中间距离法 (1／4    0) 设Dkq＞Dkp，如果采用最短距离法，则Dkr = Dkp，如果采用
最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介于两者之间的距离，称为中间距离法。 中间距离将类Gp与Gq类合并为类Gr，则任意的类Gk和Gr的距离公式为 (1／4    0) 设Dkq＞Dkp，如果采用最短距离法，则Dkr = Dkp，如果采用 最长距离法，则Dkr = Dkq。如图5.2所示，(5.15)式就是取它们（最长距离与最短距离）的中间一点作为计算Dkr的根据。

45 中间距离法 特别当 =  1／4，它表示取中间点算距离，公式为 图 中间距离法

46 层次聚类方法 重心法（centroid hierarchical method） 类的重心之间的距离 对异常值不敏感，结果更稳定

47 重心法

48 重心法

49 重心法

50 重心法

51 重心法 【例】针对例5.1的数据，试用重心法将它们聚类。 （1）样品采用欧氏距离，计算样品间的平方距离阵D2（0），见下表所示。 表

52 重心法 （2）D2（0）中最小的元素是D212＝D256＝1，于是将G1和G2合 其中， 其它结果类似可以求得
并成G7，G5和G6合并成G8，并计算新类与其它类的距离得到距离阵D2（1） ，见表 其中， 其它结果类似可以求得

53 重心法 （3）在D2（1）中最小值是D234＝4，那么G3与G4合并一个新类G9，其与与其它类的距离D2（2） ，见表： 表

54 重心法 （4）在中最小值是＝12.5，那么与合并一个新类，其与与 其它类的距离，见表：

55 重心法 （5）最后将G7和G10合并成G11，这时所有的六个样品聚为一类，其过程终止。 图 重心聚类法的过程
上述重心法聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。 图 重心聚类法的过程

56 离差平方和法 离差平方和法（ward method） 即 D2=WM－WK－WL
对异常值很敏感；对较大的类倾向产生较大的距离，从而不易合并，较符合实际需要。 Cluster K Cluster L Cluster M

57 类平均法

58 类平均法 6. 可变类平均法 由于类平均法中没有反映出Gp和Gq之间的距离Dpq的影响，
因此将类平均法进一步推广，如果将Gp和Gq合并为新类Gr，类Gk与新并类Gr的距离公式为： 其中是可变的且 <1，称这种系统聚类法为可变类平均法。

59 可变法

60 离差平方和法 8. 离差平方和法 该方法是Ward提出来的，所以又称为Ward法。该方法的基本思想来自于方差分析，如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。 设将n个样品分成k类G1，G2，…，Gk，用Xit表示Gt中的第I个样品，nt表示Gt中样品的个数， 是Gt的重心，则Gt的样品离差平方和为

61 离差平方和法

62 离差平方和法 这种系统聚类法称为离差平方和法或Ward方法。下面论证离差平方和法的距离递推式。

63 离差平方和法 由于

64 离差平方和法

65 离差平方和法

66 离差平方和法

67 类间距离的统一性 上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（Lance）和威廉姆斯（Williams）于1967年给出了一个统一的公式。 其中ap、aq、  、 是参数，不同的系统聚类法，它们取不同的数，详见表5.8。 这里应该注意，不同的聚类方法结果不一定完全相同，一般只是大致相似。如果有很大的差异，则应该仔细考查，找到问题所在；另外，可将聚类结果与实际问题对照，看哪一个结果更符合经验。

68 系统聚类法参数表

69 层次聚类方法 层次的方法缺陷一旦一个步骤（合并或分裂）完成，就不能被撤销或修正，因此产生了改进的层次聚类方法，如
BIRCH(balanced iterative reducing and clustering using hierarchies)算法 CURE(clustering using representatives)算法 ROCK(robua clustering using links)算法等

70 BIRCH算法 通过引入了聚类特征和聚类特征树概念，Zhang 等人提出BIRCH算法[Zhang et al ] 。聚类特征是一个包含关于簇的二元组，给出对象子聚类的信息汇总描述。如果某个子聚类中有N个d维的点或对象，则该子聚类的定义为CF=(N，LS，SS)，其中，N是子类中点的个数，LS是N个点的线性和，SS是点的平方和。聚类特征树中所存储的是关于聚类的信息，这些信息是计算聚类和有效利用存储的关键度量。每个叶节点包含一个或多个子聚类，每个子聚类中包含一个或多个对象。一个聚类特征树有两个参数：分支因子B和阈值T，分支因子B定义了每个非叶节点后代的最大数目，阈值参数T给出了存储在树的叶子节点中的子聚类的最大直径。BIRCH算法主要包括扫描数据库和聚类两个阶段。

71 BIRCH算法 (1)扫描数据库，建立一个初始存放于内存的聚类特征树，可以看作数据的多层压缩，试图保留数据内在的聚类结构。一个对象被插入到距其最近的叶节点(子聚类)中时，如果在插入对象后，存储在叶节点中的子聚类的直径大于阈值，那么该叶节点被分裂，也可能有其他节点被分裂。新对象插入后，关于该对象的信息向根节点传递。通过修改阈值，聚类特征树的大小可以改变。如果存储聚类特征树需要的内存大于主存的大小，可以定义一个较大的阈值，并重建聚类特征树。重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读所有的对象。因此为了建树，只需读一次数据。采用一些启发式规则和方法。通过额外的数据扫描来处理孤立点和改进CF树的质量。聚类特征树建好后，可以在阶段二被用于任何聚类算法。

72 BIRCH算法 (2)BIRCH采用某个聚类算法对聚类特征树的叶节点进行聚类。
B1RCH算法具有可伸缩性，算法的时间复杂度为O(n)(不重建聚类特征树时)，通过对数据集的首次扫描产生一个基本聚类，二次扫描进一步改进聚类质量并处理异常点。BIRCH算法的处理速度较快，但对非球形簇处理效果不好。

73 CURE算法 Guha 等人提出CURE(clustering using representatives)算法利用代表点进行聚类，解决了大多数聚类算法偏好球形和相似大小的问题，并且容易处理异常点[Guha et al.1998] 。CURE算法选用数据空间中固定数目的、具有代表性的点代表簇，然后根据一个特定的分数或收缩因子向簇中心“收缩”或将其移动。如果两个簇的代表点距离最近，则将这两个簇合并。 由于每个簇有一个以上的代表点，使CURE算法可以适应非球形的几何形状，而且簇的收缩或凝聚可以控制异常点的影响，因此CURE算法对异常点的处理更健壮。对于大型数据库，CURE算法有良好的伸缩性，不会降低聚类的质量

74 CURE算法 (1)从源数据集中抽取一个随机样本S，包含s个对象。 (2)将样本S分为p个划分，每个划分大小为s／p。
(3)将每个划分局部聚类成s／pq聚类，其中q>l。 (4)通过随机采样消除异常数据，若一个簇增长太慢，就删除该簇。 (5)对局部的簇进行再聚类，落在每个新形成的聚类中的代表点，则根据用户定义的收缩因子a收缩或向簇中心移动。这些点将用于代表并描绘出聚类的边界。 (6)对簇中的数据标记上相应簇标记。 CURE算法的时间复杂度为O(n)，最大问题是无法处理分类属性。

75 ROCK算法 Guha等人于1999年提出了一个面向分类属性数据的聚类算法ROCK [Guha et al. 2000]。其突出贡献是采用公共近邻（链接）数的全局信息作为评价数据点间相关性的度量标准，而不是传统的基于两点间距离的局部度量函数。 算法11.5 ROCK算法 Procedure cluster(S,k) (1) begin (2) link: = compute_links(S) (3) for each s∈S do (4) q[s]: = build_local_heap(link,s) (5) Q: = build_global_heap(S,q)

76 ROCK算法 (6) while size(Q)>k do { (7) u: = extract_max(Q)
(8) v: = max(q[u]) (9) delete(Q,v) (10) w: = merge(u,v) (11) for each x ∈ q[u] ∪q[v] { (12) link[x,w]:=link[x,u] + link[x,v] (13) delete(q[x],u); delete(q[x],v) (14) insert(q[x],w,g(x,w));insert(q[w],x,g(x,w)) (15) update(Q,x,q[x]) (16) }

77 ROCK算法 (17) insert(Q,w,q[w]) (18) deallocate(q[u]); deallocate(q[v])
(19) } (20) end 注意到算法中有两种队列，全局队列Q和普通队列q[i]。算法中compute_links(S)是预处理计算公共点的数量。

78 ROCK算法 procedure compute_links(S) begin
Compute inlist[i] for every point I in S Set link[I,j] to be zero for all i,j for i: = 1 to n do { N: = inlist[i]; for j: = 1 to |N|-1 do for l: = j+1 to |N| do link[ N[j], N[l] ]: = link[ N[j], N[l] ] + 1 } end

79 ROCK算法 在以往的算法中，两个对象之间的距离或相似性只与这两个对象本身有关，而与其他对象无关。ROCK算法将这一局部运算扩展成一种全局运算，在计算两个对象之间的距离或相似性时，不仅考虑两个对象本身，还考虑周围邻居的影响，增强了算法的抗噪声能力。为了能够处理大规模的数据，ROCK也采用随机抽样的方法。

80 基于密度的方法 （density-based method）
主要有DBSCAN，OPTICS法 思想： 只要临近区域的密度超过一定的阈值，就继续聚类 特点： 可以过滤噪声和孤立点outlier，发现任意形状的类

81 基于密度的方法 （density-based method）
以空间中的一点为中心，单位体积内点的个数称为该点的密度。基于密度的聚类（density-basedclustering）根据空间密度的差别，把具有相似密度的相邻的点作为一个聚类。密度聚类只要邻近区域的密度(对象或数据点的数目)超过某个阈值，就能够继续聚类。 也就是说，对给定类中的每个数据点，在一个给定的区域内必须至少包含某个数目的点。这样，密度聚类方法就可以用来过滤“噪声”异常点数据，发现任意形状的簇。

82 基于密度的方法 （density-based method）
密度聚类算法： 有基于高密度连接区域的DBSCAN(Density-based Spatial Clustedng ofApplication with Noise)算法 通过对象排序识别聚类结构的OPTICS(Ordering Points To Identify the Clustering Structure)算法 基于密度分布函数聚类的DENCLUE(DENsity．based CLUstEring)算法。

83 DBSCAN算法 DBSCAN通过不断生长足够高密度区域来进行聚类，它能从含有噪声的空间数据库中发现任意形状的聚类。DBSCAN方法将一个聚类定义为一组“密度相连”的点集。DBSCAN的基本思想涉及的一些概念如下： (1)对象的一邻域：给定对象的半径内的区域。 (2)核心点：一个对象的一邻域至少包含最小数目(MinPts)个对象，则称该对象为核心点。 (3)直接密度可达：给定一组对象集合D，如果p是在q的一邻域内，而q是一个核心点，则称对象p从对象q出发是直接密度可达的。

84 DBSCAN算法 (4)密度可达：如果存在一个对象链p1，p2，，pm，其中p1=p，且pm=q，对于pl∈D，(1≤i≤n)，pi+1是从p1关于和MinPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。 (5)密度相连：如果对象集合D中存在一个对象o，使得对象p和q是从o关于和MinPts密度可达的，则对象p和q是关于和MinPts密度相连的。 (6)边界点：非核心点，是从某一核心点直接密度可达的。 (7)噪声：聚类结束时，不属于任何簇的点。

85 DBSCAN算法 DBSCAN算法首先需要用户给定聚类对象的半径一邻域和一邻域中最小包含的对象数MinPts，然后算法检查某个对象—邻域中的对象数，如果对象数大于MinPts，该对象就是核心对象，就构建以该对象为核心的新簇。然后，反复寻找从这些核心对象出发在一邻域内的对象，这个寻找过程可能会合并一些簇，直到没有新的对象可以添加到任何簇中为止。一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。

86 基于网格的方法 （grid-based method）
网格聚类方法是将对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类操作都在这个网格结构(即量化的空间)上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，只与量化空间中每一维上的单元数目有关。 在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的STING(STatistical INformation Grid-based method)算法、用小波转换方法进行聚类的WaveCluster方法和在高维数据空问基于网格和密度的CLIQUE(Clustering InQUEst)聚类方法。 STING算法是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（用于回答查询）被预先计算和存储

87 STING算法 (1) 在层次结构中选定一层作为查询处理的开始点； (2) 对前层次的每个网格单元，计算出反映该单元与给定查询的关联程度的置信度区间； (3) 从上面计算的置信度区间中标识每个网格单元是否与给定查询相关； (4) 如果当前层是底层，则执行步骤(6)，否则执行步骤(5)； (5) 处理层次结构中的下一层，对于形成高层的相关网格单元执行步骤(2)； (6) 如果查询要求被满足，则执行步骤(8)；否则，执行步骤(7)； (7) 检索和进一步的处理落在相关单元中的数据，返回满足查询要求的结果。执行步骤(9)； (8) 寻找相关网格的区域，返回满足查询要求的相关单元的区域。执行步骤(9)； (9) 算法结束。

88 基于模型方法 （model-based method）
基于模型的聚类方法为每一个簇假定了一个模型，寻找数据对给定模型的最佳拟合，它试图优化给定的数据和某些数学模型之间的适应性，基于模型的方法经常假设数据是根据潜在的概率分布生成的，算法主要有统计学和神经网络两种。 1987年Fisher提出了COBWEB算法[Fisher，1987] 。 COBWEB是一种流行的简单增量概念聚类算法，它的输入对象用分类属性一值对来描述，COBWEB以一个分类树的形式创建层次聚类。分类树与判定树不同。分类树中的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。概率描述包括概念的概率和形如P(Ai=Vij|Ck)的条件概率，这里Ai=Vij 是属性一值对，Ck是概念类(计数被累计并存储在每个计算概率的节点)。这就与判定树不同，判定树标记分支而非节点，而且采用逻辑描述符，而不是概率描述符。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数来沿着“最佳”匹配节点的路径在树中向下移动。

89 COBWEB方法 （model-based method）
这里n是在树的某个层次上形成一个划分{Cl，C2，，Cn}的节点、概念或类别的数目。其中： (1)概率P(Ai=Vij|Ck)表示类内相似性。该值越大，共享该属性一值对的类成员比例就越大，更能预见该属性一值对是类成员。 (2)概率P(Ck|Ai=Vij)表示类间相异性。该值越大，在对照类中的对象共享该属性一值对就越少，更能预见该属性一值对是类成员。

90 AutoClass方法 AutoClass是一种基于贝叶斯理论的数据聚类算法[Cheeseman et al.1996] , 通过对数据进行处理, 计算出每条数据属于每个类别的概率值, 将数据进行聚类。 AutoClass能对复杂数据进行精确的自动聚类，可以事先设定好类别数目让AutoClass自动寻找,在寻找结束后, 能够得到每一条数据分别属于每一类别的几率。AutoClass的程序是由Cheeseman和Stutz在1995年开发出来的。

91 AutoClass方法 AutoClass具有以下的优点: (1) 聚类的数据不需要预先给定数据的类别, 但是定义了每个数据成员。
(3) AutoClass 要求将资料存成Data File(存数据文件)与Header File(描述数据的文件)两部分, 如此可以让使用者自由搭配Data File 和Header File 而节省输入数据的时间. (4) 可以处理缺值数据。当一组数据中的某些属性值有缺漏时, AutoClass仍可将此组数据进行聚类。

92 AutoClass方法 AutoClass也存在以下缺点:
(4)没有提供一个先验标准来预测一组数据是否能够聚类, 因而带有一定的臆断性。没有提供一个后验方法来评估分类的结果是否可以信赖。

93 蚁群聚类方法 可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解 。
任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置都称为群体智能。 群体智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。 2019/1/2 高级人工智能 史忠植

94 群体智能的特点 分布式：能够适应当前网络环境下的工作状态; 鲁棒性：没有中心的控制与数据，个体的故障不影响整个问题的求解;
扩充性：个体的增加，系统的通信开销增加小; 简单性：个体简单，实现也比较简单。 2019/1/2 高级人工智能 史忠植

95 蚁群算法 蚁群寻食行为研究，相对应组合优化算法和通信网络路由控制算法； 群体分工和任务分配行为研究，相对应多主体分工协作算法；
巢穴组织和自组织行为及群体分类行为研究，相对应数据分析和图的分割算法； 建巢和自装配行为研究，相对应模拟建巢算法； 群体合作搬运行为研究，相对应机器人合作搬运算法。 2019/1/2 高级人工智能 史忠植

96 蚁群算法的关键问题 蚁群算法 效率与理论； 由于没有标准的测试集，除了寻食模型，蚁卵聚类、蚁群分工和蚁巢自装配等模型都只处于证实阶段 理论和实验 ； 一个多主体自组织模型实验和测试平台 ； 对于追求效率的实际问题，如何既保持群体智能系统的灵活性和鲁棒性等自组织特征又能保证系统的高效率也是一个关键问题 ； 群体智能与分布式智能的智能主体研究相结合，将产生新的智能主体协作、建模等算法和机制，提出网络和网格环境的自适应多智能主体系统 。 2019/1/2 高级人工智能 史忠植

97 蚂蚁寻找最短路径原理 外激素多的短路径将吸收更多的蚂蚁，反过来，更多的蚂蚁在短路径上会留下更多的外激素，加上外激素挥发效应，最后，蚁群都选择了最短路径。 A）蚁群到达决策点。 B）一些蚂蚁选择上方路径，一些蚂蚁选择下方路径。选择是随机的。 C）下方短路径蚂蚁到达相反方向的决策点的时间早于选择上方长路径的蚂蚁。 D）短路径上外激素以较高的速度积累。。 2019/1/2 高级人工智能 史忠植

98 蚁群算法 第k个蚂蚁从城市i到城市j 的跃迁概率为： τij（t）为t时刻边e(i,j)上外激素的强度 可见度ij为1/dij
2019/1/2 高级人工智能 史忠植

99 一种基于蚁群算法的TSP问题分段 蚁群算法
求解算法 相遇算法，提高了蚂蚁一次周游的质量， 然后将相遇算法与采用并行策略的分段算法相结合，提出一种基于蚁群算法的TSP问题分段求解算法。 实验结果表明该算法有较好的有效性。 2019/1/2 高级人工智能 史忠植

100 TSP蚁群算法 实例 ST70 （TSPLIB） 677.88 677.1096 CHC144 （中国144城市）30354.3
kroB150 (TSPLIB) 2019/1/2 高级人工智能 史忠植

101 蚁群聚类算法CSI的研究 CSI聚类算法主要步骤； 基本模型简化：概率转换公式； 实验结果 。 2019/1/2 高级人工智能 史忠植

102 基于蚁群算法的聚类算法 主要步骤： 随机分布待聚类模式；
每只蚂蚁计算当前对象在局部环境的群体相似度，并通过概率转换函数得到拾起或放下对象的概率，以这个概率行动； 经过群体大量的相互作用，最终得到若干聚类中心； 最后收集聚类结果。 2019/1/2 高级人工智能 史忠植

103 概率转换公式的简化 基本模型 简化模型 2019/1/2 高级人工智能 史忠植

104 实验结果 2019/1/2 高级人工智能 史忠植

105 电信消费数据聚类分析实验结果比较 2019/1/2 高级人工智能 史忠植

106 基于群体智能的文档聚类算法CSIM的研究
为了处理聚类过程中出现的散点以及克服算法的一些随机因素，更是为了提高算法的效率，我们将基于群体智能的文档聚类算法与经典的K均值算法相结合，对算法进行了改进。 混合算法的过程是这样的：首先采用基于群体智能文档聚类算法对聚类文档进行处理，得到初始的聚类中心个数和聚类中心模板，然后运用K均值算法再次聚类。 这样，既保留了群体智能算法的自组织特征，又结合了K均值算法的高效率，同时也克服了两种算法的弱点，如群体智能算法的随机性和K均值算法的聚类中心个数的参数预定及输入顺序敏感。我们将算法缩写为CSIM。 2019/1/2 高级人工智能 史忠植

107 基于群体智能的文档聚类算法CSIM的研究
数据集 文档数 维数 类别 来源 D1 394 833 Gold,Coffee,Sugar Reuters-21578 D2 323 600 GNP,Livestock,Sugar D3 1000 496 Football FM365 网站 2019/1/2 高级人工智能 史忠植

108 基于群体智能的文档聚类算法CSIM的研究
数据集 聚类中心个数 CSIM 正确率 k-means正确率 CSI正确率 CSI 散点 D1 6.5 16 98.2% 97.4% 99.0% 5.6% 8 11 98.5% 97.2% 99.4% 2.1% 9 10 95.4% 92.4% 0.9% D2 92.5% 88.5% 94.7% 10% 这个结果达到了SONIA系统所用文档聚类算法的水平，而SONIA的算法性能明显高于Scatter/Gather和 TFIDF 方法。 2019/1/2 高级人工智能 史忠植

109 七、粒度计算 粒度计算从广义上来说是一种看待客观世界的世界观和方法论。
粒度计算的基本思想就是使用粒而不是对象为计算单元，使用粒、粒集以及粒间关系进行计算或问题求解。 2019/1/2 高级人工智能 史忠植

110 粒度计算 1997年Lotfi A. Zadeh 提出了粒度的概念，他认为在人类认知中存在三种概念：粒度，组织与因果关系。从直观的来讲，粒化涉及到从整体到部分的分解，而组织却是从部分到整体的集成，而因果关系涉及原因与结果之间的联系。对一个事物的粒化就是以可分辨性、相似性、邻近性与功能性集聚有关的事物。 粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究，主要用于处理不确定的、模糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息粒度理论、粗糙集理论、商空间理论、区间计算等的超集，另一方面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中，应用了分组、分类、聚类以及层次化手段的一切理论与方法均属于粒度计算的范畴。信息粒度在粒度计算，词计算，感知计算理论和精化自然语言中都有反映 2019/1/2 高级人工智能 史忠植

111 粒度计算的必要性 从哲学的角度看 从人工智能的角度看
Yager和Filev指出“人类已经形成了世界就是一个粒度的观点”以及 “人们观察、度量、定义和推理的实体都是粒度” 。信息粒是一种抽象，它如同数学中的“点”、“线”、“面”一样，在人类的思维和活动中占有重要地位。 从人工智能的角度看 张钹院士指出“人类智能的公认特点，就是人们能从极不相同的粒度上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解，而且能够很快地从一个粒度世界跳到另一个粒度的世界，往返自如，毫无困难。这种处理不同世界的能力，正是人类问题求解的强有力的表现” 。 2019/1/2 高级人工智能 史忠植

112 粒度计算的必要性 从优化论的角度来看 粒度计算的理论与方法在观念上突破了传统优化思想的束缚，不再以数学上的精确解为目标，即：需要的是很好地理解和刻画一个问题，而不是沉溺于那些用处不大的细节信息上。粒度计算的方法不要求目标函数和约束函数的连续性与凸性，甚至有时连解析表达式都不要求，而且对计算中数据的不确定性也有很强地适应能力，计算速度也快，这些优点使粒度计算具有更广泛地应用前景，所以，粒度计算理论的研究对推动优化领域的发展极其重要。 2019/1/2 高级人工智能 史忠植

113 粒度计算的必要性 从问题求解的角度看 从应用技术的角度看
用粒度计算的观点来分析解决问题显得尤为重要，这样就不用局限于具体对象的细节。除此之外，将复杂问题划分为一系列更容易管理和更小的子任务，可以降低全局计算代价。 从应用技术的角度看 图像处理、语音与字符识别等，是计算机多媒体的核心技术。这些信息处理质量的好坏直接依赖于分割的方法和技术，而粒度计算的研究或许能够解决这一问题。 2019/1/2 高级人工智能 史忠植

114 粒度计算的基本问题 两大问题 粒的构造 ：处理粒的形成、表示和解释 使用粒的计算：处理在问题求解中粒的运用 两个方面
从语义 上：侧重于对粒的解释 ，如为什么两个对象会在同一个粒之中，为什么不同的粒会相关。 从算法上：如何进行粒化和如何进行基于粒的计算。对粒的分解与合并方法的研究，是构建任何粒度体系结构的本质要求。 2019/1/2 高级人工智能 史忠植

115 粒度计算的国内外研究现状 粗糙集理论 粒：等价类，子集 粒的计算：粒之间的近似 商空间理论 粒：等价类，子集，粒之间具有拓扑关系
粒的计算：合成、分解 词计算理论 粒：词 粒的计算：模糊数学 2019/1/2 高级人工智能 史忠植

116 2019/1/2 高级人工智能 史忠植

117 商空间粒度模型 张铃, 张钹把商空间的概念通过模糊等价关系推广到模糊集合上，他们证明下面4种提法等价： 在论域X上给定一个模糊等价关系
2019/1/2 高级人工智能 史忠植

118 存在的问题 粒的定义：子集，没有内涵，无法区分粒和类 粒的元素：粒的元素为基本对象，不能为粒 粒的嵌套层次结构简单
粒的功能是用于描述和近似，而对于问题求解作用不大（明显） 2019/1/2 高级人工智能 史忠植

119 相关工作 基于近似和相容关系的粒度模型 层次和嵌套模型 近似空间 变精度粗糙集模型 相容空间 由嵌套等价关系序列引导的嵌套粗糙集近似
由层次结构引导的层次粗糙集近似 由邻域系统引导的层次粗糙集近似 2019/1/2 高级人工智能 史忠植

120 相容粒度空间模型 四元组(OS, TR, FG, NTC) OS 表示对象集系统 TR 表示一个相容关系系统 FG表示相容粒转换函数
嵌套相容覆盖系统是一个参数化的粒度结构，其中定义了不同层次的粒和基于对象系统和相容关系系统的参数化过程。它定义了： ａ. 粒之间、粒集之间、对象之间以及粒和对象之间的关系； b. 粒的合成和分 解。 对象集系统由在相容粒度空间中处理和粒化的对象组成，它也可以看成是一个对象域 相容关系系统是一个参数化的关系结构，它由一组相容关系组成，包括一个粒度空间所基于的关系和参数 2019/1/2 高级人工智能 史忠植

121 相容粒 用一个三元组来描述相容粒G=(IG, EG, FG) IG：相容粒G的内涵，用向量表示 EG：相容粒G的外延，用向量的集合表示
定义了粒的内涵和外延之间的转换，可以用函数、规则、算法等形式来描述 描述了相容粒在特定环境下表现的知识，并表示在一个特定任务下相容粒中所有元素的一般性特征、规则、共同性等 粒，根据它的名字可知，是实体的集合，这些实体通常来源于数据层。这些数据根据他们的相似性，功能临近性，不可分辨性，一致性等组织在一起；同时，粒也是我们现实的抽象，它的目标是建立高效的以及以用户为中心的对于外界世界的观点，从而支持和帮助我们对周围物理和虚拟世界的感知。因此一个粒不仅仅是实体的聚类或者集合，同时也是这些聚类或者集合的抽象。这是粒和集合或者聚类不同点所在。 包含这个粒所涵盖的对象或粒 2019/1/2 高级人工智能 史忠植

122 Zhongzhi Shi etc image seg
相容关系 A tolerance relation tr, trXX, is a reflexive and symmetrical binary relation, where X is the original space of object vector and X∈Rn. A simple tolerance proposition sp(α, β|dis, d) is defined as A compound tolerance proposition cp(α,β|DIS,D) . 2019/1/2 2019/1/2 Zhongzhi Shi Granular Computing Zhongzhi Shi etc image seg 122 122

123 Zhongzhi Shi etc image seg
变换函数 Suppose that X is universe of G’s extension EG, and Y is universe of G’s intension. FG is formalized as follows. Generalization transformation function: let FG be a function form X to Y, i.e., FG : X → Y where EG and IG are condition variable and decision variable, respectively; and X and Y are domain and range of function FG, respectively. 2019/1/2 Zhongzhi Shi etc image seg

124 Zhongzhi Shi etc image seg
变换函数 Specialization transformation function: Let FG-1 be a function form Y to X, i.e., FG-1 : Y → X Transformation function can be expressed in a variety of forms, such as linear function, nonlinear function, rule function, algorithm(action as a function), and so on. 2019/1/2 Zhongzhi Shi etc image seg

125 Zhongzhi Shi etc image seg
嵌套相容覆盖系统 Nested tolerance covering system is a kind of parameterized granular structure, which provides a mechanism for representing the relationship between granules, sets of granules, objects, granule and object, as well as for synthesis and decomposition of granules. parameterized definition of tolerance granule By parameterized definition, the universe of tolerance granule on TG is expressed as 2019/1/2 Zhongzhi Shi etc image seg

126 Zhongzhi Shi etc image seg
嵌套相容覆盖系统 构建 NTC Tolerance covering on layer i is defined as then the top-down approach to constructing NTC can be described as follows: Step1: initializing Constructing granule G10 = on layer 0. 2019/1/2 Zhongzhi Shi etc image seg

127 Zhongzhi Shi etc image seg
嵌套相容覆盖系统 construction of NTC Step2: Calculate granule Step3: Calculate Step4: By using every granule on layer 0 as original or the lowest granule, the nested tolerance covering NTC2 on O2 can be constructed by the above steps. Similarly, NTCk on Ok can be constructed by using Ok-1. At last, The nested tolerance covering system can be generated as follows: NTC={NTC1, …, NTCk, …}. 2019/1/2 Zhongzhi Shi etc image seg

128 相容粒度空间模型的主要特点 功能特点 建模所基于关系的特点 粒的定义的特点 粒度空间结构的特点
粒度计算的功能不仅仅在于对问题的简化和近似化，更在于以粒为单位通过粒之间的关系进行计算在某些问题的解决中不可替代的作用。 建模所基于关系的特点 相容关系 粒的定义的特点 粒度空间结构的特点 通过定义粒的三种关系：内涵关系、外延关系和复合关系，以及粒度空间的层次和嵌套结构实现了这种粒之间和粒度层次之间交互跳跃的能力。 2019/1/2 高级人工智能 史忠植

129 Question! Thank You Intelligence Science http://www.intsci.ac.cn/ NN 1
10-00 Thank You Question! Intelligence Science 2019/1/2 史忠植 强化学习 Elene Marchiori