§2-1判別函數§2-2線性判別函數§2-3線性判別函數的性質§2-4廣義線性判別函數§2-5非線性判別函數第二章

判別函數2023/2/4湖南大學電氣與信息工程學院*假設對一模式X已抽取n個特征，表示為：模式識別問題就是根據模式X的n個特征來判別模式屬于ω1,ω2,

…,

ωm

類中的那一類。§2-1判別函數

2023/2/4湖南大學電氣與信息工程學院*例如下圖：三類的分類問題，它們的邊界線就是一個判別函數§2.1判別函數（續)2023/2/4湖南大學電氣與信息工程學院*判別函數包含兩類：一類是線性判別函數：線性判別函數廣義線性判別函數所謂廣義線性判別函數就是把非線性判別函數映射到另外一個空間變成線性判別函數分段線性判別函數另一類是非線性判別函數§2.1判別函數（續）2023/2/4湖南大學電氣與信息工程學院*§2-2線性判別函數我們現在對兩類問題和多類問題分別進行討論。(一)兩類問題即:

1.二維情況：取兩個特征向量這種情況下判別函數:2023/2/4湖南大學電氣與信息工程學院*在兩類別情況，判別函數g

(x)

具有以下性質：這是二維情況下判別由判別邊界分類.情況如圖：1.二維情況2023/2/4湖南大學電氣與信息工程學院*2.n維情況現抽取n個特征為：判別函數：

另外一種表示方法：2023/2/4湖南大學電氣與信息工程學院*模式分類：當g1(x)=WTX=0為判別邊界。當n=2時，二維情況的判別邊界為一直線。當n=3時，判別邊界為一平面，n>3時，則判別邊界為一超平面。2.n維情況2023/2/4湖南大學電氣與信息工程學院*(二)

多類問題對于多類問題，模式有ω1,ω2,

…,

ωm

個類別。可分三種情況：1.第一種情況：每一模式類與其它模式類間可用單個判別平面把一個類分開。這種情況，M類可有M個判別函數，且具有以下性質：2023/2/4湖南大學電氣與信息工程學院*右圖所示，每一類別可用單個判別邊界與其它類別相分開。如果一模式X屬于ω1，則由圖可清楚看出:這時g1(x)>0而g2(x)<0

，g3(x)<0

。ω1

類與其它類之間的邊界由g1(x)=0確定.1.第一種情況2023/2/4湖南大學電氣與信息工程學院*例：已知三類ω1,ω2,ω3的判別函數分別為：因此三個判別邊界為：1.第一種情況（續）2023/2/4湖南大學電氣與信息工程學院*作圖如下：1.第一種情況（續）2023/2/4湖南大學電氣與信息工程學院*對于任一模式X如果它的g1(x)>0，g2(x)<0，g3(x)<0則該模式屬于ω1類。相應ω1類的區域由直線-x2+1=0

的正邊、直線-x1+x2-5=0

和直線-x1+x2=0的負邊來確定。1.第一種情況（續）2023/2/4湖南大學電氣與信息工程學院*必須指出，如果某個X使二個以上的判別函數gi(x)>0。則此模式X就無法作出確切的判決。如圖中

IR1,IR3，IR4區域。另一種情況是IR2區域，判別函數都為負值。IR1，IR2，IR3，IR4。都為不確定區域。1.第一種情況（續）2023/2/4湖南大學電氣與信息工程學院*問當x=(x1,x2)T=(6,5)T時屬于那一類結論：g1(x)<0，g2(x)>0，g3(x)<0所以它屬于ω2類1.第一種情況（續）2023/2/4湖南大學電氣與信息工程學院*這樣有M(M_1)/2個判別平面。對于兩類問題，M=2，則有一個判別平面。同理，三類問題則有三個判別平面。

判別函數：判別邊界：判別條件：2.第二種情況每個模式類和其它模式類間可分別用判別平面分開。2023/2/4湖南大學電氣與信息工程學院*判別函數性質：假設判別函數為：判別邊界為：2.第二種情況（續）用方程式作圖：2023/2/4湖南大學電氣與信息工程學院*問:未知模式X=(x1,x2)T=(4,3)T屬于那一類代入判別函數可得:把下標對換可得:因為結論：所以X屬于ω3類結論：判別區間增大，不確定區間減小，比第一種情況小的多.2.第二種情況（續）2023/2/4湖南大學電氣與信息工程學院*3.第三種情況判別函數：

判別規則：判別邊界：gi(x)=gj(x)

或gi(x)-gj(x)

=0就是說，要判別模式X屬于那一類，先把X代入M個判別函數中，判別函數最大的那個類別就是X所屬類別。類與類之間的邊界可由gi(x)=gj(x)

或gi(x)-gj(x)

=0來確定。每類都有一個判別函數,存在M個判別函數2023/2/4湖南大學電氣與信息工程學院*右圖所示是M=3的例子。對于ω1類模式，必然滿足g1(x)>g2(x)

和g1(x)>g3(x)

。假設判別函數為：則判別邊界為：3.第三種情況（續）2023/2/4湖南大學電氣與信息工程學院*結論：不確定區間沒有了，所以這種是最好情況。用上列方程組作圖如下：3.第三種情況（續）2023/2/4湖南大學電氣與信息工程學院*問假設未知模式x=(x1,x2)T=(1,1)T

，則x屬于那一類。把它代入判別函數：得判別函數為：因為所以模式x=(1,1)T屬于類。3.第三種情況（續）2023/2/4湖南大學電氣與信息工程學院*§2-3線性判別函數的性質1.模式空間與加權空間模式空間：由構成的n維歐氏空間。W是此空間的加權向量，它決定模式的分界面H，W與H正交。加權空間：以為變量構成的歐氏空間模式空間與加權空間的幾何表示如下圖：2023/2/4湖南大學電氣與信息工程學院*模式空間2023/2/4湖南大學電氣與信息工程學院*2023/2/4湖南大學電氣與信息工程學院*1.模式空間與加權空間（續）2023/2/4湖南大學電氣與信息工程學院*該式表示一個通過加權空間原點的平面，此平面就是加權空間圖中的平面①,同樣令g

(x2)=g

(x3)=g

(x4)=0，分別作出通過加權空間原點的平面②③④圖中用陰影表示的部分是各平面的正側。加權空間的構造：設是加權空間分界面上的一點，代入上式得：1.模式空間與加權空間2023/2/4湖南大學電氣與信息工程學院*這是一個不等式方程組，它的解處于由ω1類所有模式決定的平面的正邊和由ω2類所有模式決定的平面的負邊，它的解區即為凸多面錐。如圖所示：(b)為加權空間，（c）為正規化后的加權空間。由上可以得到結論：加權空間的所有分界面都通過坐標原點。這是加權空間的性質。為了更清楚，下面用二維權空間來表示解向量和解區。1.模式空間與加權空間（續）2023/2/4湖南大學電氣與信息工程學院*在三維空間里，令w3

=0

則為二維權空間。如圖：給定一個模式X，就決定一條直線：即分界面H，W與H正交，W稱為解向量。解向量的變動范圍稱為解區。因x1,x2∈ω1，x3,x4∈ω2由圖可見x1,x3離的最近，所以分界面H可以是x1,x3之間的任一直線，由垂直于這些直線的W就構成解區，解區為一扇形平面，即陰影區域。如右圖:2.解向量和解區2023/2/4湖南大學電氣與信息工程學院*把不等式方程正規化：正規化：2.解向量的解區（續）2023/2/4湖南大學電氣與信息工程學院*g(x)=WTX=0決定一個決策界面，當g(x)為線性時，這個決策界面便是一個超平面H，并有以下性質：性質①：W與H正交（如圖所示）假設x1,x2是H上的兩個向量所以W

與(x1-x2)

垂直，即W與H正交。一般說，超平面H把特征空間分成兩個半空間。即Ω1,Ω2空間，當x在Ω1空間時g(x)>0,W指向Ω1，為H的正側，反之為H的負側.3.超平面的幾何性質2023/2/4湖南大學電氣與信息工程學院*Ω1Ω2g(x)>0g(x)<03.超平面的幾何性質2023/2/4湖南大學電氣與信息工程學院*矢量到H的正交投影與值成正比其中：x

p：x在H

的投影向量，r是x

到H

的垂直距離。是W方向的單位向量。3.超平面的幾何性質（續）性質②：2023/2/4湖南大學電氣與信息工程學院*另一方面:3.超平面的幾何性質（續）這是超平面的第二個性質，矢量x到超平面的正交投影正比與g(x)的函數值。2023/2/4湖南大學電氣與信息工程學院*性質③：3.超平面的幾何性質（續）2023/2/4湖南大學電氣與信息工程學院*性質④：3.超平面的幾何性質（續）2023/2/4湖南大學電氣與信息工程學院*一組模式樣本不一定是線性可分的，所以需要研究線性分類能力的方法，對任何容量為N的樣本集，線性可分的概率多大呢？（如下圖（a），線性不可分）例：4個樣本有幾種分法。圖（b）①直線把x1分開，每條直線可把4個樣本分成ω1

ω2

類，4個樣本分成二類的總的可能的分法為24=16類，其中有二種是不能用線性分類實現的線性可分的是14。即概率為14/16。4.二分法能力（a）x1x2x3x4⑥

③

②

④

⑤

⑦

（b）2023/2/4湖南大學電氣與信息工程學院*結論：N個樣品線性可分數目(條件：樣本分布良好）：4.二分法能力（續）對N和n各種組合的D(N,n)值，表示在下表中，從表中可看出，當N，n緩慢增加時D(N,n)卻增加很快。2023/2/4湖南大學電氣與信息工程學院*12345612222222444444368888848141616161651022303232324.二分法能力（續）線性可分概率：2023/2/4湖南大學電氣與信息工程學院*把上式用曲線表示成下圖：圖中橫坐標用λ=N/n+1表示。由圖討論：4.二分法能力（續）2023/2/4湖南大學電氣與信息工程學院*結論：在實際工作中，分類的訓練非常重要，由已知樣本來訓練。因為已知樣本有限，而未知樣本無限。選擇已知類別的訓練樣本數方法如下：4.二分法能力（續）2023/2/4湖南大學電氣與信息工程學院*①：如果訓練樣本N

<N0，設計分類器的分類能力太差，因為訓練樣本太少。②：如果訓練樣本N太多時，則樣本太多，運算量、存儲量太大。③：因此實際工作中應該取：②4.二分法能力（續）2023/2/4湖南大學電氣與信息工程學院*§2-4廣義線性判別函數這樣一個非線性判別函數通過映射，變換成線性判別函數。判別函數的一般形式：2023/2/4湖南大學電氣與信息工程學院*§2-4廣義線性判別函數（續）例：如右圖。2023/2/4湖南大學電氣與信息工程學院*§2-4廣義線性判別函數（續）要用二次判別函數才可把二類分開：ω2ω1ω22023/2/4湖南大學電氣與信息工程學院*§2-4廣義線性判別函數（續）從圖可以看出：在陰影上面是ω1類，在陰影下面是ω2類，結論：在X空間的非線性判別函數通過變換到Y空間成為線性的，但X變為高維空間ω2ω1ω22023/2/4湖南大學電氣與信息工程學院*1.分段線性判別函數（用線性無法分開,可用分段線性判別函數）

①、基于距離的分段線性判別函數。（用均值代表一類，通過均值連線中點的垂直線分開）把ωi類可以分成li個子類:∴分成l個子類。現在定義子類判別函數：在同類的子類中找最近的均值。判別規則：這是在M類中找最近均值。則把x歸于ωj類完成分類。§2-5非線性判別函數Ⅱ

Ⅲ

2023/2/4湖南大學電氣與信息工程學院*§2-5非線性判別函數（續）例：未知x,如圖：先與ω1類各子類的均值比較，即，找一個最近的與ω2各子類均值比較取最近的因g2(x)<g1(x)，所以x∈ω2類。2023/2/4湖南大學電氣與信息工程學院*設ω＝ω1,

ω2

,……ωm而每一類又可以分為子類。對每個子類定義一個線性判別函數為：則定義ωi類的線性判別函數為：②、基于函數的分段線性判別函數利用均值代表一類有時有局限性，如圖所示。若用線性判別函數代表一類，就會克服上述情況。1.分段線性判別函數2023/2/4湖南大學電氣與信息工程學院*在各子類中找最大的判別函數作為此類的代表，則對于M類，可定義M個判別函數gi(x),i=1,2,…..M,因此，決策規則：對未知模式x，把x先代入每類的各子類的判別函數中，找出一個最大的子類判別函數，M類有M個最大子類判別函數，在M個子類最大判別函數中，再找一個最大的，則x就屬于最大的子類判別函數所屬的那一類。1.分段線性判別函數（續）2023/2/4湖南大學電氣與信息工程學院*③、基于凹函數的并分段線性判別函數（針對多峰情況）設li子類判別函數，i=1,2,…..r則分段線性判別函數有如下特性：1.分段線性判別函數（續）(a)：l1,l2,……lr都是分段線性判別函數(b)：