分类技术讲解

1、第4章分类技术我们知道，世界上存在万事万物，每个事物都有自己的特点，但也存在一些共性。当我们遇到某 一事物时，总是在脑子里对事物进行分析，抽象出事物的属性，也就是事物具有的性质。事物的属性 可能包括与其他事物相同的性质，称作共性。也可能包括与其他事物不同的性质，称作特性。分类就 是根据事物的属性取值将事物分成不同的类。事物的属性可以用图 i表示。属性i事物属性2图1事物的属性表示模型我们平常所说的“按某某分类，就是指按事物的某个属性的取值进行分类。例如，按性别将人分为男、女，就是根据人的性别属性的取值“男”或“女”将人分为两类。这种能够利用单个属性的取 值即能区分事物的分类很简单，但很多情况不

2、是这样，例如如何根据动物的生活习性进行分类？考虑对人们对事物的分类过程，可以概括为以下步骤：(1 )对事物抽象，得出能够描述事物的关键属性；(2)提取或计算事物关键属性的取值征；(3 )根据事物的关键属性取值对事物分类。事物的关键属性的取值常作为判别事物的特征。根据事物的特征对事物分类有两种情况：已经预 先分好了类和还没有预先分好类，或者有监督的分类和无监督的分类。第一种情况相对简单，通常是 在已知道了分类种数和已分类样本的情况下按某种原则对新的样本进行分类。第二种情况通常是在没有规定分类种数的情况下，根据所有样本的特征按某种规则将所有样本分成适当的种类。第二种情况是在没有监督的情况下进行的，

3、又称聚类，难度往往比较大，有时很难给出合适的分类种数。例如， 如何根据内容对当前缤纷万千的Web网页进行恰当的分类。综合起来，对事物分类需要对事物的内容和特征进行分析，确定事物的关键属性和取值范围，提 取或计算事物的特征值，计算事物特征间的差别或相似性，按一定规则将事物分类。事物的特征提取 是根据具体事物的特点和应用，选择适当的事物特征和提取方法。例如，在基于内容的图像检索和图 像识别中，图像的颜色、纹理、边缘、形状等参数都是图像的重要特征。本章主要介绍智能系统中常 用的分类技术。，单参数的简单分类和多参数的模糊分类。第一节相似性测度要对事物进行分类，首先要对事物间的差别或相似性进行判断。对事

4、物分类的基本原则是同一类的事物尽量相似，不同类间事物的差距尽量大。因此，量度事物间的差距或计算他们的相似性是分类 技术必不可少的工作。要完成这些工作，需要建立表示事物特征的数学模型和相应的相似度计算方法。按图1所示的事物特征表示方法，设事物 x,它有M个特征，有N个样本。样本 为可以表示为 Xi= a i i ,a2 i, ,aM i o其中i =1,2,i,N是样本编号，au, a aa m i是每个特征的取值，可以是子符型、逻辑型和数值型等，根据具体属性而定。当 a a2i, 3m i的取值是相同的域时，事物 x可以用M维矢量表示，即 xi= ai总2/-,aM,。这样，事物及其特征可以用

5、矢量模型表示，每个事物样本为均可以用一个 M维矢量为表示，比较两个事物的差别就成为计算两个矢量的距离。在M维矢量空间中，常用的两个矢量的距离计算方法：1/r，C r）Minkowsky 距离：D （x, y）=lXi xi - yi g J mEudidean 品巨离：D ( x, y )= J工(ximManhanttan(City Block)距离： D (x, y)=工 为 一 yi i 4mChebychev 距离： D (x, y ) = max xi - yi 二X yCamberra 品巨离： D (x, y ) = Z y x +yiMax-Min 距离:mD x, y =、i

6、 1min 凶,yi /max(x, yjTm m、Quadratic 距离：D( x, y)=(x y) Q (x y) = E IZ (x -乂 m(xj - yj )TliVJ1/mT jMahalanobis 距离：D (x, y)=ldetV (x y) V (x y)Chi-square 距离：D ( x, y )= Z -x-曰 sum Sizq对于Minkowsky距离，当 丫 =1时，成为 Manhattan（City-Block 街区）距离；当 丫 =2时，成为 Euclidean 距离；当 丫 一8时，成为 Chebychev （棋盘） 距离。事物的相似性和差距是两个相反

7、的概念，事物的差距越大其相似性越小，反之亦然。两个矢量xi、x2间的相似性可以由两个矢量间的距离转换求得，也可以直接计算求得。 归一化（取值范围01）的相似性可以由两个矢量间的距离线性转换求得：也可以按某种特殊要求由非线性转换求得，如：_1sj （2 f N Q十 1 一do I dij do J -dij ）当dj=do时Sj=0.5,相当于半功率点，可以作为相似的 判断阈值。曲线如图 2。在一些场合，常用两个矢量与、x2间的相关系数量度两图2相似性与距离的一种转换曲线者的相似性，即:相关性:D x,y =m_ 2 m HYPERLINK l bookmark8 o Current Docu

8、ment xi -xi工yi 1i 1一 2-yiKendall Rank 相关性:2v 2x xrirjr z1图3k-近邻法示意图R.一 xri xrj 夹角余弦：sj = r 口jRRm i -1二二 sign xi -xj sign y - yji j 4第二节有监督的分类方法分类通常是在已知分类类别数的情况下，对每个样本确定为某一类的过程。在这种情况下，已知分类的类别数，再制定适当的分类准则就很容易对新样本分类。例如，根据亮度阈值将灰度图像变换 为黑白图像，将学生考试成绩的分值转换为“优、良、中、差”等。有监督的分类，通常已知分类类别数和已分类的样本。已分类的样本可以用于分类训练，可

9、以计算分类类别中心的情况。一种最简单的分类方法是将样本划归到最近类别中心的类，即最近距离法。但这种方法对于类别大小不同的情况不合理，因而有出现了近邻法和 k-近邻法。近邻法是将样本划归到最近的已分类样本所属的类别中，k-近邻法是将样本划归到 k个最近样本中多数样本所属的类别中。对于一些更复杂的情况，需要进行更为鲁棒的模湖分类，如BP神经网络分类器和 SVM分类器。K-近邻法假设共有n个样本，分为c类。第ic(i =(1,2, |H, c)类有 n 个样本，且 ni = n i 1在待分类样本x的近邻区域内的 k个已分类c样本中，属于第i类有ki个，且Z K = k。则x属 iW于第r类：r =

10、arg max & i =(1,2,III, c )o i如图2, Arg意思是“使”。利用BP神经网络分类神经网络系统是由大量的、简单的神经元广泛连接而形成的复杂系统。一般认为，神经网络系统是一个高度复杂的非线性动力学系统，每个神经元的结构和功能十分简单，但大量神经元构成的网络系统的行为却是十分复杂。单个神经元的结构如图4。图4单个神经元的结构神经网络有多种数学模型，主要有4类：前向型、反馈型、随机型和自组织竞争型。M-P数学模型是Mccu110ch (生理学家)和 Pitts(数理逻辑学家)1943年提出第一个神经元的前向型数学模型， 如图5。图5 M-P模型输入向量：X=(Xl,X2,

11、,Xn) 权值向量：W=(W,W2,Wn) 阈值：9n输出：y=f(二 Wix -)i 1输入输出变换函数：f(x)输入输出变换函数有多种形式，常用的变换函数如下表:变换函数公式0w说明阶跃函数：1 x 之 0 f (x)=/0 x 0(5-43)yi (w Xi +b )-1 0(5-44)ai (Yi (w X +b )-1 ) = 0(5-45)(5-44)和(5-45)式表明，只有满足 yi (w X +b )1 =0的样本，才能使 ai0,而对满足yi (w x +b )1 a0的样本，必须使 ai=0。使ai0的样本就是支持向量，对应的 ai记为3 ,取优分 界面的权向量w*由a；

12、和支持向量的线性组合生成：Nw = ajy?(5-46)i 4为了求出a；,将(5-41)、 (5-42)式代回(5-40)式，得(5-40)式的对偶函数：N1 NLd = ai -Z aajyiyj (k Xj )(5-47)i 12 i,j =1拉格朗日理论证明，(5-47)式的极大值解和(5-40)式的条件极小值界相同，因此利用(5-47)式可以求出aj,代入(5-46)式得w*o在w*确定之后，利用某个支持向量和(4-45)式，求出b*值，即：b* = yi w* Xi(5-48)利用符号函数对任意向量分类，即：N N)f (x) =sgn(w* X )+b* ) = sgn 工 a*

13、Mx x)+b*(5-49)n.1上式只包含分类样本与训练样本中支持向量的点积，计算量大大减小。(2)非线性可分条件下的支持向量机最优分界面在非线性可分的条件下，可以采用特征映射方法，将非线性可分的特征向量空间映射到线性可分的新的特征向量空间(特征向量空间的维数通常会增加很多)中，然后再利用线性可分的支持向量机 进行分类。利用特征映射方法的原理示意图如图8所示，其中图(a)表示在原特征空间中非线性可分的两类样本，图(b)表示经特征映射后在新特征空间中非线性可分的两类样本变成线性可分的情 况。如果将原来的特征向量X映射为f(Xi),则相应的对偶函数变成：N1 NLd = ai -Z aiajyi

14、yj (f (为)f 3)(5-50)i =12 i 衽X（X）（X）（O）、 （X）（O）.（X）（O）(a)非线性不可分(b)映射后变成线性可分图8非线性可分经映射后变成线性可分分类界面方程变成:N a% (f 仔)，f (x )+b* =0(5-51)i 1确定特征映射函数很困难，而且也没必要。因此，支持向量机理论提出利用某种与f (xi ) f (xj )等价的核函数 K (xi,xj )代替f (x ), f (Xj )的点积(或内积)。这样，相应的对偶函数变成:Ni NLd =ai -aiajyiyjK xi,xjy2 y（5-52）分类界面方程变为:N * _*ai yiK x

15、, x 】- b =0i 1分类判断函数变为：N N)一一.一 *_ _. _ *f (x) =sgn 工 a yiK (x,x)+b【yJ利用特征影射进行分类的结构如图 9所示。（5-53）（5-54）N-*sgn Z a yK（x,x）+b.i TXix29xn（）（O）图9支持向量机计算示意图目前，常用的核函数有以下三种：多项式型核函数：qK(x,Xj ) = (x Xj ) + 1)(5-55)径向基型核函数：lx _Xi|2K(x,x )=exp(5-56)S型核函数：K (x, xi ) = tanh(a (xi x)+P)(5-57)Matlab工具箱中没有 SVM!数，但可以嵌

16、入第三方的函数，如LS-SVMlab1.5、osu_svm3.00等。10第三节 无监督的聚类方法有监督的分类通常由教师预先定义好了类别数和各类别的样本，用于训练分类器，以便对新样本分类。但在很多情况下很难由教师预先定义好类别数并对部分样本分好类，需要根据集合中所有样本的特征进行自动聚类，如图象中的颜色主色调提取、文本中关键词提取等。图10层次聚类的例子图10二维聚类的两个例子聚类是一个将对象集合自动分组的过程。聚类的方法主要包括两类：层次聚类法、分割聚类法。层次聚类法按层次将对象集合分类，得到一个嵌套的聚类结构，包括系统聚类法、传递闭包法、最大 数法、传递法等。分割聚类法将所有样本分割成不同

17、的类别，包括动态聚类法、自组织神经网络聚类 法等。4.3.1层次聚类方法层次聚类就是把各种事物按其相似性或内 在联系组织起来，按不同的相似度分成不同类别 的聚类，组成有层次的结构。层次聚类的算法比较简单。先把性质最接 近的事物划归一类，然后再把相近的几类合并， 形成树状结构的层次分类，如图 10。两个类X与Y之间的距离用 A(X ,Y )表示。X(Y, Y X以下几种量度方法：(1)最近距离X,Y =mip (x, y)y Y(2)最远距离X，Y =%x (x，y)y y(3) Haussdorff 距离11哨X啜”x, y)(4)均值距离X,Y = (mx,my)其中mx,my是两个类的质心

18、，6(,)可以是任何一种距离度量。采用不同的距离量度方法会得到 不同的聚类效果。在确定了距离度量方法后，分级聚类算法可以按以下步骤进行：(1)初始时每个样本自成一类，用 为。=1,2, I，N )表示，N是样本数。(2)找最近的一类对Xi，yj,满足(Xi，y) = mjn (乂4v)。将其合并。(3)若仅为1类，则终止，否则转向步骤 1。4.3.2动态聚类方法分割聚类法是将样本集划分成一定数量的子集，要解决的关键问题是 ：(a)将样本集划分多少类好 ？(b)已知划分类的数目后，如何进行最佳划分？动态聚类方法是一个动态的迭代过程，一般需要有以下几个要点：(1)选定某种距离度量方法作为样本间的相

19、似性度量；(2)确定合理的初始样本分类，包括代表点的选择、初始的分类方法选择等；(3)确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。C-均值算法和ISODATA#法是两种常用的动态聚类算法。1. C-均值算法C-均值聚类算法的步骤：(1)选取聚类数k；(2)从训练集中任意取定 k个向量4,02,111,7作为聚类中心；(3)将每个样本向量 xi = xi,xi2,HI,xJT (n为输入向量的维数)，按欧氏距离最近划归中心 为 q 的类中。| xl -ci | =mjn | xl - cj | ;(4)重新调整聚类中心c。令G =【Ci1,C2,IM ,Cin，

20、其中Gm由下式计算得出：xiimxh - CiCim 一Ni其中Ni是第i个聚类块中的样本数。(5)如果步骤(4)中的聚类中心(c,i =1,2, III,k )不再变化，则停止，否则转步骤(3)。C-均值聚类的结果可以采用下面的目标函数评价：12其中G是中心为g的聚类块。123456789 10 Cc-均值算法都是在类别数已知的条件下进行的。在类 别数未知情况下使用 c均值算法时，可以假设类别数是逐 步增加的，例如对 k=1, 2, 3,分别使用该算法。显然 准则函数J是随k的增加而单调地减少的。 如果样本集的合 理聚类数为k类，当类别数继续增大时， 相当于将聚类很好 的类别又分成子类，则J

21、值虽然继续减少但会呈现平缓趋势， 如图11。图中拐点对应的类别数就比较接近于最优聚类数， 是较合适的聚类数。但是并非所有的情况都能找到明显的转折点。在无明显 的转折点时，这种选择最佳分类数的方法将失效。一般需要图11聚类数目对目标函数的影响利用先验知识对不同的聚类结果进行分析比较。Matlab中C-均值算法函数为 KMEANS 2. ISODAT期法C-均值算法简单，但自我调整能力差，主要表现在类别数不能改变，受初始聚类中心影响较大。ISODATA算法与C-均值算法相比，具有以下改进：.考虑了类别的合并与分裂，具有自我调整类别数的能力。合并主要发生在类内样本个数太少或两类聚类中心之间距离太小的

22、情况。为此，设有最小类内样本数限制N ,以及类间中心最小距离参数C。若出现两类聚类中心距离小于C的情况，可考虑将此两类合并。分裂主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数S,用以决定是否需要将某一类分裂成两类。.因具有自我调整的能力， 需要设置若干个控制用参数，如聚类数期望值 K、每次迭代允许合并的最大聚类对数L和允许迭代次数I等。ISODATAB法的步骤：(1)确定控制参数及初始聚类中心 需确定的控制参数： K :聚类期望数目； N: 一个聚类中的最少样本数； S：分量标准偏差控制参数，用于控制分裂； C :

23、类间最小距离控制参数，用于控制合并； L：每次迭代允许合并的最大聚类对数； I :允许迭代的次数。设初始聚类数目为k,聚类中心为 mi, i =1,2,111,ko(2)分类对所有样本，按给定的 k个聚类中心，以最小距离进行分类，即:若 |y-mj 卜 |y-m|，i =1,2,川，k , i = j ,则 y w c(3)取消类内样本数过小的类13若有任何一个类c j ,其样本数Nj N ,则取消q。令k = k -1 ,将q中的原样本按近邻法划归为其它类；(4)调整聚类中心重新调整聚类中心：1，mjy j =1, 2| k,(5-19)Nj y cj(5)计算类内平均距离每类样本距离其聚类中心的平均距离：1Djy-mj j =1, 2|l k,(5-20)N j y cj(6)计算类间平均距离所有样本距离其聚类中心的平均距离：k Du% Nj Dj(5-21)N j4 j(7)分裂或合并 K 如果k W 一,则转向步骤8,执行分裂步骤；2如果k之2K ,则转向步骤11,执行合并步骤，否则转向步骤 8,执行分裂步骤。(8)计