模式识别与MATLAB

模式识别与MATLAB---信息0603康叶主讲内容•Fisher算法及MATLAB实现•Svm（supportvectormachine）与优化•通过MATLAB编程进一步熟悉一下模式识别中的一些典型算法典型算法•聚类算法：1、层次聚类2、划分聚类•分类器算法3、线性判别函数4、Bayes算法L1L3L2P(x/w1)p(w1)P(x/w2)p(w2)tΩ1Ω2P(w2)ε21P(w1)ε12x1、层次聚类•单连接算法第一步：将n个样本分配到n个簇中，计算距离矩阵；第二步：计算最新距离矩阵，将拥有最小簇间距离的两个簇合并，得到新簇集合；第三步：若簇数大于1，重复第二步；若为1，则结束。Matlab代码•样本：x•数据标准化：xn=zscore(x)•计算样本间距离：Y=pdist(xn,distance)距离矩阵：squareform（y)•调用z=linkage（y,method）dendrogram(z)生成层次图•调用T=cluster（z，c）对样本进行分类Distance:Euclid：欧拉距离Hamming:汉明距离Function：@DISTFUNY=(1:6)X=[0123104524063560],squareform(Y)=X,squareform(X)=Y.MethodSingle：最小距离Complete：最大距离Average、weighted：平均距离Centroid、median：重心法•Example：出生死亡率（‰）平均寿命满族5.870.59朝鲜族7.4467.14蒙古族8.1167.14维吾尔族10.2158.88藏族9.5159.24哈萨克族9.8160.47clearX=[5.8090.597.4467.148.1165.4810.2158.889.5159.249.8160.47];Xn=zscore(X);Y=pdist(Xn,'euclid‘)squareform(Y)figureZ=linkage(Y,'centroid‘);dendrogram(Z);T=cluster(Z,3)Clusterdata•k-均值(k-means)算法给定k，算法的处理流程如下:第一步：随机的把所有对象分配到k个非空的簇中；第二步：计算每个簇的平均值，并用该平均值代表相应的簇中心；第三步：将每个对象根据其与各个簇中心的距离，重新分配到与它距离最近的簇中；第四步：重复2,3直到k个簇的中心点不再发生变化或准则函数Je收敛。2、划分聚类Matlab代码•直接调用库函数kmeans（）[IDX,C,SUMD,D]=KMEANS(X,K,‘PARAM1’,val1,‘PARAM2’,val2,...)'Distance''Start''Replicates''Display'Example:X=[randn(20,2)+ones(20,2);randn(20,2)-ones(20,2)];[cidx,ctrs]=kmeans(X,2,'dist','city','rep',5,'disp','final');plot(X(cidx==1,1),X(cidx==1,2),'r.',...X(cidx==2,1),X(cidx==2,2),'b.',ctrs(:,1),ctrs(:,2),'kx');3、线性判别函数现抽取n个特征为：判别函数：判别条件：TxxxxX),...,,(n32112211......)(nnnwxwxwxwxgg1(x)g2(x)和g1(x)g3(x)•实现步骤第一步：初始化各权值矢量W=0；第二步：将所有样本x（k）进行计算，求的g(x(k))；第三步：若x（k）∈ω判断gi（k）是不是最大值，若是，权值不用修改；否则权值需修正；W+x（k）,Wj-x（k）第四步：重复2,3直到权值不再修正。第五步：求的gij=gi-gjMatlab代码•g=sample(i,:)*w;•length(find(d==max(d)))~=1||find(d==max(d))~=y(i);%判断是否是最大值•w=w+sample(i,:)‘*[2*(y(i)==1)-1,2*(y(i)==2)-1,2*(y(i)==3)-1];%修正权值•flag=1;%设标志位•w=[w(:,1)-w(:,2),w(:,2)-w(:,3),w(:,3)-w(:,1)];%求的gij例：对一批人进行癌症普查，患癌症者定为属1类，正常者定为属2类。统计资料表明人们患癌的概率，从而。设有一种诊断此病的试验，其结果有阳性反应和阴性反应之分，依其作诊断。化验结果是一维离散模式特征。统计资料表明：癌症者有阳性反映的概率为0.95即，从而可知，正常人阳性反映的概率为0.01即,可知。005.0)(1P995.0)(2P95.0)(1阳xP05.0)(1阴xP01.0)(2阳xP99.0)(2阴xP4、Bayes算法对于两类1，2问题，直观地，可以根据后验概率做判决：121122(|)(|)(|)(|)pωxpωxxpωxpωxx若则若则随机模式分类识别，通常称为Bayes(贝叶斯)判决。主要依据类的概率、概密，按照某种准则使分类结果从统计上讲是最佳的。准则函数不同，所导出的判决规则就不同，分类结果也不同。将P(i|x)代入判别式，判别规则可表示为1122111222(|)()(|)()(|)()(|)()pxωPpxωPxpxωPpxωPx若则若则根据Bayes公式，后验概率可由类i的先验概率P(i)和条件概率密度来表示，即(/)ipx(/)ipx21(|)()(|)()(|)()(|)()iiiiiiiipxPpxPpxpxpxP最小误判概率准则下的判决规则：•如果•则判)()(11xpP)()(22xpP21x)(1xP)(2xP21x另一个等价形式是：如果则判由贝叶斯定理)()()()(iiixpPxPxp对于多类问题，最小误判概率准则有如下几种等价的判决规则:⑵若，则判⑴若，，则判)()(xPxPjiijix)(xPi)(maxxPjjix（后验概率形式）⑶若，，则判⑷若，则判（条件概率形式）)()()()(jjiiPxpPxpijix)()(iiPxp)()(maxjjjPxpix实现步骤•1、先验概率：•2、类概率：•3、后验概率：•4、判别：)/(ixP)(iP)/(xPiFisher算法二维模式向一维空间投影示意图tyoxyoyx映射Y空间Y=WTX-W00X∈ω1Y=WTX-W00X∈ω2把X空间各点投影到Y空间得一直线上，维数由2维降为一维。若适当选择W的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向量W的问题。w(y)wy1y2x2x1ω1ω2投影样本之间的分离性用投影样本之差表示投影样本类内离散度:XXNXNyYYNYYiiiiiiWW11TT空间的投影均值在NxiiiXNxX1空间的均值：在11WYXT22WYXT类间分离性越大越好|)(|||2121XXWYYTWSWNXXTXTyYYYiTiiiiiWW222WSWT121WSWT222i=1,2i=1,2iTiiiXXNXXXS其中2222NXXXXXST1111NXXXXXST2212212||)(YYWJFisher准则函数有所以WSWXWTXWTYYWJbT212212)(的分子2121XXXXSTb其中WSWWSWWSWWJwTTT212212)(的分母小越好。投影样本的总离散度越）来表示，要求用（投影样本总的离散度可2212类间散布矩阵SSSw21上式就是n维x空间向一维y空间的最好投影方向，它实际是多维空间向一维空间的一种映射。XXSWWJw211)(求极值得对WSWWSW)(wTbTWJ所以其中Sw为类内散布矩阵,Sb为类间散布矩阵现在我们已把一个n维的问题转化为一维的问题。现在一维空间设计Fisher分类器:W0的选择2010XWXWYXWXWYTT2.1210YYW2121212102122.2NNXWNXWNNNYNYNWTTYki表示第i类中第k个样本的投影值N1为ω1样本数N2为ω2样本数当W0选定后，对任一样本X，只要判断Y=WTXW0则X∈ω1;Y=WTXW0则X∈ω2。分类问题就解决了NYYNYYNYYYYYWkkkkkk2211111211221121120)(.3NxiiiXNx1•实现步骤第一步：把来自两类ω1/ω2的训练样本集X分成与ω1对应的子集X1和与X2对应的子集；第二步：由计算xi；第三步：由计算各类的类内离差阵S1，S2第四步：计算类内总离差阵Sw=S1+S2第五步：计算的逆矩阵第六步：按求解W1SXXSWw211iTiiiXXNXXXSS第七步：第八步：第九步：对未知模式x判定模式类XXNXNyYYNYiiiiiiWW11TT2210YYW2010XWXWYXWXWYTTSvm（supportvectormachine）与优化•首先看一下它处理分类问题的情况：12211......)(nnnwxwxwxwxg1)(xgijiwxxgxg其中)()(判别函数判别准则bxwxg)(核函数•解决线性不可分问题：低维空间的线性不可分非线性转换高维空间的线性可分由于维数是升高，很大程度上增大了计算量，所以引进多项式内积核函数。diidiixxxxKxxxxK)(),(]1)[(),(和)||||exp(),(2iixxxxK)||||exp(),(22iixxxxK)(),(iixxxxK线性核函数（linear）高斯径向基核函数（rbf）D阶（非）齐次多项式核函数（poly）指数型径向基核函数（erfb）example:线性判别：二阶多项式判别：clearloadlineardatac=100;ker='linear';[nsv,alpha,bias]=svc(x,y,c)svcplot(x,y,ker,alpha,bias);clearloadiris2%poly2c=inf;ker='poly';globalp1p1=2;[nsv,alpha,bias]=svc(x,y,ker,c)svcplot(x,y,ker,alpha,bias);