史忠植 高级人工智能(中科院)第十一章

2012-05-11高级人工智能史忠植1高级人工智能第十一章史忠植中国科学院计算技术研究所无监督学习UnsupervisedLearning2012-05-11高级人工智能史忠植2内容提要一、概述二、相似性度量三、划分方法四、层次聚类方法五、基于密度的聚类六、基于网格方法七、基于模型方法八、蚁群聚类方法十、粒度计算概述无监督学习不要求对数据进行事先标定，在数据的分类结构未知时，按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内相似性尽量大。利用无监督学习期望能够发现数据集中自身隐藏的内蕴结构信息。无监督学习也称聚类分析。无监督学习源于许多研究领域，受到很多应用需求的推动。例如，在复杂网络分析中，人们希望发现具有内在紧密联系的社团在图像分析中，人们希望将图像分割成具有类似性质的区域在文本处理中，人们希望发现具有相同主题的文本子集在有损编码技术中，人们希望找到信息损失最小的编码在顾客行为分析中，人们希望发现消费方式类似的顾客群，以便制订有针对性的客户管理方式和提高营销效率。这些情况都可以在适当的条件下归为聚类分析。概述“物以类聚，人以群分”。一般的聚类算法是先选择若干个模式点作为聚类的中心。每一中心代表一个类别，按照某种相似性度量方法（如最小距离方法）将各模式归于各聚类中心所代表的类别，形成初始分类。然后由聚类准则判断初始分类是否合理，如果不合理就修改分类，如此反复迭代运算，直到合理为止。与监督学习不同，无监督法是边学习边分类，通过学习找到相同的类别，然后将该类与其它类区分开。聚类分析聚类分析(clusteranalysis)是将样品个体或指标变量按其具有的特性进行分类的一种统计分析方法。o对样品进行聚类，称为样品(Q型)聚类分析。其目的是将分类不明确的样品按性质相似程度分成若干组，从而发现同类样品的共性和不同类样品间的差异。o对指标进行聚类，称为指标（R型）聚类分析。其目的是将分类不明确的指标按性质相似程度分成若干组，从而在尽量不损失信息的条件下，用一组少量的指标来代替原来的多个指标（主成分分析？因子分析？）典型的数据聚类基本步骤如下：(1)对数据集进行表示和预处理，包括数据清洗、特征选择或特征抽取；(2)给定数据之间的相似度或相异度及其定义方法；(3)根据相似度，对数据进行划分，即聚类；(4)对聚类结果进行评估。聚类分析相似性度量如何刻画样品/（指标）变量间的亲疏关系或相似程度？样品相似性的度量变量相似性的度量相似系数度量相似系数体现对象间的相似程度，反映样本之间相对于某些属性的相似程度。确定相似系数有很多方法，这里列出一些常用的方法，可以根据实际问题选择使用。设为被分类对象的全体，以表示每一对象的特征数据。令xi,xj∈O,rij是xi和xj之间的相似系数，满足以下条件：rij=1⇔xi=xj∀xi,xj,rij∈[0,1]∀xi,xj,rij=rji相似系数度量1.数量积法.1;11≠==∑=mkjkikijjixxMjir)(max1∑=≠≥mkjkikjixxM其中，M为正数，满足相似系数度量2、夹角余弦两变量Xi与Xj看作p维空间的两个向量，这两个向量间的夹角余弦可用下式进行计算显然，∣cosθij∣≤1。12211cos()()pikjkkijppikjkkkXXXXθ====∑∑∑相似系数度量3．相关系数相关系数经常用来度量变量间的相似性。变量Xi与Xj的相关系数定义为显然也有，∣rij∣≤1。12211()()()()pikijkjkijppikijkjkkXXXXrXXXX===−−=−−∑∑∑相似系数度量4．最大最小法)()(11∑∑==∨∧=mkjkikmkjkikijxxxxr5．算术平均最小法)()(211∑∑==+∧=mkjkikmkjkikijxxxxr相似系数度量6．几何平均最小法7．绝对值指数法)(11∑∑==∧=mkjkikmkjkikijxxxxr1||∑==−−mkjkikxxijer相似系数度量8．指数相似系数法9．绝对值倒数法11)(22∑=−−=mksxxijkjkikemr||11jixxMjirmkjkikij≠−==∑=相似系数度量10．绝对值减数法12.贴近度法||11∑=−−=mkjkikijxxcr11．非参数法13.专家打分法划分方法划分聚类方法(partitioningmethod，PAM)是给定一个有n个对象或元组的的数据库构建k个划分的方法。每个划分为一个类（或簇），并且k≤n。每个类至少包含一个对象，每个对象必须属于而且只能属于一个类(模糊划分计算除外)。所形成的聚类将使得一个客观划分标准最优化，从而使得一个聚类中对象是“相似”的，而不同聚类中的对象是“不相似”的K均值聚类分析K均值法是麦奎因（MacQueen，1967）提出的，这种算法的基本思想是将每一个样品分配给最近中心（均值）的类中，具体的算法至少包括以下三个步骤：(1)从n个数据对象随机选取k个对象作为初始簇中心。(2)计算每个簇的平均值，并用该平均值代表相应的簇。(3)计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。(4)转步骤(2)，重新计算每个(自变化)簇的平均值。这个过程不断重复直到某个准则函数不再明显变化或者聚类的对象不再变化为止。K均值聚类分析【例】假定我们对A、B、C、D四个样品分别测量两个变量和得到结果见表。试将以上的样品聚成两类。样品变量1X2XA53B-11C1-2D-3-2样品测量结果K均值聚类分析第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见下表所示。中心坐标是通过原始数据计算得来的，比如（A、B）类的，等等。中心坐标聚类1X2X（A、B）22（C、D）-1-215(1)22X+−==K均值聚类分析第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离：由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：10)23()25())(,(222=−+−=ABAd61)23()15())(,(222=+++=CDAd10)21()21())(,(222=−+−−=ABBd9)21()11())(,(222=+++−=CDBdK均值聚类分析由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）。更新中心坐标如下表所示。中心坐标聚类1X2X（A）53（B、C、D）-1-1更新后的中心坐标K均值聚类分析第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方，结果见下表。到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类。样品到中心的距离平方聚类ABCD（A）0404189（B、C、D）52455距离选择的原则一般说来，同一批数据采用不同的距离公式，会得到不同的分类结果。产生不同结果的原因，主要是由于不同的距离公式的侧重点和实际意义都有不同。因此我们在进行聚类分析时，应注意距离公式的选择。通常选择距离公式应注意遵循以下的基本原则：（1）要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。（2）要综合考虑对样本观测数据的预处理和将要采用的聚类分析方法。如在进行聚类分析之前已经对变量作了标准化处理，则通常就可采用欧氏距离。（3）要考虑研究对象的特点和计算量的大小。样品间距离公式的选择是一个比较复杂且带有一定主观性的问题，我们应根据研究对象的特点不同做出具体分折。实际中，聚类分析前不妨试探性地多选择几个距离公式分别进行聚类，然后对聚类分析的结果进行对比分析，以确定最合适的距离测度方法。层次聚类方法（hierarchicalmethod）定义：对给定的数据进行层次的分解：分类：凝聚方法（agglomerative）（自底向上）思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。分裂方法（divisive）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。层次聚类方法（hierarchicalmethod）特点：类的个数不需事先定好需确定距离矩阵运算量要大，适用于处理小样本数据层次聚类方法广泛采用的类间距离：最小距离法（singlelinkagemethod）极小异常值在实际中不多出现，避免极大值的影响最短距离法1.最短距离法定义类与之间的距离为两类最近样品的距离，即为设类与合并成一个新类记为，则任一类与的距离为ijGXGXijdDjjii∈∈=,min,minikjrkrijXGXGDd∈∈=,,min{min,min}ikjpikjqijijXGXGxGxGdd∈∈∈∈=min{,}kpkqDD=最短距离法最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离阵记为D（0），开始每个样品自成一类，显然这时Dij=dij。（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，即Gr=｛Gp，Gq｝。（3）按（5.12）计算新类与其它类的距离。（4）重复（2）、（3）两步，直到所有元素。并成一类为止。如果某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并。最短距离法【例5.1】设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。（1）样品采用绝对值距离，计算样品间的距离阵D（0），见表G1G2G3G4G5G6G10G210G3430G46520G587420G6985310表最短距离法（2）D（0）中最小的元素是D12＝D56＝1，于是将G1和G2合并成G7，G5和G6合并成G8，并利用（5.12）式计算新类与其它类的距离D（1），见下表：G7G3G4G8G70G330G4520G87420表最短距离法（3）在D（1）中最小值是D34＝D48＝2，由于G4与G3合并，又与G8合并，因此G3、G4、G8合并成一个新类G9，其与其它类的距离D（2），见下表：G7G9G70G930表最短距离法（4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程终止。上述聚类的可视化过程见下图所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。图最短距离聚类法的过程层次聚类方法最大距离法（completelinkagemethod）可能被极大值扭曲，删除这些值之后再聚类最长距离法2.最长距离法定义类iG与jG之间的距离为两类最远样品的距离，即为,maxipjqpqijXGXGDd∈∈=最长距离法与最短距离法的并类步骤完全一样，也是将各样品先自成一类，然后将距离最小的两类合并。将类pG与qG合并为rG，则任一类kG与rG的类间距离公式为最长距离法再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；另一是计算新类与其它类的距离所用的公式不同。,maxikjrkrijXGXGDd∈∈=,,max{max,max}ikjpjikjqijijXGXGxGxGdd∈∈∈∈=max{,}kpkqDD=层次聚类方法类平均距离法（averagelinkagemethod）类间所有样本点的平均距离该法利用了所有样本的信息，被认为是较好的系统聚类法中间距离法3.中间距离法最短、最长距离定义表示都是极端情况，我们定义类间