《模式识别与MATLAB》PPT课件.ppt

1、模式识别与MATLAB,-信息0603 康叶,主讲内容,Fisher算法及MATLAB实现,Svm（support vector machine）与优化,通过MATLAB编程进一步熟悉一下模式识别中的一些典型算法,典型算法,聚类算法： 1、 层次聚类 2、划分聚类,分类器算法 3、线性判别函数 4、 Bayes算法,W2,W1,W3,L1,L3,L2,1、 层次聚类,单连接算法 第一步：将n个样本分配到n个簇中，计算距离矩阵； 第二步：计算最新距离矩阵，将拥有最小簇间距离的两个簇合并，得到新簇集合； 第三步：若簇数大于1，重复第二步；若为1，则结束。,Matlab 代码,样本： x 数据标准化

2、 ：xn=zscore(x) 计算样本间距离：Y=pdist(xn,distance) 距离矩阵：squareform（y) 调用z=linkage（y,method） dendrogram(z)生成层次图 调用T=cluster（z，c）对样本进行分类,Distance: Euclid：欧拉距离 Hamming:汉明距离 Function：DISTFUN,Y = (1:6) X = 0 1 2 3 1 0 4 5 2 4 0 6 3 5 6 0, squareform(Y) = X, squareform(X) =Y.,Method Single：最小距离 Complete：最大距离 Ave

3、rage、weighted：平均距离 Centroid、median：重心法,Example：,clear X=5.80 90.59 7.44 67.14 8.11 65.48 10.21 58.88 9.51 59.24 9.81 60.47; Xn=zscore(X); Y=pdist(Xn,euclid) squareform(Y) figure Z=linkage(Y,centroid); dendrogram(Z); T=cluster(Z,3),Clusterdata,k-均值(k-means)算法 给定k，算法的处理流程如下: 第一步：随机的把所有对象分配到k个非空的簇中； 第二

4、步：计算每个簇的平均值，并用该平均值代表相应的簇中心； 第三步：将每个对象根据其与各个簇中心的距离，重新分配到与它距离最近的簇中； 第四步：重复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 =

5、 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个特征为： 判别函数： 判别条件：,g1(x) g2(x) 和 g1(x) g3(x),实现步骤 第一步：初始化各权值矢量W=0； 第二步：将所有样本x（k）进行计算，求的g(x(k)； 第三步：若x （k）判断gi （k）是不是最大值，若是，权值不用修改；否则权值需修正 ；W + x （k）,Wj - x

6、 （k） 第四步：重复2,3直到权值不再修正。 第五步：求的gij = gi-gj,Matlab 代码,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类。统计资料表明人们患癌的概率 ，从而

7、 。设有一种诊断此病的试验，其结果有阳性反应和阴性反应之分，依其作诊断。化验结果是一维离散模式特征。统计资料表明：癌症者有阳性反映的概率为0.95即 ，从而可知 ，正常人阳性反映的概率为0.01即 , 可知 。,4、 Bayes算法,对于两类1， 2问题，直观地，可以根据后验概率做判决：,随机模式分类识别，通常称为Bayes(贝叶斯)判决。,主要依据类的概率、概密，按照某种准则使分类结果从统计上讲是最佳的。准则函数不同，所导出的判决规则就不同，分类结果也不同。,将P(i|x)代入判别式，判别规则可表示为,根据Bayes公式，后验概率 可由类i的先验概率P(i)和条件概率密度 来表示，即,最小误

8、判概率准则下的判决规则：,如果 则判,另一个等价形式是： 如果 则判,由贝叶斯定理,对于多类问题，最小误判概率准则有如下几种等价的判决规则:,实现步骤,1、先验概率： 2、类概率： 3、后验概率： 4、判别：,Fisher算法,二维模式向一维空间投影示意图,o,x,y,o,y,x,映射Y空间 Y=WTX-W0 0 X 1 Y=WTX-W0 0 X2 把X空间各点投影到Y空间得一直线上，维数由2维降为一维。若适当选择W的方向，可以使二类分开。下面我们从数学上寻找最好的投影方向，即寻找最好的变换向量W的问题。,w(y),w,y1,y2,x2,x1,1,2,投影样本之间的分离性用投影样本之差表示 投

9、影样本类内离散度:,i=1,2,i=1,2,类间散布矩阵,上式就是n维x空间向一维y空间的最好投影方向， 它实际是多维空间向一维空间的一种映射。,其中Sw为类内散布矩阵, Sb为类间散布矩阵,现在我们已把一个n维的问题转化为一维的问题。 现在一维空间设计 Fisher分类器: W0的选择,Yki表示第i类中第k个样本的投影值 N1为1样本数 N2为2样本数 当W0选定后，对任一样本X，只要判断Y=WTX W0 则X1; Y=WTX W0 则X2。分类问题就解决了,实现步骤 第一步：把来自两类1 / 2的训练样本集X分成与1对应的子集X1和与X2对应的子集； 第二步：由 计算xi ； 第三步：由

10、 计算各类的类内离差阵S1 ， S2 第四步：计算类内总离差阵Sw = S1 + S2 第五步：计算的 逆矩阵 第六步 ：按 求解W,第七步： 第八步： 第九步：对未知模式x判定模式类,Svm（support vector machine）与优化,首先看一下它处理分类问题的情况：,判别函数,判别准则,核函数,解决线性不可分问题：,低维空间的 线性不可分,非线性转换,高维空间的 线性可分,由于维数是升高，很大程度上增大了计算量，所以引进多项式内积核函数。,线性核函数（linear）,高斯径向基核函数 （rbf）,D阶（非）齐次多项式核函数（poly）,指数型径向基核函数（erfb）,example:,线性判别：,二阶多项式判别：,clear load lineardata c=100;ker=linear; nsv,alpha,