王秀平-數(shù)據(jù)挖掘復(fù)習(xí)

算法K-近鄰分類算法輸入：訓(xùn)練數(shù)據(jù)X；

近鄰數(shù)目K；

待分類的元組t。輸出：

輸出類別c。（1）N=

；（

2）

FOR

each

d∈X

DO

BEGIN（

3）

IF

||N||<K

THEN（

4）N=N

∪t7rvbpv；（

5

）

ELSE（

6）IF

u

∈Nsuch

that

sim(t，

u)<sim(t，

d)

THEN

BEGIN（

7）

N=N

-{u}；（

8）

N=N

∪d9vvnjv；（

9）

END（10

）END（

11）

c=class

to

which

the

most

u

∈N.K-近鄰分類算法（KNearestNeighbors

，

簡稱KNN）通過計算每個訓(xùn)練數(shù)據(jù)到待分類元組的距離

，

取和待分類元組距離最近的K個訓(xùn)練數(shù)據(jù)

，

K個數(shù)據(jù)中哪個類別的訓(xùn)練數(shù)據(jù)占多數(shù)

，

則待分類元組就屬于哪個類別。K-近鄰分類算法1、定義的直觀形式:?找出與目標(biāo)最接近的K個樣本；?將目標(biāo)劃分到找出的K個樣本中出現(xiàn)最頻繁的類。2、K的直觀形式:?以目標(biāo)樣本為中心；?劃出一個剛好包含K個樣本的圓；?當(dāng)K增大時，圓半徑增大。KNN的直觀解釋k近鄰算法K近鄰設(shè)有N個樣本分布到c個類為1，…,i，…本例的k1=4，k2=0，k3=1c，每類有Ni個樣本，i=1…c。在全部樣本找出k個最近距離的近鄰。k個近鄰分布于c個類中數(shù)目用ki表示。k近鄰的判斷函數(shù)為:決策規(guī)則如果如圖所示例子中k1=4,所以j=1,。那么決策為k2=0,k3=1,k近鄰法x

eoj遺傳算法的生物學(xué)基礎(chǔ)生物進(jìn)化理論與遺傳學(xué)現(xiàn)代綜合進(jìn)化論1.生物的進(jìn)化實際上是種群的進(jìn)化2.每一代個體基因型的改變會影響種群基因庫的組成3.種群基因庫的進(jìn)化就是種群的進(jìn)化沒有所謂生存斗爭的問題,單是個體繁殖機(jī)會的差異也能造成后代基因庫組成的改變,自然選擇也能夠進(jìn)行 基因庫+適者繁殖=群體進(jìn)化編碼:從問題域到遺傳域的映射。即性狀與基因的DNA序列的映射解碼:從遺傳域到問題域的映射。即將DNA序列解釋成個體的性狀適應(yīng)度:種群的某個個體對生存環(huán)境的適應(yīng)程度。適應(yīng)度高的個體可以獲得更多的繁殖機(jī)會，而適應(yīng)度低的個體，其繁殖機(jī)會就會比較少，甚至逐漸滅絕選擇:以一定概率從種群中選擇若干個體的操作。一般而言，選擇就是基于適應(yīng)度的優(yōu)勝劣汰的過程交叉:有性生殖生物在繁殖下一時兩個同源染色體之間通過交叉而重組，即在兩個染色體的相同位置處DNA被切斷，前后兩串分別交叉組合形成新的染色體遺傳算法的基本術(shù)語遺傳算法的基本思想解碼編碼遺傳算法的流程圖遺傳算法基本要素與實現(xiàn)技術(shù)遺傳域（基因空間）優(yōu)化變量的代碼表示二進(jìn)制編碼浮點數(shù)編碼

符號編碼問題域（解空間）

映射優(yōu)化變量

─一編碼與解碼二進(jìn)制編碼二進(jìn)制編碼是遺傳算法中最常用、最原始的一種編碼方法,它將原問題的解空間映射到二進(jìn)制空間上,然后進(jìn)行遺傳操作。找到最優(yōu)個體后再通過解碼過程還原原始的數(shù)據(jù)形式進(jìn)行適應(yīng)度評價二進(jìn)制編碼的串長度取決于求解的精度編碼公式解碼公式

編碼與解碼浮點編碼個體的基因值用某一范圍內(nèi)決策變量的一個浮點數(shù)來表示,個體的編碼長度等于其決策變量的個數(shù)。浮點編碼使用的是決策變量的真實值某個優(yōu)化問題含有6個變量,則它的一個基因表達(dá)為對應(yīng)的表現(xiàn)型為x=

[2

.50,9

.54,3

.25,0

.25,4

.25,7

.00]編碼與解碼2.509.543.250.254.257.00X

:符號編碼個體基因值取自一個無數(shù)值含意,而只有代碼含義的符號集。符號集可以是字母,也可以是數(shù)字序號。如血型A,B,AB,O可以分別用[a,b,c,d]表示,或者[a1,a2,a3,a4],也可表示為[1,2,3,4]編碼與解碼二進(jìn)制編碼染色體的交叉單點交叉基因位數(shù)為,交叉點k的范圍為[1,-1],在該點為分界相互交換變量子個體1011

1

0

1

0

0

1

0

1子個體2

1

0

1

0

1

0

1

1

0

1

0例如:二進(jìn)制編碼染色體的交叉多點交叉的破壞性可以促進(jìn)解空間的搜索多點交叉二進(jìn)制編碼染色體的交叉均勻交叉兩個配對個體的染色體每個基因位以相同的交叉概率進(jìn)行

交換具體步驟。隨機(jī)產(chǎn)生一個與個體編碼串長度等長的屏蔽字W

=

。按下列規(guī)則交叉兩個父本的基因若=0,則父代第i個基因相互交換若=1,則父代第i個基因不相互交換均勻交叉例如基因型:10001011101101010001110基因解碼編碼個體（染色體）表現(xiàn)型:0.637197幾個術(shù)語00000|0111000000001000011100|00000111111000101交叉后:00000|0000011111100010111100|01110000000010000單點交叉運(yùn)算交叉點交叉前:

產(chǎn)生初始群體

是否滿足停止準(zhǔn)則

否

產(chǎn)生新一代群體GA的框圖輸出結(jié)果并結(jié)束

計算個體適應(yīng)度值

基本位變異運(yùn)算

執(zhí)行M/2次單點交叉運(yùn)算比例選擇運(yùn)算是線性分類器x

f

y

…

…

間到到隔隔::的的nn））器器ggii類類aarr分分mm性性（（線線f(x,w,b)=sign(w.x-b)超平面最近的樣本

與此超平面之間的

距離。+1-

1最大間隔x

f

y其就是一種最簡單的支持向量機(jī)(SVM)(稱為線性支持向量機(jī),即LSVM)f(x,w,b)=sign(w.x-b)具有最大間隔的線性分類器叫做最大

間隔線性分類器。線性支持向量機(jī)+1-

1

+

…

s

)

具有最大間隔的線

"

間隔線性分類器

。支持向量·

。

。

的點。xxbb))((ww,,ww,,iiggnnff((xx1111(Support其就是一種最簡單Vectors):…")是那些距離。。量機(jī),即LSVM)超平面最近線性支持向量機(jī)向向VVMM持持((SS支支機(jī)機(jī)性性量量線線向向為為持持稱稱支支((的的最大間隔x

f

y.。?！阈苑诸惼鹘凶鲎畲笾С窒蛄?/p>

·

"

其就是一種最簡單Vectors)

:

"

"(稱為線性支持向是那些距離

超平面最近

線性支持向量機(jī)

的點。f(x,w,b)=sign(w.x-b)具有最大間隔的線性分類器叫做最大心

"間隔線性分類器

。(Support

"的支持向量機(jī)(SVM)最大間隔?Why…量機(jī),即LSVM)+1-

1傳統(tǒng)的統(tǒng)計模式識別方法只有在樣本趨向無窮大時,其性能才有理論的保證。統(tǒng)計學(xué)習(xí)理論（STL）研究有限樣本情況下的機(jī)器學(xué)習(xí)問題。SVM的理論基礎(chǔ)就是統(tǒng)計學(xué)習(xí)理論。傳統(tǒng)的統(tǒng)計模式識別方法在進(jìn)行機(jī)器學(xué)習(xí)時,強(qiáng)調(diào)經(jīng)驗風(fēng)險最小化。而單純的經(jīng)驗風(fēng)險最小化會產(chǎn)生“過學(xué)習(xí)問題”,其推廣能力較差。推廣能力是指:將學(xué)習(xí)機(jī)器(即預(yù)測函數(shù),或稱學(xué)習(xí)函數(shù)、學(xué)習(xí)模型)對未來輸出進(jìn)行正確預(yù)測的能力。SVM的理論基礎(chǔ)“過學(xué)習(xí)問題”:某些情況下，當(dāng)訓(xùn)練誤差過小反而會導(dǎo)致推廣能力的下降。例如:對一組訓(xùn)練樣本(x,y),x分布在實數(shù)范圍內(nèi)，y取值在[0，1]之間。無論這些樣本是由什么模型產(chǎn)生的，我們總可以用y=sin(w*x)去擬合，使得訓(xùn)練誤差為0.過學(xué)習(xí)問題根據(jù)統(tǒng)計學(xué)習(xí)理論,學(xué)習(xí)機(jī)器的實際風(fēng)險由經(jīng)驗風(fēng)險值和置信范圍值兩部分組成。而基于經(jīng)驗風(fēng)險最小化準(zhǔn)則的學(xué)習(xí)方法只強(qiáng)調(diào)了訓(xùn)練樣本的經(jīng)驗風(fēng)險最小誤差,沒有最小化置信范圍值,因此其推廣能力較差。Vapnik提出的支持向量機(jī)（SupportVectorMachine,SVM）以訓(xùn)練誤差作為優(yōu)化問題的約束條件,以置信范圍值最小化作為優(yōu)化目標(biāo),即SVM是一種基于結(jié)構(gòu)風(fēng)險最小化準(zhǔn)則的學(xué)習(xí)方法,其推廣能力明顯優(yōu)于一些傳統(tǒng)的學(xué)習(xí)方法。形成時期在1992—1995年。SVM由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問題的求解,因此SVM的解是全局唯一的最優(yōu)解SVM在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢,并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中Joachims最近采用SVM在Reuters-21578來進(jìn)行文本分類,并聲稱它比當(dāng)前發(fā)表的其他方法都好SVM推廣到高維空間

，

最優(yōu)分類線就變?yōu)樽顑?yōu)分類面

。。圖中,

方形點和圓形點代表兩類樣

本,

H

為分類線,H1

,

H2分別為過

各類中離分類線最近的樣本且平行

于分類線的直線,

它們之間的距離

叫做分類間隔(margin)

。所謂最優(yōu)分類線就是要求分類線不

但能將兩類正確分開(訓(xùn)練錯誤率為0)

,而且使分類間隔最大

.SVM

是從線性可分情況下的最優(yōu)分類面發(fā)展而來

的,

基本思想可用圖2的兩維情況說明.最優(yōu)分類面最優(yōu)分類面

如何求最優(yōu)分類面最優(yōu)分類面①非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射

;②對特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊際的思想是SVM方法的核心

;③支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定作用的是支持向量。SVM

是一種有堅實理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法

。它

基本上不涉及概率測度及大數(shù)定律等,

因此不同于現(xiàn)有的統(tǒng)

計方法

。從本質(zhì)上看,它避開了從歸納到演繹的傳統(tǒng)過程,實

現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報樣本的“轉(zhuǎn)導(dǎo)推理”(transductive

inference)

,大大簡化了通常的分類和回歸

等問題。SVM方法的特點SVM的最終決策函數(shù)只由少數(shù)的支持向量所確定,計

算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上避免了“維數(shù)災(zāi)難

”。少數(shù)支持向量決定了最終結(jié)果,這不但可以幫助我們

抓住關(guān)鍵樣本、“剔除

”大量冗余樣本,而且注定了該方法不但算法簡單,而且具有較好的“魯棒

”性。這種“魯棒

”性主要體現(xiàn)在

:。①增

、刪非支持向量樣本對模型沒有影響

;。②支持向量樣本集具有一定的魯棒性

;。③有些成功的應(yīng)用中,SVM

方法對核的選取不敏感。SVM方法的特點1、設(shè)全部樣本分為6類，2.計算距離矩陣D(0)

1

2

3

4

56

78

9

10

例1:如下圖所示（簡單的一維情況）0Ω

1Ω4Ω5Ω2Ω310409160416643625810Ω6Ω

1025949164Ω3Ω5Ω4Ω2Ω63、求最小元素：4、把Ω1,Ω3合并Ω7=(1,3)Ω4,Ω6合并Ω8=(4,6)5.作距離矩陣D(1)，按最小距離準(zhǔn)則Ω7Ω2Ω8Ω54916254004Ω8Ω5Ω7090Ω26.若合并的類數(shù)沒有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、Ω8,Ω5,Ω2合并,Ω9=（2,5,4,6）三、初始分類和調(diào)整①選一批代表點后,代表點就是聚類中心,計算其它樣本到聚類中心的距離,把所有樣本歸于最近的聚類中心點,形成初始分類,再重新計算各聚類中心,稱為成批處理法。②選一批代表點后,依次計算其它樣本的歸類,當(dāng)計算完第一個樣本時,把它歸于最近的一類,形成新的分類。再計算新的聚類中心,再計算第二個樣本到新的聚類中心的距離,對第二個樣本歸類。即每個樣本的歸類都改變一次聚類中心。此法稱為逐個處理法。③直接用樣本進(jìn)行初始分類,先規(guī)定距離d,把第一個樣品作為第一類的聚類中心,考察第二個樣本,若第二個樣本距第一個聚類中心距離小于d,就把第二個樣本歸于第一類,否則第二個樣本就成為第二類的聚類中心,再考慮其它樣本,根據(jù)樣本到聚類中心距離大于還是小于d,決定分裂還是合并。四、K-均值算法:成批處理法例:已知有20