第一篇：基于DV―Hop定位算法的改進

基于DV―Hop定位算法的改進

摘要：針對DV-Hop算法采用跳數(shù)乘以平均每跳跳距估算節(jié)點間的跳距，利用三邊測量法或極大似然估計法估算節(jié)點坐標信息，算法過程存在缺陷從而造成定位誤差過高的問題。為此提出一種基于節(jié)點密度區(qū)域劃分的DVHop改進算法（DZDVHop），依據(jù)網(wǎng)絡(luò)的連通度和節(jié)點密度限制參與估算的信標節(jié)點的跳數(shù)，采用加權(quán)質(zhì)心法估算定位坐標。Matlab仿真測試結(jié)果表明，在相同的網(wǎng)絡(luò)硬件和拓撲結(jié)構(gòu)環(huán)境下，改進后的算法能有效地減少節(jié)點通信量，且平均定位誤差率比傳統(tǒng)的DVHop算法減少了13.6%左右，提高了定位精度?！糂P）〗

針對DVHop算法采用跳數(shù)乘以平均每跳跳距估算節(jié)點間的跳距，利用三邊測量法或極大似然估計法估算節(jié)點坐標信息，算法過程存在缺陷從而造成定位誤差過高的問題。為此提出一種基于節(jié)點密度區(qū)域劃分的DVHop改進算法（DZDVHop），依據(jù)網(wǎng)絡(luò)的連通度和節(jié)點密度限制參與估算的信標節(jié)點的跳數(shù)，采用加權(quán)質(zhì)心法估算定位坐標。Matlab仿真測試結(jié)果表明，在相同的網(wǎng)絡(luò)硬件和拓撲結(jié)構(gòu)環(huán)境下，改進后的算法能有效地減少節(jié)點通信量，且平均定位誤差率比傳統(tǒng)的DVHop算法減少了13.6%左右，提高了定位精度。

關(guān)鍵詞：

無線傳感器網(wǎng)絡(luò)；密度區(qū)域劃分；節(jié)點定位；限跳機制

中圖分類號：TP393

文獻標志碼：A

0引言

現(xiàn)代電子技術(shù)、檢測技術(shù)和信號處理等技術(shù)的進步，促進了低功耗、多功能智能傳感器的快速發(fā)展[1]。無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是指由大量成本低廉的具有智能感知能力、計算能力、無線通信能力的傳感器節(jié)點組成的網(wǎng)絡(luò)，它可以感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)目標對象的信息[2-3]。作為一種新型信息獲取的系統(tǒng)，WSN廣泛應(yīng)用于軍事、環(huán)境監(jiān)測、城市交通、災(zāi)難防控等眾多領(lǐng)域[4]。節(jié)點定位問題是傳感器網(wǎng)絡(luò)進行目標識別、監(jiān)控、定位等應(yīng)用的前提，也是傳感器網(wǎng)絡(luò)應(yīng)用的關(guān)鍵技術(shù)之一[5-7]。研究節(jié)點定位算法的意義主要體現(xiàn)在兩方面：一是，WSN中的多數(shù)應(yīng)用都依賴于傳感器節(jié)點或者被檢測目標的地理位置信息，不知檢測目標位置而獲取的任何信息都是沒有意義的[8]；二是，WSN網(wǎng)絡(luò)的運行和管理需要節(jié)點位置信息的支持。因此，準確估算節(jié)點位置，在傳感器網(wǎng)絡(luò)的應(yīng)用中起著至關(guān)重要的作用。

節(jié)點定位技術(shù)分為基于測距（Range Based）的定位算法和無需測距（Range Free）的定位算法兩類[3]1283，[5]39，[8]3?；跍y距的定位算法原理是：通過測量節(jié)點與節(jié)點間的直線距離或角度信息估算未知節(jié)點的坐標位置，目前這類測距技術(shù)主要有RSSI（Received Signal Strength Indicator）、TOA（Time of Arrival）、TDOA（Time Difference on Arrival）和AOA（Angle of Arrival）等[1]77，[5]40?；跍y距定位算法的優(yōu)點是定位精度較高，缺點是網(wǎng)絡(luò)中的節(jié)點需要增加特殊的測距設(shè)備，從而導(dǎo)致節(jié)點成本較高。而無需測距的定位算法原理是：不需要測量節(jié)點間的實際距離以及節(jié)點間的方位角，只根據(jù)網(wǎng)絡(luò)中節(jié)點間的連通性、同向性等信息，就可以估算出未知節(jié)點的坐標位置，常用的無需測距技術(shù)有：APIT（Approximate PointinTriangulation test）、質(zhì)心算法、DVHop（Distance VectorHop）和Amorphous等算法[5]40，[9]。無需測距定位算法的優(yōu)點是：組網(wǎng)成本低、網(wǎng)絡(luò)資源開銷少，缺點是定位誤差率稍高。實踐證明無需測距定位技術(shù)更能適合多數(shù)WSN的應(yīng)用，而在眾多無需測距的定位算法中，DVHop算法以其算法過程的簡單性和實效性成為目前應(yīng)用較多的種類之一[7]2468。WSN中的節(jié)點分為兩類：一類是預(yù)先已知自身位置信息的傳感器節(jié)點，稱之為信標節(jié)點（或“錨節(jié)點”），信標節(jié)點的坐標信息既可以通過全球定位系統(tǒng)（Global Positioning System，GPS）等技術(shù)自動獲得，也可以在部署網(wǎng)絡(luò)時靠人工設(shè)置[8]6；第二類節(jié)點是預(yù)先并不知道自身的位置，通常稱之為待定位節(jié)點或者未知節(jié)點。這些未知節(jié)點的位置信息就需要利用本文和相關(guān)研究所探討的相關(guān)定位算法進行估算。

1經(jīng)典DVHop算法描述

美國Rutgers University的〖BP（〗Dragos 〖BP）〗Niculescu等將距離矢量路由與GPS原理相結(jié)合提出了一系列分布式定位算法（Ad Hoc Positioning System，APS）[10]。APS共包括DVHop、DV Distance、Euclidean、DV Coordinate、DV Bearing和DV Radial等6種類型。其中應(yīng)用較多的是DVHop，DVHop的執(zhí)行過程可歸納為以下3個階段[1]77，[5]40，[11]。首先，接收并存儲未知節(jié)點與它鄰近的每個信標節(jié)點間最小跳數(shù)；信標節(jié)點向鄰居節(jié)點廣播包含自身地理位置信息的分組，這樣網(wǎng)絡(luò)中的所有節(jié)點都能記錄下自己到每個信標節(jié)點的最小跳數(shù)。其次，計算未知節(jié)點與信標節(jié)點的跳距；每個信標節(jié)點根據(jù)上述第一個階段的操作，記錄下了自己與其他信標節(jié)點的坐標值以及它們間的跳數(shù)。最后利用式（1），就可以估算出自己的平均每跳跳距。其中：（xi，yi）、（xj，yj）是信標節(jié)點i和j的坐標，hj是信標節(jié)點i與j之間的跳數(shù)。

平均每跳跳距：

第二篇：基于RSSI測距的改進加權(quán)質(zhì)心定位算法

基于RSSI測距的改進加權(quán)質(zhì)心定位算法

王振朝1,2，張琦1，張峰1

（1.河北大學(xué) 電子信息工程學(xué)院，河北 保定 071002；

2.河北大學(xué) 河北省數(shù)字醫(yī)療工程重點實驗室，河北 保定 071002）

摘要：基于RSSI（Received Signal Strength Indication）的三角形加權(quán)質(zhì)心定位算法在測距和定位中存在較大誤差，針對這一缺點提出一種改進的加權(quán)算法。在該算法中采用節(jié)點距離倒數(shù)之和代替距離和的倒數(shù)作為權(quán)值，并且根據(jù)節(jié)點距離給出加權(quán)因子作為修正，以充分利用節(jié)點信息。仿真結(jié)果驗證了該算法的有效性，與原有定位算法比較其定位精度得到提升，最高可達50%。關(guān)鍵詞：定位；RSSI；加權(quán)；修正系數(shù)

中圖分類號：TM933 文獻標識碼：A

文章編號：1001-1390(2014)21-0000-00

*Improved Weighted Centroid Positioning Algorithm based on RSSI Ranging

WANG Zhen-chao1,2, ZHANG Qi1, ZHANG Feng1

(1.College of Electronic and Information Engineering, Hebei University, Baoding 071002, China.2.Key Laboratory of Digital Medical Engineering of Hebei Province, Hebei University, Baoding 071002, Hebei, China)Abstract：Aiming at the error existing in triangular weighted centroid positioning algorithm based on RSSI(Received Signal Strength Indication)ranging, an improved weighted algorithm is put forward in this paper.The sum of reciprocal of distance between nodes instead of the reciprocal of sum of distance has been taken as the weighted value.To make full use of the node information, the algorithm has been corrected according to the weighted factors.The simulation results verify the effectiveness of the proposed algorithm and show that the improved weighted centroid positioning algorithm can provide an additional maximum precision gain of 50%.Key words: positioning, RSSI, weighted, modified coefficient

0 引 言 1 算法模型

無線傳感器網(wǎng)絡(luò)[1-2]是面向應(yīng)用的，貼近客觀世

1.1 無線信號傳播模型

界的網(wǎng)絡(luò)系統(tǒng)。在大多數(shù)的傳感器網(wǎng)絡(luò)實際應(yīng)用中，準確知道節(jié)點的方位是至關(guān)重要的。在無線傳感網(wǎng)無線信號常用的傳播路徑損耗模型有:自由空絡(luò)的定位機制中，需要測量節(jié)點間的實際距離或方間傳播模型，對數(shù)距離路徑損耗模型，Hata模型，位時經(jīng)常采用的方法主要有TOA(Time of Arrival)，對數(shù)-常態(tài)分布模型等[5]。在這些理論模型中最常用TDOA（Time Difference of Arrival），RSSI和AOA的是對數(shù)-常態(tài)分布模型：（Angle of Arrival）等。但TOA需要精確的時鐘同假設(shè)節(jié)點A發(fā)射信號到節(jié)點B，損耗的功率為步，TDOA同樣需要比較準確的時鐘，AOA需要專PAB，傳播的距離為dAB，則路徑損耗計算公式如下： 門的天線陣列來測量特定信號的來源方向，而RSSI

P（1）AB?P(d0)?10klog10(dAB/d0)?x?測距是一種廉價的測距技術(shù)，不需要額外的硬件支持，RADAR[3]是一個經(jīng)典的基于RSSI的室內(nèi)定位系整理可得：

[4-5]統(tǒng),基于RSSI的定位算法是目前研究的熱點。(P(Pt?Px?x??P(d0))/10kAB?x??P(d0))/10k（2）d?10?10AB 本文對文獻[5]中提出的基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法進行了研究，對其算法進?式中 Pt是節(jié)點A的信號發(fā)射功率，Px是節(jié)點B接收行了分析和討論，并且在此基礎(chǔ)上提出了更為合理到的信號功率。是平均xσ值為0的高斯分布隨機變的加權(quán)方法，使得定位更加精確。數(shù)，其標準差范圍為4～10；系數(shù)k根據(jù)傳輸位置的不同取值也不一樣，其范圍在2～5之間；d0典型取 值為1m?？紤]RSSI理想模型，k=2，忽略xσ的影響，*基金項目：國家自然科學(xué)基金資助項目（61074175:61203160）；河北省自然科學(xué)基金(F2014201168)代入上式，整理(2)式可得：

dAB?10(Pt?Px?P(d0))/20（3）同時可以得到，B接收A信號時的信號強度為：

RSSI=發(fā)射功率+天線增益-路徑損耗（PAB）

在實際的應(yīng)用中，可以通過多次測量得到接收功率的平均值來有效的降低RSSI的系統(tǒng)誤差。

1.2 三角形加權(quán)質(zhì)心定位算法

基于RSSI的三角形質(zhì)心定位算法是將RSSI測量與三角形質(zhì)心定位法相結(jié)合的新型定位算法。該算法是利用各個已知節(jié)點的發(fā)射信號強度，根據(jù)未知節(jié)點接收到的每個已知節(jié)點的信號強度，計算出各條路徑的信號傳播損耗。在眾多路徑中選取其中三個信號傳播損耗較小的，利用理論模型和經(jīng)驗?zāi)Ｐ蚚5-6]將傳輸損耗轉(zhuǎn)化為距離，分別以傳輸距離為半徑，已知節(jié)點為圓心畫圓，如圖1所示，計算出三個圓的交點坐標，以這三個點為頂點能夠組成一個三角形，三角形的質(zhì)心坐標即為未知節(jié)點的坐標[6]。

但是以上定位算法并沒有考慮未知節(jié)點與已知節(jié)點距離的遠近對定位的影響，而將三個參與定位的節(jié)點的作用等同，造成較大的定位誤差。文獻[5]提出了一種改進的定位算法，為參與定位的節(jié)點增加了權(quán)值，以體現(xiàn)不同頂點的貢獻值。根據(jù)對數(shù)-常態(tài)分布模型繪制的RSSI曲線分析圖[5]可知，已知節(jié)點到未知節(jié)點的距離越近，由RSSI值的偏差產(chǎn)生的絕對距離誤差越小。因此，距離越近的節(jié)點權(quán)重越大，距離遠近與權(quán)重大小呈反比的關(guān)系[7]。而三角形的每個頂點由兩個距離確定，故權(quán)值選擇為

1dA?dB（假設(shè)圓A與圓B相交，圓心距交點的距離分別為dA和dB，如圖1），故將算法的公式修正為：

??xAxBxC?d?d?A?dBdB?CdA?dC?x?1???d?1?1A?dBdB?dCdA?dC（4）

?yAyyC??y?dd?B?A?BdB?dCdA?dC?1??d?d?1?1ABdB?dCdA?dCdAhdBdC 圖1 加權(quán)質(zhì)心算法原理圖

Fig.1 Schematic of triangular weighted centroid

positioning algorithm 改進的三角形加權(quán)質(zhì)心定位算法

上述的加權(quán)算法雖然考慮到了距離的不同對定

位造成的不同影響，提出加權(quán)因子

1d，進而提

A?dB高了定位精度，然而在權(quán)值[8]的選擇上依然存在一些不合理的地方。兩個已知節(jié)點的半徑和的倒數(shù)這個因子的選取，使得dA和dB成為決定未知節(jié)點位置的關(guān)鍵。然而dA和dB中數(shù)值較大的一個會在這個因子中起到更大的作用，使得較小的數(shù)值對應(yīng)的節(jié)點所發(fā)揮的作用弱化，造成定位誤差。在本論文的算法中，對權(quán)值的選擇上進行了修正。首先是改變權(quán)重

中dA和dB地位上的主導(dǎo)關(guān)系，將1d變?yōu)锳?dB1d?1，充分利用了節(jié)點測量數(shù)據(jù)的信息；其次為AdB了進一步改善權(quán)值的決定權(quán)，防止修正過度，采取增加冪值的方法：

1?11n?m

dA?dBdAdB這個修正方法起到了避免次要數(shù)據(jù)起主要作用的情況發(fā)生，并且可以有效地防止修正過度。例如，dA>dB時，與dA相關(guān)的已知節(jié)點和未知節(jié)點的距離更遠，在公式中應(yīng)該起次要作用，而對于修正前的系數(shù)1d?d來說，dA

卻起到了主要作用，淹沒了應(yīng)

AB該起主要作用的dB。而本文給出的修正系數(shù)可以使較小的數(shù)起主要作用，即距離未知節(jié)點較近的已知節(jié)點有較大權(quán)重，并通過調(diào)整n、m的值調(diào)整修正的程度。

修正程度n、m的研究較為繁瑣，由于n、m是與距離dA、dB有關(guān)的兩個變量，（1）式中參數(shù)的變化會影響dA、dB與n、m的取值，所以如果直接研究dA、dB與n、m關(guān)系會比較復(fù)雜。為了計算方便同時提高定位精度，這里采用比值的方法，利用兩者的比值dA作為dB的冪值?？紤]到應(yīng)用實際，我dB們這里主要討論已知節(jié)點與未知節(jié)點間的距離都大于1的情況。

在dA和dB都大于1的條件下，假設(shè)n=1，m?dA。例如當(dāng)d>d時，m>1，這時因子1的AB

dBmdB存在使得在系數(shù)

11中原本起主要作用的dB所?dAdB起作用稍微弱化，以防止過度修正，這樣可以進一步充分利用數(shù)據(jù)信息。修正以后的算法公式為：

111111?x?(?)?x?(?)?x?(?)ABCdAdAdAdA?dAdA?dBdBdBdBdCdCdCdC?x?111?2?(??)dAdAdA?dBdBdCdC?

（5）?111111?yA?(?)?yB?(dA?))?yC?(?)dAdAdA?dAdAdBdBdBdBdCdCdCdC??y?1112?(??)?dAdAdA?dBdBdCdC?3 改進后的定位算法實現(xiàn)步驟

改進后的三角形質(zhì)心算法定位的實現(xiàn)過程：

(1)將已知節(jié)點命名為錨節(jié)點[9-10]，錨節(jié)點周期性地向周圍廣播信息，信息中包括自身節(jié)點ID號及其坐標。

(2)未知節(jié)點根據(jù)接收到的信息，只記錄同一個錨節(jié)點的RSSI值，當(dāng)接收到一定數(shù)量的RSSI值后，對多個RSSI數(shù)據(jù)取均值，作為接收到的這個錨節(jié)點的RSSI值；

(3)當(dāng)未知節(jié)點收到一定數(shù)量的錨節(jié)點信息后，停止接收信息，將RSSI從強到弱對錨節(jié)點排序，建立2個集合。錨節(jié)點集合：

(6)定義定位誤差為Er，其真實位置為(x0 , y0)，則定位誤差Er為：

Er?(xh?x0)2?(y n?y0)2f?{(a1,x1,y1),(a2,x2,y2),(a3,x3,y3),(a4,x4,y4),...,(an,xn,yn)}

錨節(jié)點依據(jù)RSSI從大到小排列的集合： 仿真

利用Matlab對算法進行仿真實驗以驗證該算法的有效性，并與加權(quán)的三角形質(zhì)心定位算法進行對比。假設(shè)在100m×100m的正方形區(qū)域內(nèi)，均勻地放置錨節(jié)點的數(shù)量分別為25、36、64、81，節(jié)點的無線射程距離相同，通信半徑為30m，且為圓形區(qū)域，能夠保證各個節(jié)點都可以正常接收RSSI信息，然后在該區(qū)域內(nèi)隨機放置一個節(jié)點進行定位，試驗進行100次，得到定位誤差數(shù)據(jù)如下所示：

表1 兩種算法的誤差對比數(shù)據(jù) Tab.1 Data contrast of the two algorithms

錨節(jié)點數(shù)量 加權(quán)的三角形質(zhì)心改進的加權(quán)三角形質(zhì)誤差下降比

/個 25 36

算法(誤差/m)

3.4 2.9 1.1 0.8

心算法（誤差/m）

2.4 1.8 0.6 0.4

例（%）29 38 45 50 d?{a1,a2,a3,a4,...,an}

(4)選取RSSI值大的前三個并利用理論模型和經(jīng)驗?zāi)Ｐ蛯⑵滢D(zhuǎn)化為錨節(jié)點與未知節(jié)點之間的距離，即：

{a1,d1},{a2,d2},{a3,d3}。

(5)利用本文的算法，能夠得出未知節(jié)點的估計位置(xh , yh)。

81

3.53加權(quán)算法改進的加權(quán)算法---米2.5/離距2差誤1.510.***090錨節(jié)點個數(shù)/個

圖2 兩種算法的誤差分析對比

Fig.2 Error analysis contrast of the two algorithms 從表1以及圖2中可以看出：本文提出的改進后的三角形加權(quán)質(zhì)心定位算法對于未知節(jié)點的定位精度較文獻[5]中的算法有了較大程度的提高；隨著錨節(jié)點數(shù)量的增多，定位精度也隨之提高，這是因為當(dāng)未知節(jié)點距離錨節(jié)點距離相對較遠時，利用RSSI測距技術(shù)定位會存在較大的干擾，造成定位有較大的誤差。本文的算法是在RSSI的基礎(chǔ)上對三角形質(zhì)心定位算法的改進，故修正的精度會跟錨節(jié)點的數(shù)量有一定的關(guān)系，在一定范圍內(nèi)，錨節(jié)點數(shù)量越多，定位的精度也越高。5 結(jié)束語

基于RSSI測距的三角形加權(quán)質(zhì)心算法在實際的定位應(yīng)用中誤差較大，這是由于在權(quán)值的選擇上存在一些問題。本文在文獻[5]的基礎(chǔ)上采用測試距離倒數(shù)之和代替距離和的倒數(shù)作為權(quán)值，同時根據(jù)測試距離給出了修正因子，這樣可以防止修正過度和信息淹沒，以提高定位精度。在相同條件下，仿真效果明顯優(yōu)于文獻[5]中的三角形加權(quán)質(zhì)心算法，定位精度最高可提高50%。

參 考 文 獻

[1] 李曉維.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京: 北京理工大學(xué)出版社, 2007.[2] 孫利民, 李建中, 陳渝, 等.無線傳感器網(wǎng)絡(luò)[M].北京: 清華大學(xué)出版社, 2005.[3] Bahl P, Padmanabhan VN.RADAR: An In-building RF-based User Location and Tracking System[C].//Proc.of the IEEE INFOCOM 2000, Tel Aviv: [s.n.].2000, 2: 775-784.[4] ALIREZAN, JACEKI.A Testbed for Localizing Wireless LAN Devices Using Received Signal Strength[C].//Proceedings of 6th Annual Communication Networks and Services Research Conference

(CNSR2008).Halifax, Canada, 2008: 481-487.[5] 陳維克, 李文鋒, 首珩, 等.基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定

位算法[J].武漢理工大學(xué)學(xué)報, 2006, 20(12): 2695-2700.CHEN Wei-ke, LI Wen-feng, SHOU Heng, et al.Weighted Centroid Localization Algorithm Based on RSSI for Wireless Sensor Networks[J].Journal of Wuhan University of Technology, 2006, 20(12): 2695-2700.[6] 林 瑋, 陳傳峰.基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J].現(xiàn)代電子技術(shù), 2009, 32(2): 180-182.LIN Wei, CHEN Chuan-feng.RSSI-based Triangle and Centroid

Location in Wireless Sensor Network[J].Modern Electronics Technique, 2009, 32(2): 180-182.[7] 劉運杰, 金明錄, 崔承毅.基于RSSI的無線傳感器網(wǎng)絡(luò)修正加權(quán)質(zhì)心

定位算法[J].傳感技術(shù)學(xué)報, 2010, 23(5): 716-721.LIU Yun-jie, JIN Ming-lu, CUI Cheng-yi.Modified Weighted Centroid

Localization Algorithm Based on RSSI for WSN[J].Chinese Journal of Sensors and Actuators, 2010, 23(5): 716-721.[8] 朱博, 陳曙.一種無線傳感器網(wǎng)絡(luò)質(zhì)心定位改進算法[J].傳感技術(shù)學(xué)

報, 2010, 23(6): 868-872.ZHU Bo, CHEN Shu.An Improved Centroid Localization Algorithm for Wireless Sensor Network[J].Chinese Journal of Sensors and Actuators, 2010, 23(6): 868-872.[9] 神顯豪, 楊小平.基于RSSI的WSN節(jié)點改進質(zhì)心定位算法[J].微計

算機信息(測控自動化), 2010, 26(11-1): 213-214.SHEN Xian-hao, YANG Xiao-ping.Improved RSSI-based Centroid

Localization Algorithm for Wireless Sensor Networks[J].Control and Automation Publication Group.2010, 26(11-1): 213-214.[10] 李娟, 王珂, 李莉.基于錨圓交點加權(quán)質(zhì)心的無線傳感器網(wǎng)絡(luò)定位算

法[J].吉林大學(xué)學(xué)報(工學(xué)版), 2009, 39(6): 1649-1653.LI Juan, WANG Ke, LI li.Weighted Centroid Localization Algorithm

Based on Intersection of Anchor Circle for Wireless Sensor Network[J].Journal of Jilin University(Engineering and Technology Edition), 2009, 39(6): 1649-1653.作者簡介:

王振朝（1958—），男，山東鄄城人，河北大學(xué)電子信息工程學(xué)

院教授，博士，主要從事工業(yè)數(shù)據(jù)通信及控制網(wǎng)絡(luò)，電力線載波通信技術(shù)及其應(yīng)用，電磁場的生物效應(yīng)等研究方向。

張琦(1986—)，男，碩士研究生，主要研究方向為無線自組網(wǎng)。張峰(1987—)，男，碩士研究生，主要研究方向為無線自組網(wǎng)。

收稿日期：2012-09-12;修回日期：2012-09-12

（田春雨

編發(fā)）

第三篇：新課程算法初步的教學(xué)定位探討

新課程算法初步的教學(xué)定位探討

內(nèi)容摘要：“算法初步”是高中數(shù)學(xué)課程中全新的內(nèi)容，算法思想已成為現(xiàn)代人應(yīng)具備的一種數(shù)學(xué)素養(yǎng)。由于算法初步的新生性,目前我們對它的定位把握不夠，有很多老師把算法課上成了計算機課，甚至于有些學(xué)校干脆請計算機老師來教數(shù)學(xué)課中的算法.本文將從新課程標準對算法的要求、學(xué)生認知能力及各地的高考要求這三個方面對算法的教學(xué)定位做進一步探討研究,并提出了相應(yīng)的教學(xué)建議。

關(guān)鍵詞：數(shù)學(xué)課程標準；算法初步；教學(xué)定位

一

問題的提出

《普通高中數(shù)學(xué)課程標準（實驗）》（以下簡稱《標準》）確定了高中數(shù)學(xué)課程的總目標：“使學(xué)生在九年義務(wù)教育基礎(chǔ)上，進一步提高作為未來公民所必要的數(shù)學(xué)素養(yǎng)，以滿足個人發(fā)展與社會進步的需要。”在具體目標中指出：使學(xué)生“獲得必要的數(shù)學(xué)基礎(chǔ)知識和基本技能，理解基本的數(shù)學(xué)概念、數(shù)學(xué)結(jié)論的本質(zhì)，了解概念、結(jié)論產(chǎn)生的背景、應(yīng)用，體會其中所蘊含的數(shù)學(xué)思想和方法，以及它們在后續(xù)學(xué)習(xí)中的作用，通過不同形式的自主學(xué)習(xí)、探究活動、體驗數(shù)學(xué)發(fā)展和創(chuàng)造的歷程?！?/p>

算法初步在新課標中是必修模塊數(shù)學(xué)3中的內(nèi)容之一。算法思想源遠流長，中國古代數(shù)學(xué)中就蘊涵了豐富的算法思想。由于西方演繹數(shù)學(xué)的常足進步，算法數(shù)學(xué)曾一度被人們所忽略。但隨著現(xiàn)代信息技術(shù)的飛速發(fā)展，算法重新煥發(fā)出了前所未與的活力，在科學(xué)技術(shù)、社會發(fā)展中發(fā)揮著越來越大的作用，并且日益融入社會生活的許多方面，算法思想已成為現(xiàn)代人應(yīng)具備的一種數(shù)學(xué)素養(yǎng)。

算法作為新名稱，在以前的數(shù)學(xué)教材中沒有出現(xiàn)，但算法本身，學(xué)生并不陌生，小學(xué)中的加減乘除四則運算，初中的解方程的算法，解不等式的算法，因式分解的算法等等，都是同學(xué)們思想的內(nèi)容。由于算法初步是新課程中新增內(nèi)容，所以目前我們對它的定位把握不夠，有很多老師把算法課上成了計算機課，甚至于有些學(xué)校干脆請計算機老師來教數(shù)學(xué)課中的算法，所以我們有必要對算法的教學(xué)定位做進一步探討研究。二 “算法”內(nèi)容的定位分析

2.1從新課程標準對算法的要求中研究算法教學(xué)定位

《高中數(shù)學(xué)課程標準》中指出：“算法是數(shù)學(xué)及其應(yīng)用的重要組成部分，是計算科學(xué)的重要基礎(chǔ)，算法思想已成為現(xiàn)代人應(yīng)具備的一種數(shù)學(xué)素養(yǎng)。在本模塊中，學(xué)生將在義務(wù)教育階段初步感受算法思想的基礎(chǔ)上，結(jié)合對具體教學(xué)實例的分析，體驗程序框圖在解決問題中的作用；通過模仿，操作，探索，學(xué)習(xí)設(shè)計程序框圖表達解決問題的過程，體會算法的基本思想及算法的重要性和有效性，發(fā)展有條理地思考與表達的能力，提高邏輯思維能力”?！稑藴省分刑貏e強調(diào)：“不要將此部分內(nèi)容覺得處理成程序語言的學(xué)習(xí)和程序設(shè)計”。

《高中信息技術(shù)課程標準》中指出：“本模塊旨在使學(xué)生進一步體驗算法思想，了解算法和程序設(shè)計在解決問題過程中的地位和作用；能從簡單問題出發(fā)，設(shè)計解決問題的算法，并能初步使用一種程序設(shè)計語言編制程序?qū)崿F(xiàn)算法解決問題。本模塊為選修模塊。本模塊的教學(xué)，應(yīng)注意與數(shù)學(xué)課程中有關(guān)內(nèi)容的銜接，要強調(diào)理論與實踐的結(jié)合，引導(dǎo)學(xué)生注意尋找、發(fā)現(xiàn)身邊的實際問題，進而設(shè)計出算法和計算機程序去解決這些問題。教師要注意發(fā)現(xiàn)對程序設(shè)計有特殊才能的學(xué)生，根據(jù)具體情況為他們提供充分的發(fā)展空間。本模塊強調(diào)的是通過算法與程序設(shè)計解決實際問題的方法，對程序設(shè)計語言的選擇不作具體規(guī)定”。

從這兩門課程的課程標準的對比中可以看出，兩門課程的主要區(qū)別在于：數(shù)學(xué)課程中算法教學(xué)的主要目的是使學(xué)生體會算法的思想，提高邏輯思維能力；信息技術(shù)課程的主要目的是設(shè)計解決問題的算法，并能初步使用一種程序設(shè)計語言編制程序?qū)崿F(xiàn)算法解決問題，在程序設(shè)計語言的要求上技術(shù)課比數(shù)學(xué)課的要求高很多。兩門課程的聯(lián)系在于：所設(shè)計的算法正確與否要通過遍程并且運行程序進行驗證，借助于程序語言可以使算法得以實現(xiàn)；反之要設(shè)計程序就必須弄清算法原理，從這一點上，可以說，算法教學(xué)是程序語言教學(xué)的基礎(chǔ)，程序語言教學(xué)是算法教學(xué)必要的延續(xù)，兩者相輔相成。

2.2從學(xué)生認知能力來研究算法教學(xué)定位

與以往的課程目標相比，新的課程目標著眼于人終身學(xué)習(xí)和個性發(fā)展，目標中除規(guī)定了外顯行為外，更加注重對學(xué)習(xí)者的內(nèi)部心理過程的描述，因此，“算法初步”課程目標需要心理學(xué)的角度加以理解。例如，對大部分的學(xué)生來說。從“算法初步”課中能學(xué)到哪些“有用”的知識？在計算機技術(shù)日新月異的今天，還有 必要學(xué)習(xí)“算法初步”？短短十二個學(xué)時能學(xué)會算法嗎？“算法初步”課的基礎(chǔ)教育性質(zhì)體現(xiàn)在哪里？它是如何支撐學(xué)生的進一步發(fā)展的？等等。

在高中階段，“算法初步”課程應(yīng)該是讓學(xué)生學(xué)習(xí)那些具有廣泛意義的知識和方法，是“為遷移而教”，其實質(zhì)是塑造學(xué)生良好的認知結(jié)構(gòu)。

何為認知結(jié)構(gòu)？奧蘇伯爾（D.P.Ausubel）認為,所謂認識結(jié)構(gòu)，就是學(xué)習(xí)者頭腦里的知識結(jié)構(gòu)。廣義地說，它是學(xué)習(xí)者的觀念的全部內(nèi)容和組織；狹義地說，它是學(xué)習(xí)者在某一特殊知識領(lǐng)域內(nèi)的觀念的內(nèi)容和組織。學(xué)習(xí)者學(xué)習(xí)時，新舊知識通過反復(fù)同化，最后形成一個綜合貫通的網(wǎng)絡(luò)結(jié)構(gòu)。從認識心理學(xué)的這一基本理論來看，學(xué)習(xí)者認識結(jié)構(gòu)的建立是一個長期的過程，教學(xué)的意義在于盡可能幫助學(xué)生建立一個合理的認識結(jié)構(gòu)。一般而言，認識結(jié)構(gòu)建立得越合理，有效學(xué)習(xí)發(fā)生的可能性就越大；認識結(jié)構(gòu)越完善，復(fù)雜程序越高，學(xué)習(xí)者的外顯能力就越強。從這方面看，“算法初步”課程目標就是要學(xué)生已有的適當(dāng)觀念上，幫助他們建立盡可能合理的算法初步認識結(jié)構(gòu)，學(xué)習(xí)用算法初步的思想方法解決問題，培養(yǎng)學(xué)習(xí)算法初步的興趣愛好，為學(xué)生將來的發(fā)展提供該領(lǐng)域的知識與能力準備。

那么，什么樣的算法初步認識結(jié)構(gòu)才是合理的呢？合理的算法初步認識結(jié)構(gòu)應(yīng)該是算法初步的一般規(guī)律及其基本思想方法的學(xué)習(xí)者認識結(jié)構(gòu)中的合理映射，是利用算法初步解決問題的能力的合理映射，是利用算法初步解決問題的能力的合理映射，同時還是樂于此道的態(tài)度的合理映射（延伸、收獲、體驗），它是一個系統(tǒng)結(jié)構(gòu)，而不是程序框圖、方法技巧的簡單堆砌，知識、技能、能力間的聯(lián)系是非人為的和實質(zhì)性的。對于高中生來說，這一認識結(jié)構(gòu)所映射的是算法的最具普遍意義的知識體系，是靈活運用習(xí)得的知識改造舊有觀念，以及解決基本問題的能力，并形成積極主動的探究態(tài)度，在此基礎(chǔ)上，學(xué)生可以通過繼續(xù)學(xué)習(xí)逐步完善這一認識結(jié)構(gòu)。

學(xué)生這一階段的認知結(jié)構(gòu)特點表現(xiàn)為：易于接受具體的、特殊的、有趣的數(shù)學(xué)知識，難以接受抽象的、一般的、枯燥乏味的數(shù)學(xué)知識。所以在教材的安排中體現(xiàn)了一種從特殊到一般的思想。教材中也是從具體實例出發(fā)引出這一類問題的通法。考慮到這一認知特點，我們提出以下教學(xué)建議

2.3 從各地的高考要求中研究算法教學(xué)定位

1．（07．海南、寧夏卷.5）如果執(zhí)行 如圖的程序框圖,那么輸出的S等于()A.2450 B.2500 C.2550 D.2652

2.(07.山東卷.10)閱讀如右圖所示的程序

框圖,若輸出的 n是100,則輸出的 變量S和T的值依次是()A 2550,2500 B 2550,2550 C 2500,2500 D 2500,2550 以上兩道高考題都在考查學(xué)生的識圖能力和程序框圖的應(yīng)用，以及學(xué)生對條件語句和循環(huán)語句的理解。

縱觀海南，山東，寧夏等省市算法中的高考題可以發(fā)現(xiàn)，循環(huán)結(jié)構(gòu)是考試的重點，所以它也是我們教學(xué)的重點和難點。這也提醒我們教師在教學(xué)中要準確定位，不要把難度拔得太高。

三 對算法內(nèi)容的教學(xué)建議

(1)在教學(xué)中要時時聯(lián)系新課標,注意突出算法思想，使學(xué)生經(jīng)歷通過模仿、探索、操作、設(shè)計程序框圖表達解決問題等的過程，而不應(yīng)在將算法內(nèi)容單純處理成程序語言的學(xué)習(xí)和程序設(shè)計,但在教學(xué)中要能借信息技術(shù)之東風(fēng)助算法揚帆起航。(2)在教學(xué)中要多從學(xué)生的認知情況出發(fā), 重視從特殊到一般的教學(xué)思想,多選擇實例進行教學(xué).在選取實例教學(xué)時要注意：

① 選取的實例是具體的、鮮活的、是學(xué)生能夠感受到的或是他們已經(jīng)積累的知識。如我國古代數(shù)學(xué)著作《九章算術(shù)》中有一個著名的“雞兔同籠”問題：“今有雉兔同籠,上有三十五頭,下有九十四足,問雉兔各幾何?”利用此例引入算法含義能夠提升學(xué)生的學(xué)習(xí)興趣。

② 所選的例子不要太難,例子太難容易是學(xué)生產(chǎn)生厭學(xué)心理。所選取的例子要有一定的基礎(chǔ)性要蘊涵豐富的算法思想，能夠讓學(xué)生從中學(xué)習(xí)算法的“三基”————基本思想、基本結(jié)構(gòu)以及基本語句。例如：在講解選擇結(jié)構(gòu)時，可以選取比較基礎(chǔ)且具有代表意義的分段函數(shù)的例子，這樣既能幫助學(xué)生理解選擇結(jié)構(gòu)的基本思想，又能幫助學(xué)生更好地掌握分段函數(shù)。(3)在教學(xué)中要多注意對高考題的積累和對高考要求的準確把握,注意循序漸進，逐層深入，分散難點。多重視條件語句和循環(huán)語句的教學(xué).參考文獻: [1] 中學(xué)數(shù)學(xué)課程教材研究開發(fā)中心.普通高中課程標準實驗教科書·數(shù)學(xué)3.人民教育出版社，2004.[2] 中華人民共和國教育部.普通高中數(shù)學(xué)課程標準.北京.人民教育出版社,2003 [3] 中華人民共和國教育部.普通高中技術(shù)課程標準.北京.人民教育出版社,2003 [4] 皮連生.教育心理學(xué).上海.上海教育出版社,2004 [5] 容德基教育研究中心.2007年高考卷匯編數(shù)學(xué)(文科).內(nèi)蒙古少年兒童出版社 [6] 王建國、劉彬.高中數(shù)學(xué)算法教學(xué)內(nèi)容難度的比較與研究.北京教育學(xué)院學(xué)報第一卷第六期

[7] 熊芹.對高中必修課“算法初步”教學(xué)策略的探討.中國數(shù)學(xué)教學(xué),2006年第4期

第四篇：機器學(xué)習(xí)算法優(yōu)缺點改進總結(jié)

Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)（2）Linear Regression Algorithm(線性回歸)（3）Local Weighted Regression(局部加權(quán)回歸)（4）k-Nearest Neighbor Algorithm for Regression(回歸k近鄰)（5）Linear Classifier(線性分類)（6）Perceptron Algorithm(線性分類)（7）Fisher Discriminant Analysis or Linear Discriminant Analysis(LDA)（8）k-NN Algorithm for Classifier(分類k近鄰)（9）Bayesian Decision Method(貝葉斯決策方法)Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多層感知器)（2）BP Algorithm

Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量機)（此算法是重點，必考題）此處有一道必考題

Lecture 4 Introduction to Decision Rule Mining（1）Decision Tree Algorithm（2）ID3 Algorithm（3）C4.5 Algorithm（4）粗糙集……

Lecture 5 Classifier Assessment and Ensemble Methods（1）Bagging（2）Booting（3）Adaboosting Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms（2）FP-tree Algorithms Lecture 7 Introduction to Custering Analysis（1）k-means Algorithms（2）fuzzy c-means Algorithms（3）k-mode Algorithms（4）DBSCAN Algorithms Lecture 8 Basics of Feature Selection（1）Relief Algorithms（2）ReliefF Algorithms（3）mRMR Algorithms最小冗余最大相關(guān)算法（4）attribute reduction Algorithms

比較了幾種分類算法性質(zhì)。（以下兩個表格來自兩篇該領(lǐng)域經(jīng)典論文）

Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)①算法思想：

EM算法又稱期望最大化算法，是對參數(shù)極大似然估計的一種迭代優(yōu)化策略，它是一種可以從非完整的數(shù)據(jù)集中對參數(shù)進行極大似然估計的算法,應(yīng)用于缺損數(shù)據(jù)，截尾數(shù)據(jù)，帶有噪聲的非完整數(shù)據(jù)。

最大期望算法經(jīng)過兩個步驟交替進行計算：

第一步計算期望（E）：也就是將隱藏的變量對象能夠觀察到的一樣包含在內(nèi)，從而計算最大似然的期望值；

另外一步是最大化（M），也就是最大化在E步上找到的最大似然期望值，從而計算參數(shù)的似然估計。M步上找到的參數(shù)然后用于另一個E步計算。

重復(fù)上面2步直至收斂。

②優(yōu)點：1）Ｍ步僅涉及完全數(shù)據(jù)極大似然，通常計算比較簡單

2）收斂是穩(wěn)定的，因為每次迭代的似然函數(shù)是不斷增加的。

③缺點：1）表現(xiàn)在對缺失數(shù)據(jù)較多或是多維高斯分布的情形下，計算量大，收斂速度較慢。

2）對于某些特殊的模型，要計算算法中的M步，即完成對似然函數(shù)的估計是比較困難的。

3）在某些情況下，要獲得EM算法中E步的期望顯式是非常困難的。

4）EM算法的收斂速度，非常依賴初始值的設(shè)置，設(shè)置不當(dāng)，計算代價相當(dāng)大。

5）EM算法中的M-Step依然是采用求導(dǎo)函數(shù)的方法,所以它找到的是極值點,即局

部最優(yōu)解,而不一定是全局最優(yōu)解。④改進：針對1）改進：擴大參數(shù)空間來加快收斂

針對2）改進：ECM算法，該算法通過在Ｍ步構(gòu)建計算比較簡單的小循環(huán)對EM

算法進行了改進，從而使期望函數(shù)極大化更加容易和有效，從而解決這一問題。

針對3）改進：MCEM算法，將E步積分求期望用蒙特卡洛模擬方法來實現(xiàn)，使

得E步求期望更容易實現(xiàn)。

針對4）初始值的獲取可以通過k-means算法，層次聚類算法或是數(shù)據(jù)數(shù)據(jù)進行隨

機分割，然后重復(fù)EM效果進行初始點選擇。

針對5）結(jié)合遺傳算法的全局搜索能力，擴大EM算法的搜索空間，有效降低EM

算法對初始值的依賴度，改善局部最優(yōu)值的缺陷。

（2）Linear Regression Algorithm(線性回歸)①算法思想：

線性回歸(Linear Regression)是利用稱為線性回歸方程的最小平方函數(shù)對一個或多個自變量和因變量之間關(guān)系進行建模的一種回歸分析。這種函數(shù)是一個或多個稱為回歸系數(shù)的模型參數(shù)的線性組合。只有一個自變量的情況稱為簡單回歸,大于一個自變量情況的叫做多元回歸。

回歸模型：

i

其中 ?和C是未知參數(shù)，對于每個訓(xùn)練樣本(xi，yi)可得到h(xi)，用來預(yù)測真實值y。損失函數(shù)：

即誤差值的平方。

1：對于訓(xùn)練集，求取θ，使得損失函數(shù)最小。（使用最小二乘法，梯度下降法）2：對于新輸入x，其預(yù)測輸出為θTx ②優(yōu)點：結(jié)果易于理解，實現(xiàn)簡單，計算簡單

③缺點：1）對于非線性的數(shù)據(jù)擬合效果不好（原因：因為線性回歸將數(shù)據(jù)視為線性的，可能出現(xiàn)欠擬合現(xiàn)象，導(dǎo)致結(jié)果不能取得最好的預(yù)測效果）

2）如果訓(xùn)練數(shù)據(jù)如果有些數(shù)據(jù)偏差特別大，這回造成最后訓(xùn)練的模型可能對整體

具備很好的準確性

④改進：針對2）改進 ：局部加權(quán)回歸

數(shù)據(jù)都不（3）Local Weighted Regression(局部加權(quán)回歸)①算法思想：

給每個待預(yù)測點周圍的點賦予一定的權(quán)重,越近的點權(quán)重越高,以此來選出該預(yù)測點對應(yīng)的數(shù)據(jù)子集,然后在此數(shù)據(jù)子集上基于最小均方差進行普通的回歸.局部加權(quán)回歸實質(zhì)上是對于需要預(yù)測的點，只是根據(jù)其附近的點進行訓(xùn)練，其他的沒有改變。

對于局部線性加權(quán)算法：

1：對于輸入x，找到訓(xùn)練集中與x鄰域的訓(xùn)練樣本

2：對于其鄰域的訓(xùn)練樣本，求取θ，使得其

∈x的鄰域）最小。其中w(i)為權(quán)重值。

3.預(yù)測輸出為θTx

4.對于新輸入，重復(fù)1-3過程。

其中

τ 為帶寬(bandwidth)常量，距離輸入越遠，權(quán)重越小，反之越大。

②優(yōu)點：1）局部加權(quán)回歸還是對訓(xùn)練數(shù)據(jù)擬合的比較好

2）不太依賴特征的選擇，而且只需要用線性模型就能夠訓(xùn)練出不錯的擬合模型、③缺點：1）計算量較大。（因為局部加權(quán)回歸的損失數(shù)隨著預(yù)測值的不同而不同，這樣θ

就無法事先確定，每次預(yù)測時都需要掃描所有的數(shù)據(jù)并重新計算θ）

2）局部加權(quán)回歸容易出現(xiàn)過擬合現(xiàn)象，過擬合現(xiàn)象很明顯

3）關(guān)注局部的訓(xùn)練數(shù)據(jù)，忽略了全局數(shù)據(jù)，如果預(yù)測點在出現(xiàn)偏差的訓(xùn)練數(shù)據(jù)附

近，那么預(yù)測值會偏差很大。

④改進：

（4）k-Nearest Neighbor Algorithm for Regression(回歸k近鄰)①算法思想：

通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。

如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。

KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成反比。②優(yōu)點：

1）簡單、有效。

2）重新訓(xùn)練的代價較低（類別體系的變化和訓(xùn)練集的變化，在Web環(huán)境和電子商務(wù)應(yīng)用中是很常見的）。3）計算時間和空間線性于訓(xùn)練集的規(guī)模（在一些場合不算太大）。

4）由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

5）該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。③缺點：

（1）KNN在對屬性較多的訓(xùn)練樣本進行分類時，由于計算量大而使其效率大大降低，效果不是很理想。

（2）當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。

（3）對數(shù)據(jù)的局部結(jié)構(gòu)比較敏感。如果查詢點是位于訓(xùn)練集較密集的區(qū)域，那預(yù)測相對比其他稀疏集來說更準確。（4）對k值敏感。

（5）維數(shù)災(zāi)難：臨近距離可能被不相干屬性主導(dǎo)（因此特征選擇問題）④改進：

（1）分類效率：事先對樣本屬性進行約簡，刪除對分類結(jié)果影響較小的屬性，快速的得出待分類樣本的類別。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。（2）分類效果：采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進，Han等人于2002年嘗試利用貪心法，針對文件分類實做可調(diào)整權(quán)重的k最近鄰居法WAkNN(weighted adjusted k nearest neighbor)，以促進分類效果；而Li等人于2004年提出由于不同分類的文件本身有數(shù)量上有差異，因此也應(yīng)該依照訓(xùn)練集合中各種分類的文件數(shù)量，選取不同數(shù)目的最近鄰居，來參與分類。

（3）該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。該算法只計算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數(shù)量并不能影響運行結(jié)果?？梢圆捎脵?quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進。（4）K 值的選擇會對算法的結(jié)果產(chǎn)生重大影響。K值較小意味著只有與輸入實例較近的訓(xùn)練實例才會對預(yù)測結(jié)果起作用，但容易發(fā)生過擬合；如果 K 值較大，優(yōu)點是可以減少學(xué)習(xí)的估計誤差，但缺點是學(xué)習(xí)的近似誤差增大，這時與輸入實例較遠的訓(xùn)練實例也會對預(yù)測起作用，是預(yù)測發(fā)生錯誤。在實際應(yīng)用中，K 值一般選擇一個較小的數(shù)值，通常采用交叉驗證的方法來選擇最優(yōu)的 K 值。隨著訓(xùn)練實例數(shù)目趨向于無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向于無窮，則誤差率趨向于貝葉斯誤差率。

（5）該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

（5）Linear Classifier(線性分類器)①算法思想：線性分類器使用線性判別函數(shù)，實現(xiàn)線性判別函數(shù)分類的方法有感知器算法、LMSE分類算法和Fisher分類。

在分類問題中，因變量Y可以看做是數(shù)據(jù)的label，屬于分類變量。所謂分類問題，就是能夠在數(shù)據(jù)的自變量X空間內(nèi)找到一些決策邊界，把label不同的數(shù)據(jù)分開，如果某種方法所找出的這些決策邊界在自變量X空間內(nèi)是線性的，這時就說這種方法是一種線性分類器。

C1和C2是要區(qū)分的兩個類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個分類函數(shù)，它可以將兩類樣本完全分開。

線性分類器在數(shù)學(xué)上被理解為線性判別函數(shù)(Linear Discriminant Functions)，在幾何上可以理解為決策超平面(Decision Hyperplanes)。②優(yōu)點：算法簡單

③缺點：只能處理線性問題

④改進：要處理其他非線性問題，可以向高維轉(zhuǎn)化，例如用SVM方法。線性分類器是分類方法，不是具體算法。

（6）Perceptron Algorithm(感知器算法)①算法思想：

感知機（Perceptron）是二類分類的線性分類模型，其輸入為實例的特征向量，輸出為實例的類別，取+1和-1二值。感知機對應(yīng)于輸入空間（特征空間）中將實例劃分為正負兩類的分離超平面，屬于判別模型。②優(yōu)點：

（1）感知機學(xué)習(xí)算法是基于隨機梯度下降法的對損失函數(shù)的最優(yōu)化算法，有原始形式和對偶形式。算法簡單且易于實現(xiàn)；

（2）它提出了自組織自學(xué)習(xí)的思想。對能夠解決的問題有一個收斂的算法，并從數(shù)學(xué)上給出了嚴格的證明。（3）當(dāng)樣本線性可分情況下，學(xué)習(xí)率 合適時，算法具有收斂性。③缺點：

（1）即感知機無法找到一個線性模型對異或問題進行劃分。

（2）其實不光感知機無法處理異或問題，所有的線性分類模型都無法處理異或分類問題。（3）收斂速度慢；當(dāng)樣本線性不可分情況下，算法不收斂，且無法判斷樣本是否線性可分。

④改進：單個感知器雖然無法解決異或問題，但卻可以通過將多個感知器組合，實現(xiàn)復(fù)雜空間的分割。（7）線性判別分析（LDA，Linear Discriminant Analysis）①基礎(chǔ)概念

（1）判別分析概念

根據(jù)已知對象的某些觀測指標和所屬類別來判斷未知對象所屬類別的統(tǒng)計方法。利用已知類別的樣本信息求判別函數(shù)，根據(jù)判別函數(shù)對未知樣本所屬類別進行判別。（2）判別分析分類

按判別組數(shù)來分，有兩組判別分析和多組判別分析

按數(shù)學(xué)模型（函數(shù)形式）來分，有線性判別分析和非線性判別分析

按判別方法來分，有Fisher判別分析、Bayes判別分析和距離判別（K-NN）注:線性判別分析就是一般化的Fisher判別分析（3）Fisher判別分析與Bayes判別分析優(yōu)缺點比較

Fisher判別方法對總體分布沒有特殊要求，但是Fisher判別法未考慮各總體出現(xiàn)概率的大小，不能給出后驗概率以及錯判造成的損失。

Bayes判別法可以給出后驗概率以及錯判造成的損失。但是要求即各種變量必須服從多元正態(tài)分布、各組協(xié)方差矩陣必須相等、各組變量均值均有顯著性差異。②LDA缺點

LDA有兩個突出缺點:（1）處理高維圖像時容易產(chǎn)生“小樣本問題”, 即樣本維數(shù)大大超過訓(xùn)練圖像個數(shù)的問題；（2）由此引發(fā)的邊緣類主導(dǎo)特征空間分解的問題。（3）LDA的其余缺點（限制）：

LDA至多可生成C-1維子空間。

LDA不適合對非高斯分布的樣本進行降維。

LDA在樣本分類信息依賴方差而不是均值時，效果不好。

LDA可能過度擬合數(shù)據(jù)。

③針對“小樣本問題”的改進方法

可以利用本文設(shè)計的改進PCA 算法與LDA 算法相結(jié)合來解決小樣本問題，即將結(jié)合了基于標準差和局部均值的圖像增強處理算法的PCA 算法與LDA 算法相結(jié)合。具體的應(yīng)用過程即為: 先采用改進的PCA 算法對樣本進行降維處理，以便確保樣本的類內(nèi)離散度矩陣為非奇異的，利用改進的PCA 算法將原始樣本圖像往一個特征子空間中投影，從而使得樣本的類內(nèi)離散度矩陣是非奇異的。再利用LDA 算法在次特征子空間中求得最優(yōu)變換。

LDA與PCA的比較

兩者都是為了在對原始數(shù)據(jù)降維之后進行分類。PCA（Principal Component Analysis，主成分分析）是無監(jiān)督的方式，它沒有分類標簽，降維之后需要采用K-Means或自組織映射網(wǎng)絡(luò)等無監(jiān)督的算法進行分類。LDA是有監(jiān)督的方式，它先對訓(xùn)練數(shù)據(jù)進行降維，然后找出一個線性判別函數(shù)。（8）k-NN(k-Nearest Neighbor for classifier,分類最近鄰估計)①算法思想：（1）k-NN介紹

如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。（2）k-NN概念

k-NN算法通常以“歐氏距離(Euclidean Distance)”為其分類模型, 歐氏距離公式的定義如下: 設(shè)在n 維空間中有兩個點X =(x1,x2,?,xn)和Y =(y1,y2,?,yn), 它們之間的歐氏距離定義為:

其中, n是維數(shù), Xi和Yi分別是X和Y的第k個屬性值。②優(yōu)點

（1）簡單，易于理解，易于實現(xiàn)，無需估計參數(shù)，無需訓(xùn)練

（2）適合對稀有事件進行分類（例如當(dāng)流失率很低時，比如低于0.5%，構(gòu)造流失預(yù)測模型）

（3）特別適合于多分類問題(multi-modal,對象具有多個類別標簽)，例如根據(jù)基因特征來判斷其功能分類，kNN比SVM的表現(xiàn)要好.③缺點

（1）計算量大，由于要逐個計算到每條記錄的歐氏距離, 對于海量數(shù)據(jù), 該算法時間效率非常低。它在對每一個查詢實例(Query Instance)進行分類時, 都需要搜索整個訓(xùn)練集來尋找最近鄰, 所以它的運算開銷巨大, 時間代價高昂, 這導(dǎo)致了它的運行速度非常低下。

（2）可解釋性較差，無法給出決策樹那樣的規(guī)則。

（3）當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。該算法只計算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數(shù)量并不能影響運行結(jié)果。（4）由于所有屬性均等地參與計算, 沒有突出屬性的重要程度, 分類結(jié)果易受單個屬性的影響;④改進

缺點1：目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。缺點4：利用信息增益來衡量屬性的重要程度(即屬性權(quán)重系數(shù)),將屬性劃分為關(guān)鍵屬性、次要屬性及無關(guān)屬性, 解決屬性均等用力的問題;缺點3，可考慮從K值設(shè)定回答

1、k值設(shè)定為多大？

k太小，分類結(jié)果易受噪聲點影響；k太大，近鄰中又可能包含太多的其它類別的點。（對距離加權(quán)，可以降低k值設(shè)定的影響）

k值通常是采用交叉檢驗來確定（以k=1為基準）經(jīng)驗規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根

補充去年相關(guān)習(xí)題：

請闡述 kNN近鄰分類算法的基本思想，并分析它的主要優(yōu)缺點。關(guān)于 k 的取值，你有什么合理的建議（至少 1 條）。優(yōu)點

(1)簡單，易于理解，易于實現(xiàn)，無需估計參數(shù)，無需訓(xùn)練

(2)適合對稀有事件進行分類（例如當(dāng)流失率很低時，比如低于0.5%，構(gòu)造流失預(yù)測模型）(3)特別適合于多分類問題，例如根據(jù)基因特征來判斷其功能分類，kNN比SVM的表現(xiàn)要好 缺點

(1)懶惰算法，對測試樣本分類時的計算量大，內(nèi)存開銷大，評分慢

(2)當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有 可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)；

(3)可解釋性較差，無法給出決策樹那樣的規(guī)則。k值設(shè)定

k值選擇過小，得到的近鄰數(shù)過少，會降低分類精度，同時也會放大噪聲數(shù)據(jù)的干擾；而如果k值選擇過大，并且待分類樣本屬于訓(xùn)練集中包含數(shù)據(jù)數(shù)較少的類，那么在選擇k個近鄰的時候，實際上并不相似的數(shù)據(jù)亦被包含進來，造成噪聲增加而導(dǎo)致分類效果的降低。

k太小，分類結(jié)果易受噪聲點影響；k太大，近鄰中又可能包含太多的其它類別的點。（對距離加權(quán)，可以降低k值設(shè)定的影響）K值設(shè)定的建議

k值通常是采用交叉檢驗來確定（以k=1為基準）k一般低于訓(xùn)練樣本數(shù)的平方根

（9）貝葉斯決策方法（Bayesian Decision Method）①貝葉斯決策概念

貝葉斯決策（Bayesian Decision Theory）就是在不完全情報下，對部分未知的狀態(tài)用主觀概率估計，然后用貝葉斯公式對發(fā)生概率進行修正，最后再利用期望值和修正概率做出最優(yōu)決策。貝葉斯決策屬于風(fēng)險型決策，決策者雖不能控制客觀因素的變化，但卻掌握其變化的可能狀況及各狀況的分布概率，并利用期望值即未來可能出現(xiàn)的平均狀況作為決策準則。

貝葉斯決策理論方法是統(tǒng)計模型決策中的一個基本方法，其基本思想是：

已知類條件概率密度參數(shù)表達式和先驗概率。

利用貝葉斯公式轉(zhuǎn)換成后驗概率。

根據(jù)后驗概率大小進行決策分類。②貝葉斯決策方法優(yōu)缺點 優(yōu)點：

貝葉斯決策能對信息的價值或是否需要采集新的信息做出科學(xué)的判斷

它能對調(diào)查結(jié)果的可能性加以數(shù)量化的評價,而不是像一般的決策方法那樣,對調(diào)查結(jié)果或者是完全相信,或者是 完全不相信

如果說任何調(diào)查結(jié)果都不可能完全準確,先驗知識或主觀概率也不是完全可以相信的,那么貝葉斯決策則巧妙地將這兩種信息有機地結(jié)合起來了

它可以在決策過程中根據(jù)具體情況下不斷地使用,使決策逐步完善和更加科學(xué) 缺點：

它需要的數(shù)據(jù)多,分析計算比較復(fù)雜,特別在解決復(fù)雜問題時,這個矛盾就更為突出

有些數(shù)據(jù)必須使用主觀概率,有些人不太相信,這也妨礙了貝葉斯決策方法的推廣使用 ③貝葉斯決策改進方法

將決策問題轉(zhuǎn)化成收益矩陣,通過對收益矩陣的分析,得出各行動方案的期望值,按照一定的準則選出最優(yōu)方案。

以各狀況下最大收益值或效用值為基礎(chǔ),求出MaxE(x),以此作為完全確定情況下的收益值,用該值減去最優(yōu)方案的期望值得出完全信息價值(EVPⅠ),根據(jù)完全信息期望值判斷是否需要補充信息量。

在第2步得到肯定回答后,首先在預(yù)先后驗分析中從理論上把各種可能的抽樣方案及結(jié)果列舉出來,計算各種抽樣方案的抽樣信息期望值EVSI=EVPI-R(n),其中R(n)為抽樣風(fēng)險,其大小是樣本大小的函數(shù)。

以EVSI-C(其中C為抽樣成本)作為標準選取最大值對應(yīng)的抽樣方案為最優(yōu)抽樣方案。

按照理論上得出的最優(yōu)抽樣方案進行抽樣,然后,根據(jù)貝葉斯理論公式推導(dǎo)出后驗概率分布的數(shù)字描述,最后,以此為依據(jù)按照貝葉斯決策準則選出最優(yōu)方案。補充樸素貝葉斯

樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅實的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。

同時，NBC模型所需估計的參數(shù)很少，對缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是因為NBC模型假設(shè)屬性之間相互獨立，這個假設(shè)在實際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數(shù)比較多或者屬性之間相關(guān)性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關(guān)性較小時，NBC模型的性能最為良好。

補充樸素貝葉斯優(yōu)點：

1）樸素貝葉斯算法是基于貝葉斯理論，邏輯清楚明了

2）本算法進行分類是，時間快，在內(nèi)存上需要的也不大

3）本算法魯棒性高，即使數(shù)據(jù)包含的噪聲點，無關(guān)屬性和缺失值的屬性，分類性能不好又 太大的變化，健壯性好

補充樸素貝葉斯算法缺點：

1）樸素貝葉斯算法要求樣本各屬性直接是獨立的，而真實的數(shù)據(jù)符合這個條件很少。

2）當(dāng)樣本數(shù)據(jù)少時，分類器可能會無法正確分類

Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多層感知器)①算法思想

多層感知器（Multilayer Perceptron,縮寫MLP）是一種前向結(jié)構(gòu)的人工神經(jīng)網(wǎng)絡(luò)。MLP算法一般包括三層，分別是一個輸入層，一個輸出層和一個或多個隱藏層的神經(jīng)網(wǎng)絡(luò)組成。一個“神經(jīng)元”的輸出就可以是另一個“神經(jīng)元”的輸入。MLP可以被看作是一個有向圖，由多個的節(jié)點層所組成，每一層都全連接到下一層。除了輸入節(jié)點，每個神經(jīng)元都有幾個輸入和輸出神經(jīng)元，每個神經(jīng)元通過輸入權(quán)重加上偏置計算輸出值，并選擇一種激活函數(shù)進行轉(zhuǎn)換。一種被稱為反向傳播算法(BP)的監(jiān)督學(xué)習(xí)方法常被用來訓(xùn)練MLP。MLP是感知器的推廣，克服了感知器不能對線性不可分數(shù)據(jù)進行識別的弱點。

激活函數(shù)

若每個神經(jīng)元的激活函數(shù)都是線性函數(shù)，那么，任意層數(shù)的MLP都可被約簡成一個等價的單層感知器。實際上，MLP本身可以使用任何形式的激活函數(shù)，但為了使用反向傳播算法進行有效學(xué)習(xí)，激活函數(shù)必須限制為可微函數(shù)。由于具有良好可微性，很多乙形函數(shù)，尤其是雙曲正切函數(shù)（Hyperbolic tangent）及邏輯乙形函數(shù)（logistic sigmoid function），被采用為激活函數(shù)。激活函數(shù)常見的有三種，分別是恒等函數(shù)，Sigmoid函數(shù)和高斯函數(shù)。

②優(yōu)點：

（1）高度的并行性

人工神經(jīng)網(wǎng)絡(luò)是由許多相同的簡單處理單元并聯(lián)組合而成，雖然每個單元的功能簡單，但大量簡單單元的并行活動，使其對信息的處理能力與效果驚人。（2）高度的非線性全局作用

神經(jīng)網(wǎng)絡(luò)系統(tǒng)是由大量簡單神經(jīng)元構(gòu)成的，每個神經(jīng)元接受大量其他神經(jīng)元的輸入，通過非線性輸入、輸出關(guān)系，產(chǎn)生輸出影響其它神經(jīng)元。網(wǎng)絡(luò)就是這樣互相制約相互影響，實現(xiàn)從輸入狀態(tài)空間到輸出狀態(tài)空間非線性映射的。網(wǎng)絡(luò)的演化遵從全局性作用原則，從輸入狀態(tài)演化到終態(tài)而輸出。從全局觀點來看，網(wǎng)絡(luò)整體性能不是網(wǎng)絡(luò)局部性能的簡單迭加，而表現(xiàn)某種集體性行為；而電腦遵從串行式局域性操作原則，每一步計算與上一步計算緊密相關(guān)，并對下一步產(chǎn)生影響，問題是通過算法逐步進行處理的。（3）良好的容錯性與聯(lián)想記憶功能

人工神經(jīng)網(wǎng)絡(luò)通過自身的網(wǎng)絡(luò)結(jié)構(gòu)能夠?qū)崿F(xiàn)對信息的記憶，而所記憶的信息是存儲在神經(jīng)元之間的權(quán)值中。從單個權(quán)值中看不出所儲存的信息內(nèi)容，因而是分布式的存儲方式。這使得網(wǎng)絡(luò)具有良好的容錯性，并能進行聚類分析、特征提取、缺損模式復(fù)原等模式信息處理工作。

（4）十分強的自適應(yīng)、自學(xué)習(xí)功能人工神經(jīng)網(wǎng)絡(luò)可以通過訓(xùn)練和學(xué)習(xí)來獲得網(wǎng)絡(luò)的權(quán)值與結(jié)構(gòu)，呈現(xiàn)出很強的自學(xué)習(xí)能力和對環(huán)境的自適應(yīng)能力。③缺點

（1）網(wǎng)絡(luò)的隱含節(jié)點個數(shù)選取問題至今仍是一個 世界難題；

（2）停止閾值、學(xué)習(xí)率、動量常數(shù)需要采用”trial-and-error”法，極其耗時（動手實驗）；（3）學(xué)習(xí)速度慢；

（4）容易陷入局部極值，學(xué)習(xí)不夠充分。④改進

（1）改進BP算法（見bp）（2）權(quán)值初始化

在初始化權(quán)值的時候，我們一般需要它們在0附近，要足夠?。ㄔ诩せ詈瘮?shù)的近似線性區(qū)域可以獲得最大的梯度）。另一個特性，尤其對深度網(wǎng)絡(luò)而言，是可以減小層與層之間的激活函數(shù)的方差和反向傳導(dǎo)梯度的方差。這就可以讓信息更好的向下和向上的傳導(dǎo)，減少層間差異。（3）學(xué)習(xí)率

隨著時間的推移減小學(xué)習(xí)速率有時候也是一個好主意。一個簡單的方法是使用這個公式：u/(1+d*t)，u是初始速率（可以使用上面講的網(wǎng)格搜索選擇），d是減小常量，用以控制學(xué)習(xí)速率，可以設(shè)為0.001或者更小，t是迭代次數(shù)或者時間?？梢曰诜诸愬e誤率自適應(yīng)的選擇學(xué)習(xí)率。（4）隱藏節(jié)點數(shù) 這個參數(shù)是非?；跀?shù)據(jù)集的。模糊的來說就是，輸入分布越復(fù)雜，去模擬它的網(wǎng)絡(luò)就需要更大的容量，那么隱藏單元的數(shù)目就要更大。（5）正則化參數(shù)

典型的方法是使用L1/L2正則化。

L2正則化就是在代價函數(shù)后面再加上一個正則化項：

C0代表原始的代價函數(shù)，后面那一項就是L2正則化項，它是這樣來的：所有參數(shù)w的平方的和，除以訓(xùn)練集的樣本大小n。λ就是正則項系數(shù)，權(quán)衡正則項與C0項的比重。另外還有一個系數(shù)1/2，1/2經(jīng)常會看到，主要是為了后面求導(dǎo)的結(jié)果方便，后面那一項求導(dǎo)會產(chǎn)生一個2，與1/2相乘剛好湊整。

過擬合，就是擬合函數(shù)需要顧忌每一個點，最終形成的擬合函數(shù)波動很大。在某些很小的區(qū)間里，函數(shù)值的變化很劇烈。這就意味著函數(shù)在某些小區(qū)間里的導(dǎo)數(shù)值（絕對值）非常大，由于自變量值可大可小，所以只有系數(shù)足夠大，才能保證導(dǎo)數(shù)值很大。而正則化是通過約束參數(shù)的范數(shù)使其不要太大，所以可以在一定程度上減少過擬合情況。

L1正則化項就是在原始的代價函數(shù)后面加上一個正則化項，即所有權(quán)重w的絕對值的和，乘以λ/n（這里不像L2正則化項那樣）：

比原始的更新規(guī)則多出了η * λ * sgn(w)/n這一項。當(dāng)w為正時，更新后的w變小。當(dāng)w為負時，更新后的w變大——因此它的效果就是讓w往0靠，使網(wǎng)絡(luò)中的權(quán)重盡可能為0，也就相當(dāng)于減小了網(wǎng)絡(luò)復(fù)雜度，防止過擬合。

（2）BP Algorithm ①算法思想

BP算法是一種有監(jiān)督式的學(xué)習(xí)算法，其主要思想是：輸入學(xué)習(xí)樣本，使用反向傳播算法對網(wǎng)絡(luò)的權(quán)值和偏差進行反復(fù)的調(diào)整訓(xùn)練，使輸出的向量與期望向量盡可能地接近，當(dāng)網(wǎng)絡(luò)輸出層的誤差平方和小于指定的誤差時訓(xùn)練完成，保存網(wǎng)絡(luò)的權(quán)值和偏差。②優(yōu)點：

（1）網(wǎng)絡(luò)實質(zhì)上實現(xiàn)了一個從輸入到輸出的映射功能，而數(shù)學(xué)理論已證明它具有實現(xiàn)任何復(fù)雜非線性映射的功能。這使得它特別適合于求解內(nèi)部機制復(fù)雜的問題；

（2）網(wǎng)絡(luò)能通過學(xué)習(xí)帶正確答案的實例集自動提取“合理的”求解規(guī)則，即具有自學(xué)習(xí)能力；（3）網(wǎng)絡(luò)具有一定的推廣、概括能力。③缺點

主要包括以下幾個方面的問題。

（1）由于學(xué)習(xí)速率是固定的，因此網(wǎng)絡(luò)的收斂速度慢，需要較長的訓(xùn)練時間。對于一些復(fù)雜問題，BP算法需要的訓(xùn)練時間可能非常長，這主要是由于學(xué)習(xí)速率太小造成的。

（2）BP算法可以使權(quán)值收斂到某個值，但并不保證其為誤差平面的全局最小值，這是因為采用梯度下降法可能產(chǎn)生一個局部最小值

（3）網(wǎng)絡(luò)隱含層的層數(shù)和單元數(shù)的選擇尚無理論上的指導(dǎo)，一般是根據(jù)經(jīng)驗或者通過反復(fù)實驗確定。因此，網(wǎng)絡(luò)往往存在很大的冗余性，在一定程度上也增加了網(wǎng)絡(luò)學(xué)習(xí)的負擔(dān)。

（4）網(wǎng)絡(luò)的學(xué)習(xí)和記憶具有不穩(wěn)定性。也就是說，如果增加了學(xué)習(xí)樣本，訓(xùn)練好的網(wǎng)絡(luò)就需要從頭開始訓(xùn)練，對于以前的權(quán)值和閾值是沒有記憶的。但是可以將預(yù)測、分類或聚類做的比較好的權(quán)值保存。

（5）網(wǎng)絡(luò)的預(yù)測能力（也稱泛化能力、推廣能力）與訓(xùn)練能力（也稱逼近能力、學(xué)習(xí)能力）的矛盾。一般情況下，訓(xùn)練能力差時，預(yù)測能力也差，并且一定程度上，隨訓(xùn)練能力地提高，預(yù)測能力也提高。但這種趨勢有一個極限，當(dāng)達到此極限時，隨訓(xùn)練能力的提高，預(yù)測能力反而下降，即出現(xiàn)所謂“過擬合”現(xiàn)象。此時，網(wǎng)絡(luò)學(xué)習(xí)了過多的樣本細節(jié)，而不能反映樣本內(nèi)含的規(guī)律。（6）網(wǎng)絡(luò)訓(xùn)練失敗的可能性較大，其原因有：

a 從數(shù)學(xué)角度看，BP算法為一種局部搜索的優(yōu)化方法，但它要解決的問題為求解復(fù)雜非線性函數(shù)的全局極值，因此，算法很有可能陷入局部極值，使訓(xùn)練失??；

b 網(wǎng)絡(luò)的逼近、推廣能力同學(xué)習(xí)樣本的典型性密切相關(guān)，而從問題中選取典型樣本實例組成訓(xùn)練集是一個很困難的問題。④改進.變步長法

BP算法的有效性和收斂性在很大程度上取決于學(xué)習(xí)步長η的值。采用一般的固定長梯度下降法求解時,起碼可能導(dǎo)致兩個主要問題:局部極小解;收斂速度慢。所以,一般要求是,當(dāng)訓(xùn)練到誤差曲面的平坦區(qū)時,梯度較小,為加快收斂應(yīng)使η增大;當(dāng)訓(xùn)練到深而窄的誤差曲面時,應(yīng)使η減小,以免因步長過大而出現(xiàn)振蕩現(xiàn)象。為加快收斂,應(yīng)使η合理化,可采用變步長算法。變步長算法的基本思想是,先設(shè)一個初始步長η,若一次迭代后誤差增大,則將步長乘以β(<1),沿原方向重新計算該迭代點;若一次迭代后誤差減小,則將步長乘以α(>1),計算下一個迭代點,以縮短學(xué)習(xí)時間。2.加動量項法

為了加速BP算法的收斂,可考慮在權(quán)值調(diào)整算式中加入動量項,即

式中,α為動量因子,一般取0.1～0.8。這時權(quán)值修正量加上了有關(guān)上一時刻權(quán)值修改方向的記憶,加速了網(wǎng)絡(luò)的收斂。加動量項法的具體原理:若相鄰兩次迭代點處的梯度方向是一致的,引入動量項可使權(quán)值的調(diào)整量增大,從而加速收斂;若相鄰兩次迭代點處的梯度方向相反,引入動量項可使權(quán)值的調(diào)整量減小,避免了來回振蕩,加快了收斂。3.串連法

BP算法的收斂速度主要取決于輸入-輸出模式間非線性映射的復(fù)雜程度。顯然,這種非線性映射關(guān)系越復(fù)雜,收斂時間越長。因此,對那些高度復(fù)雜的非線性問題,用兩個串連的BP網(wǎng)絡(luò)代替一個BP網(wǎng)絡(luò),能夠有效地縮短訓(xùn)練時間。4.利用遺傳算法優(yōu)化BP算法

BP算法的優(yōu)點是尋優(yōu)具有精確性,但它易陷入局部極小、收斂速度慢,而遺傳算法(GeneticAlgorithm,GA)是基于自然選擇和遺傳規(guī)律的全局優(yōu)化搜索算法,具有很強的宏觀搜索能力和尋優(yōu)全局性。因此,在BP神經(jīng)網(wǎng)絡(luò)理論中引入遺傳算法的思想,則可以很好地達到全局尋優(yōu)和快速高效的目的。

Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量機)（此算法是重點，必考題）

①算法思想

SVM的主要思想是針對兩類分類問題，尋找一個超平面作為兩類訓(xùn)練樣本點的分割，以保證最小的分類錯誤率。在線性可分的情況下，存在一個或多個超平面使得訓(xùn)練樣本完全分開，SVM的目標是找到其中的最優(yōu)超平面，最優(yōu)超平面是使得每一類數(shù)據(jù)與超平面距離最近的向量與超平面之間的距離最大的這樣的平面，對于線性不可分的情況，通過使用核函數(shù)（一種非線性映射算法）將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分。②優(yōu)點

（1）小樣本，并不是說樣本的絕對數(shù)量少（實際上，對任何算法來說，更多的樣本幾乎總是能帶來更好的效果），而是說與問題的復(fù)雜度比起來，SVM算法要求的樣本數(shù)是相對比較少的。

（2）非線性，是指SVM擅長應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過松弛變量（也有人叫懲罰變量）和核函數(shù)技術(shù)來實現(xiàn)，（3）高維模式識別是指樣本維數(shù)很高，例如文本的向量表示，如果沒有經(jīng)過降維處理，出現(xiàn)幾萬維的情況很正常，其他算法基本就沒有能力應(yīng)付了，SVM卻可以，主要是因為SVM 產(chǎn)生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本，此為后話），使得即使樣本維數(shù)很高，也不會給存儲和計算帶來大麻煩（相對照而言，kNN算法在分類時就要用到所有樣本，樣本數(shù)巨大，每個樣本維數(shù)再一高，這日子就沒法過了??）。③缺點

（1）SVM算法對大規(guī)模訓(xùn)練樣本難以實施 由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的計算（m為樣本的個數(shù)），當(dāng)m數(shù)目很大時該矩陣的存儲和計算將耗費大量的機器內(nèi)存和運算時間。（2）用SVM解決多分類問題存在困難 ④改進：

經(jīng)典的支持向量機算法只給出了二類分類的算法，而在數(shù)據(jù)挖掘的實際應(yīng)用中，一般要解決多類的分類問題?？梢酝ㄟ^多個二類支持向量機的組合來解決。主要有

一對多組合模式、一對一組合模式和SVM決策樹； 再就是通過構(gòu)造多個分類器的組合來解決。

主要原理是克服SVM固有的缺點，結(jié)合其他算法的優(yōu)勢，解決多類問題的分類精度。如：

與粗集理論結(jié)合，形成一種優(yōu)勢互補的多類問題的組合分類器。此處有一道必考題

Lecture 4 Introduction to Decision Rule Mining（1）ID3 Algorithm ①算法思想：

補充：

ID3算法（Iterative Dichotomiser 3 迭代二叉樹3代）是一個由Ross Quinlan發(fā)明的用于決策樹的算法。這個算法便是：

從信息論知識中我們知道，期望信息越小，信息增益越大，從而純度越高。ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。

所以，ID3的思想便是：

自頂向下的貪婪搜索遍歷可能的決策樹空間構(gòu)造決策樹(此方法是ID3算法和C4.5算法的基礎(chǔ))； 從“哪一個屬性將在樹的根節(jié)點被測試”開始；

使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的能力，分類能力最好的屬性作為樹的根結(jié)點測試(如何定義或者評判一個屬性是分類能力最好的呢？這便是下文將要介紹的信息增益，or 信息增益率)。

然后為根結(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Вㄒ簿褪钦f，樣例的該屬性值對應(yīng)的分支）之下。重復(fù)這個過程，用每個分支結(jié)點關(guān)聯(lián)的訓(xùn)練樣例來選取在該點被測試的最佳屬性。

②優(yōu)點：

（1）分類精度高；

（2）實現(xiàn)比較簡單，產(chǎn)生的規(guī)則如果用圖表示出來的話，清晰易懂；

優(yōu)點補充：

（4）ID3算法的假設(shè)空間包含了所有的決策樹，不存在無解風(fēng)險

（5）ID3算法非常適合處理離散樣本數(shù)據(jù)，利用屬性結(jié)果提取分類規(guī)則，且容易理解（6）引進了信息論的中的熵，使得算法得到結(jié)點最少的決策樹 ③缺點：

（1）ID3算法往往偏向于選擇取值較多的屬性，而在很多情況下取值較多的屬性并不總是最重要的屬性，即按照使熵值最小的原則被ID3算法列為應(yīng)該首先判斷的屬性在現(xiàn)實情況中卻并不一定非常重要。例如：在銀行客戶分析中，姓名屬性取值多，卻不能從中得到任何信息。（簡略寫：由于使用信息增益，會在屬性選擇時偏向選擇取值多的屬性）

（2）ID3算法對于噪聲數(shù)據(jù)敏感，ID3算法不能處理具有連續(xù)值的屬性，也不能處理具有缺失數(shù)據(jù)的屬性。

（3）用互信息作為選擇屬性的標準存在一個假設(shè)，即訓(xùn)練子集中的正、反例的比例應(yīng)與實際問題領(lǐng)域中正、反例的比例一致。一般情況很難保證這兩者的比例一致，這樣計算訓(xùn)練集的互信息就會存在偏差。

（4）在建造決策樹時，每個結(jié)點僅含一個屬性，是一種單變元的算法，致使生成的決策樹結(jié)點之間的相關(guān)性不夠強。雖然在一棵樹上連在一起，但聯(lián)系還是松散的。

（5）ID3算法雖然理論清晰，但計算比較復(fù)雜，在學(xué)習(xí)和訓(xùn)練數(shù)據(jù)集的過程中機器內(nèi)存占用率比較大，耗費資源。（計算復(fù)雜，有很多對數(shù)計算）

（6）ID3不夠健壯，當(dāng)有一個項數(shù)據(jù)有改變時，整棵樹的結(jié)構(gòu)可能改變很大。

改進：用R-C4.5的思想，在進行測試屬性選擇時，合并分類貢獻小的分支，避免出現(xiàn)過細的分枝，提高樹的健壯性。補充：

（7）當(dāng)訓(xùn)練集增加或減少的時候，決策樹都會隨之改變，對漸進學(xué)習(xí)不方便。

④改進：（1）對決策樹進行剪枝。可以采用交叉驗證法和加入正則化的方法。

（2）使用基于決策樹的combination算法，如bagging算法，randomforest算法，可以解決過擬合的問題（3）引入用戶興趣度

給定a(0≤a≤1)為用戶對不確定知識的興趣度，a的大小由決策者根據(jù)先驗知識或領(lǐng)域知識來確定。它是一個模糊的概念，通常指關(guān)于某一事務(wù)的先驗知識，包括領(lǐng)域知識和專家建議，具體到?jīng)Q策樹學(xué)習(xí)中則是指在決策樹訓(xùn)練過程中除了用于生成和修改決策樹的實例集之外的所有影響決策樹規(guī)則生成和選擇的因素。

（2）C4.5 Algorithm 補充：

既然說C4.5算法是ID3的改進算法，那么C4.5相比于ID3改進的地方有哪些呢？

用信息增益率來選擇屬性。ID3選擇屬性用的是子樹的信息增益，這里可以用很多方法來定義信息，ID3使用的是熵(entropy，熵是一種不純度度量準則),也就是熵的變化值，而C4.5用的是信息增益率。對，區(qū)別就在于一個是信息增益，一個是信息增益率。（因此，C4.5克服了ID3用信息增益選擇屬性時偏向選擇取值多的屬性的不足。）在樹構(gòu)造過程中進行剪枝，在構(gòu)造決策樹的時候，那些掛著幾個元素的節(jié)點，不考慮最好，不然容易導(dǎo)致overfitting。對非離散數(shù)據(jù)也能處理。能夠?qū)Σ煌暾麛?shù)據(jù)進行處理 ①算法思想：

②優(yōu)點：

（1）產(chǎn)生的分類規(guī)則易于理解，準確率較高。（2）對非離散數(shù)據(jù)也能處理。

C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點上的分枝屬性時，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個數(shù)進行計算；對于某個連續(xù)性描述屬性Ac，假設(shè)在某個結(jié)點上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理。

1）將該結(jié)點上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進行排序，得到屬性值的取值序列{A1c，A2c，??Atotalc}。

2）在取值序列中生成total-1個分割點。第i（0

3）從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分數(shù)據(jù)集的方式，C4.5計算它的信息增益比，并且從中選擇信息增益比最大的分割點來劃分數(shù)據(jù)集。（3）能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。

在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如〈x，c(x)〉是樣本集S中的一個訓(xùn)練實例，但是其屬 性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略是賦給它結(jié)點n所對應(yīng)的訓(xùn)練實例中該屬性的最常見值；另外一種更復(fù)雜的策略是為A的每個可能值賦予一個概率。例如，給定一個布爾屬性A，如果結(jié)點n包含6個已知A=1和4個A=0的實例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例（fractional examples）的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進一步細分。C4.5就是使用這種方法處理缺少的屬性值。（4）克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足。（5）采用了一種后剪枝方法

避免樹的高度無節(jié)制的增長，避免過度擬合數(shù)據(jù)，該方法使用訓(xùn)練樣本集本身來估計剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下：

其中N是實例的數(shù)量，f=E/N為觀察到的誤差率（其中E為N個實例中分類錯誤的個數(shù)），q為真實的誤差率，c為置信度（C4.5算法的一個輸入?yún)?shù)，默認值為0.25），z為對應(yīng)于置信度c的標準差，其值可根據(jù)c的設(shè)定值通過查正態(tài)分布表得到。通過該公式即可計算出真實誤差率q的一個置信度上限，用此上限為該節(jié)點誤差率e做一個悲觀的估計：

通過判斷剪枝前后e的大小，從而決定是否需要剪枝。

樹剪枝

在決策樹的創(chuàng)建時，由于數(shù)據(jù)中的噪聲和離群點，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝方法是用來處理這種過分擬合數(shù)據(jù)的問題。通常剪枝方法都是使用統(tǒng)計度量，剪去最不可靠的分枝。

剪枝一般分兩種方法：先剪枝和后剪枝。

先剪枝方法中通過提前停止樹的構(gòu)造（比如決定在某個節(jié)點不再分裂或劃分訓(xùn)練元組的子集）而對樹剪枝。一旦停止，這個節(jié)點就變成樹葉，該樹葉可能取它持有的子集最頻繁的類作為自己的類。先剪枝有很多方法，比如（1）當(dāng)決策樹達到一定的高度就停止決策樹的生長；（2）到達此節(jié)點的實例具有相同的特征向量，而不必一定屬于同一類，也可以停止生長（3）到達此節(jié)點的實例個數(shù)小于某個閾值的時候也可以停止樹的生長，不足之處是不能處理那些數(shù)據(jù)量比較小的特殊情況（4）計算每次擴展對系統(tǒng)性能的增益，如果小于某個閾值就可以讓它停止生長。先剪枝有個缺點就是視野效果問題，也就是說在相同的標準下，也許當(dāng)前擴展不能滿足要求，但更進一步擴展又能滿足要求。這樣會過早停止決策樹的生長。

另一種更常用的方法是后剪枝，它由完全成長的樹剪去子樹而形成。通過刪除節(jié)點的分枝并用樹葉來替換它。樹葉一般用子樹中最頻繁的類別來標記。

C4.5采用悲觀剪枝法，它使用訓(xùn)練集生成決策樹又用它來進行剪枝，不需要獨立的剪枝集。

悲觀剪枝法的基本思路是：設(shè)訓(xùn)練集生成的決策樹是T，用T來分類訓(xùn)練集中的N的元組，設(shè)K為到達某個葉子節(jié)點的元組個數(shù)，其中分類錯誤地個數(shù)為J。由于樹T是由訓(xùn)練集生成的，是適合訓(xùn)練集的，因此J/K不能可信地估計錯誤率。所以用(J+0.5)/K來表示。設(shè)S為T的子樹，其葉節(jié)點個數(shù)為L(s)，個數(shù)總和，為到達此子樹的葉節(jié)點的元組 為此子樹中被錯誤分類的元組個數(shù)之和。在分類新的元組時，則其錯誤分類個數(shù)為，其標準錯誤表示為：。當(dāng)用此樹分類訓(xùn)練集時，設(shè)E為分類錯誤個數(shù)，當(dāng)下面的式子成立時，則刪掉子樹S，用葉節(jié)點代替，且S的子樹不必再計算。

③缺點：

（1）構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。

（2）C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。（3）在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。④改進：

（1）SLIQ算法

SLIQ算法對C4.5決策樹分類算法的實現(xiàn)方法進行了改進，在決策樹的構(gòu)造過程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。

1)預(yù)排序。對于連續(xù)屬性在每個內(nèi)部結(jié)點尋找其最優(yōu)分裂標準時，都需要對訓(xùn)練集按照該屬性的取值進行排序，而排序是很浪費時間的操作。為此，SLIQ算法 采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對每個屬性的取值，把所有的記錄按照從小到大的順序進行排序，以消除在決策樹的每個結(jié)點對數(shù)據(jù)集進行的排序。具體實 現(xiàn)時，需要為訓(xùn)練數(shù)據(jù)集的每個屬性創(chuàng)建一個屬性列表，為類別屬性創(chuàng)建一個類別列表。

2)廣度優(yōu)先策略。在C4.5算法中，樹的構(gòu)造是按照深度優(yōu)先策略完成的，需要對每個屬性列表在每個結(jié)點處都進行一遍掃描，費時很多，為此，SLIQ采用 廣度優(yōu)先策略構(gòu)造決策樹，即在決策樹的每一層只需對每個屬性列表掃描一次，就可以為當(dāng)前決策樹中每個葉子結(jié)點找到最優(yōu)分裂標準。

SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠處理比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個數(shù)和屬性個數(shù)增長的可伸縮性。

然而它仍然存在如下缺點：

1)由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。

2)由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能達到隨記錄數(shù)目增長的線性可伸縮性。（2）SPRINT算法

為了減少駐留于內(nèi)存的數(shù)據(jù)量，SPRINT算法進一步改進了決策樹算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個 屬性列表中。這樣，在遍歷每個屬性列表尋找當(dāng)前結(jié)點的最優(yōu)分裂標準時，不必參照其他信息，將對結(jié)點的分裂表現(xiàn)在對屬性列表的分裂，即將每個屬性列表分成兩 個，分別存放屬于各個結(jié)點的記錄。

SPRINT算法的優(yōu)點是在尋找每個結(jié)點的最優(yōu)分裂標準時變得更簡單。其缺點是對非分裂屬性的屬性列表進行分裂變得很困難。解決的辦法是對分裂屬性進行分 裂時用哈希表記錄下每個記錄屬于哪個孩子結(jié)點，若內(nèi)存能夠容納下整個哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成 正比，當(dāng)訓(xùn)練集很大時，哈希表可能無法在內(nèi)存容納，此時分裂只能分批執(zhí)行，這使得SPRINT算法的可伸縮性仍然不是很好。

（3）隨機森林(Random Forest)（對C4.5,ID3改進，提高準確率）

隨機森林是一個最近比較火的算法，它有很多的優(yōu)點： 在數(shù)據(jù)集上表現(xiàn)良好

在當(dāng)前的很多數(shù)據(jù)集上，相對其他算法有著很大的優(yōu)勢

它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇 在訓(xùn)練完后，它能夠給出哪些feature比較重要

在創(chuàng)建隨機森林的時候，對generlization error使用的是無偏估計 訓(xùn)練速度快

在訓(xùn)練過程中，能夠檢測到feature間的互相影響 容易做成并行化方法 實現(xiàn)比較簡單

隨機森林顧名思義，是用隨機的方式建立一個森林，森林里面有很多的決策樹組成，隨機森林的每一棵決策樹之間是沒有關(guān)聯(lián)的。在得到森林之后，當(dāng)有一個新的輸入樣本進入的時候，就讓森林中的每一棵決策樹分別進行一下判斷，看看這個樣本應(yīng)該屬于哪一類（對于分類算法），然后看看哪一類被選擇最多，就預(yù)測這個樣本為那一類。在建立每一棵決策樹的過程中，有兩點需要注意 – 采樣與完全分裂。首先是兩個隨機采樣的過程，random forest對輸入的數(shù)據(jù)要進行行、列的采樣。對于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個，那么采樣的樣本也為N個。這樣使得在訓(xùn)練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現(xiàn)over-fitting。然后進行列采樣，從M個feature中，選擇m個(m << M)。之后就 是對采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節(jié)點要么是無法繼續(xù)分裂的，要么里面的所有樣本的都是指向的同一個分類。一般很多的決策樹算法都一個重要的步驟 – 剪枝，但是這里不這樣干，由于之前的兩個隨機采樣的過程保證了隨機性，所以就算不剪枝，也不會出現(xiàn)over-fitting。

按這種算法得到的隨機森林中的每一棵都是很弱的，但是大家組合起來就很厲害了。我覺得可以這樣比喻隨機森林算法：每一棵決策樹就是一個精通于某一個窄領(lǐng)域的專家（因為我們從M個feature中選擇m讓每一棵決策樹進行學(xué)習(xí)），這樣在隨機森林中就有了很多個精通不同領(lǐng)域的專家，對一個新的問題（新的輸入數(shù)據(jù)），可以用不同的角度去看待它，最終由各個專家，投票得到結(jié)果。隨機森林的過程請參考Mahout的random forest。這個頁面上寫的比較清楚了，其中可能不明白的就是Information Gain，可以看看之前推薦過的Moore的頁面。

Lecture 5 Classifier Assessment and Ensemble Methods

1、bagging bagging是一種用來提高學(xué)習(xí)算法準確度的方法，這種方法通過構(gòu)造一個預(yù)測函數(shù)系列，然后以一定的方式將它們組合成一個預(yù)測函數(shù)。? 基本思想

1.給定一個弱學(xué)習(xí)算法,和一個訓(xùn)練集;2.單個弱學(xué)習(xí)算法準確率不高;3.將該學(xué)習(xí)算法使用多次,得出預(yù)測函數(shù)序列,進行投票;4.最后結(jié)果準確率將得到提高.Bagging要求“不穩(wěn)定”（不穩(wěn)定是指數(shù)據(jù)集的小的變動能夠使得分類結(jié)果的顯著的變動）的分類方法。比如：決策樹，神經(jīng)網(wǎng)絡(luò)算法

2、Booting Boosting方法是一種用來提高弱分類算法準確度的方法,這種方法通過構(gòu)造一個預(yù)測函數(shù)系列,然后以一定的方式將他們組合成一個預(yù)測函數(shù)。Boosting是一種提高任意給定學(xué)習(xí)算法準確度的方法。他是一種框架算法,主要是通過對樣本集的操作獲得樣本子集,然后用弱分類算法在樣本子集上訓(xùn)練生成一系列的基分類器。可以用來提高其他弱分類算法的識別率。

? Bagging與Boosting的區(qū)別

二者的主要區(qū)別是取樣方式不同。Bagging采用均勻取樣，而Boosting根據(jù)錯誤率來取樣，因此Boosting的分類精度要優(yōu)于Bagging。Bagging的訓(xùn)練集的選擇是隨機的，各輪訓(xùn)練集之間相互獨立，而Boostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)；Bagging的各個預(yù)測函數(shù)沒有權(quán)重，而Boosting是有權(quán)重的；Bagging的各個預(yù)測函數(shù)可以并行生成，而Boosting的各個預(yù)測函數(shù)只能順序生成。對于象神經(jīng)網(wǎng)絡(luò)這樣極為耗時的學(xué)習(xí)方法。Bagging可通過并行訓(xùn)練節(jié)省大量時間開銷。

bagging和boosting都可以有效地提高分類的準確性。在大多數(shù)數(shù)據(jù)集中，boosting的準確性比bagging高。在有些數(shù)據(jù)集中，boosting會引起退化---Overfit。

Boosting思想的一種改進型AdaBoost方法在郵件過濾、文本分類方面都有很好的性能。

3、Adaboost(Adaptive Boosting)? 算法簡介

Adaboost是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強的最終分類器(強分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來，作為最后的決策分類器。使用adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。? 算法分析

該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能力。整個過程如下所示：

1.先通過對N個訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器； 2.將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器 ； 3.將1和2都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第三個弱分類器；

4.最終經(jīng)過提升的強分類器。即某個數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定。

? 算法優(yōu)點： 高精度；簡單，無需做特征篩選；可以使用各種方法構(gòu)建子分類器，Adaboost算法提供的是框架；當(dāng)使用簡單分類器時，計算出的結(jié)果是可以理解的，而且弱分類器構(gòu)造極其簡單；不會過度擬合。

對于boosting算法，存在兩個問題：

1.如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進行； 2.如何將訓(xùn)練得到的各個弱分類器聯(lián)合起來形成強分類器。針對以上兩個問題，Adaboost算法進行了調(diào)整：

1.使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上； 2.將弱分類器聯(lián)合起來，使用加權(quán)的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。

與Boosting算法不同的是，Adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。

? 算法缺點： 訓(xùn)練時間過長，執(zhí)行效果依賴于弱分類器的選擇。對噪聲數(shù)據(jù)和離群值敏感。? 改進：限制樣本權(quán)重的調(diào)整在各目標類內(nèi)部進行

1、權(quán)值更新方法的改進

Allende等人提出了RADA算法，該算法是對原算法中誤分類樣本權(quán)值抑制的方法。算法最突出的貢獻有三點：第一點是對的抑制，第二點，用當(dāng)前層分類器來判斷樣本是否分類正

確，而非原算法中的當(dāng)前弱分類器，第三點，增加 age變量記錄誤分類情況，并作了閾值限制，這里有效緩解了過擬合的問題。RADA 比傳統(tǒng) AdaBoost 算法更加穩(wěn)定，有效解決了誤分類樣本權(quán)值偏高的問題。

2、訓(xùn)練方法的改進

Merler等人提出了AdaBoost的并行計算方法P-AdaBoost算法。其主要思想是，將AdaBoost訓(xùn)練過程分為兩個階段，第一階段和原算法一樣，經(jīng)過多輪訓(xùn)練，獲得一個較為可靠的樣本分布ωi(s)，第二階段采用并行方法提高訓(xùn)練效率，訓(xùn)練中不再對樣本權(quán)值進行更新，而統(tǒng)一采用ωi(s)，最后輸出為。

采用這種方法能大大減少訓(xùn)練成本，與原算法相比，多了S 輪的樣本分布初始化工作，并且避免了差樣本因多次分類而造成權(quán)值過大的問題。

3、多算法結(jié)合的改進

Yunlong提出了EAdaBoost算法，是AdaBoost結(jié)合k近鄰算法的產(chǎn)物。AdaBoost算法具有高度擬合的特點，噪聲會對訓(xùn)練產(chǎn)生很大的影響，Yunlong等人在AdaBoost算法的基礎(chǔ)之上加入了kNN算法，對噪聲樣本進行了有效處理，提高了算法的精確度。EAdaBoost算法的主要過程如下：

(a)準備訓(xùn)練樣本，對樣本權(quán)值進行初始化。(b)計算訓(xùn)練誤差，并挑選最優(yōu)的弱分類器。(c)更新樣本權(quán)值。

(d)用 KNN 算法排除噪聲樣本，將權(quán)值設(shè)為 0。

該算法中有兩個非常關(guān)鍵的問題，什么樣的樣本稱為噪聲樣本和每次要處理多少個噪聲樣本的問題，原文中稱之為 suspect sample，算法中取的是那種難于學(xué)習(xí)、讓分類器出錯過多的樣本。

4、綜合方法的改進

Rong Xiao等人提出了Boosting Chain算法，用鏈表的方式來組織分類器，算法先用boosting特征快速排除 大量非人臉窗口，再用boosting chain和SVM分類器進行再判別，實驗效果相比FloatBoost還要略好。

Adaboosting

Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms ①算法思想：Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項集”用于搜索“K項集”。首先，找出頻繁“1項集”的集合，該集合記作L1。L1用于找頻繁“2項集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項集”。找每個Lk都需要一次數(shù)據(jù)庫掃描。

一、挖掘步驟：

1.依據(jù)支持度找出所有頻繁項集（頻度）2.依據(jù)置信度產(chǎn)生關(guān)聯(lián)規(guī)則（強度）二、一些定義： 對于A->B ①支持度：P(A∩B)，既有A又有B的概率

②置信度：P(B|A)，在A發(fā)生的事件中同時發(fā)生B的概率p(AB)/P(A)③如果事件A中包含k個元素，那么稱這個事件A為k項集事件A滿足最小支持度閾值的事件稱為頻繁k項集。④同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強規(guī)則。⑤候選集：通過向下合并得出的項集。

⑥頻繁集：支持度大于等于特定的最小支持度（Minimum Support/minsup）的項集。注意，頻繁集的子集一定是頻繁集。核心思想：連接步和剪枝步。連接步是自連接，原則是保證前k-2項相同，并按照字典順序連接。剪枝步，是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。簡單的講，1、發(fā)現(xiàn)頻繁項集，過程為（1）掃描（2）計數(shù)（3）比較（4）產(chǎn)生頻繁項集（5）連接、剪枝，產(chǎn)生候選項集，重復(fù)步驟（1）~（5）直到不能發(fā)現(xiàn)更大的頻集

2、產(chǎn)生關(guān)聯(lián)規(guī)則，過程為:根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對于每個頻繁項集L，產(chǎn)生L的所有非空子集；（2）對于L的每個非空子集S，如果 P（L）/P（S）≧minsup 則輸出規(guī)則“SàL-S”

注：L-S表示在項集L中除去S子集的項集

②優(yōu)點： Apriori（先驗的，推測的）算法應(yīng)用廣泛，可用于消費市場價格分析，猜測顧客的消費習(xí)慣；網(wǎng)絡(luò)安全領(lǐng)域中的入侵檢測技術(shù)；可用在用于高校管理中，根據(jù)挖掘規(guī)則可以有效地輔助學(xué)校管理部門有針對性的開展貧困助學(xué)工作；也可用在移動通信領(lǐng)域中，指導(dǎo)運營商的業(yè)務(wù)運營和輔助業(yè)務(wù)提供商的決策制定。

③缺點：此算法的的應(yīng)用非常廣泛，但是他在運算的過程中會產(chǎn)生大量的侯選集，而且在匹配的時候要進行整個數(shù)據(jù)庫的掃描（重復(fù)掃描），因為要做支持度計數(shù)的統(tǒng)計操作，在小規(guī)模的數(shù)據(jù)上操作還不會有大問題，如果是大型的數(shù)據(jù)庫上呢，他的效率還是有待提高的。④改進：

方法

一、Apriori優(yōu)化：Fp-tree 算法

關(guān)鍵點：以樹形的形式來展示、表達數(shù)據(jù)的形態(tài)；可以理解為水在不同河流分支的流動過程； 生成Fp-tree的幾個點： 1.掃描原始項目集； 2.排列數(shù)據(jù)；

3.創(chuàng)建ROOT節(jié)點；

4.按照排列的數(shù)據(jù)進行元素的流動； 5.節(jié)點+1；

方法

二、Apriori優(yōu)化：垂直數(shù)據(jù)分布

關(guān)鍵點：相當(dāng)于把原始數(shù)據(jù)進行行轉(zhuǎn)列的操作，并且記錄每個元素的個數(shù) Lecture 6有5種改進方法：

1.基于哈希的項集數(shù)：小于閾值的哈希桶數(shù)的k項集不是頻繁的

2.縮減事務(wù)：在子頻繁集中掃描時，不包含任何k項頻繁集的事務(wù)是無用的 3.劃分DB：DB中的任何頻繁項集在部分DB中也一定是頻繁的 4.采樣：用一個小的支持閾值和方法挖掘給定數(shù)據(jù)的子集

5.動態(tài)規(guī)劃項集數(shù)：只有當(dāng)他們的所有子集預(yù)計為頻繁時才添加一個新的候選項（1）基于hash的方法?；诠５乃惴ㄈ允菍⑺兴袛?shù)據(jù)放入內(nèi)存的方法。只要在計算的過程中能夠滿足算法對內(nèi)存的大量需求，針對C2候選項對過大，一些算法提出用來減少C2的大小。這里我們首先考慮PCY算法，這個算法使用了在Apriori算法的第一步里大量沒使用的內(nèi)存。接著，我們考慮Multistage（多步哈希）算法，這個算法使用PCY的技巧，但插入了額外的步驟來更多的減少C2的大小。類似的還有Multihash。

（2）基于劃分的方法。Savasere等設(shè)計了一個基于劃分(partition)的算法.這個算法先把數(shù)據(jù)庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來生成所有可能的頻集，最后計算這些項集的支持度。這里分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻集至少在某一個分塊中是頻集保證的。

（3）基于采樣的方法?；谇耙槐閽呙璧玫降男畔?，對此仔細地作組合分析，可以得到一個改進的算法，Mannila等先考慮了這一點，他們認為采樣是發(fā)現(xiàn)規(guī)則的一個有效途徑。

（2）FP-tree Algorithms ①算法思想：

參考http://blog.csdn.net/sealyao/article/details/6460578 FP-tree 在不生成候選項的情況下，完成Apriori算法的功能。通過合并一些重復(fù)路徑，實現(xiàn)了數(shù)據(jù)的壓縮，從而使得將頻繁項集加載到內(nèi)存中成為可能。之后以樹遍歷的操作，替代了 Apriori 算法中最耗費時間的事務(wù)記錄遍歷，從而大大提高了運算效率。算法步驟如下：

1.掃描一遍數(shù)據(jù)庫，刪除頻率小于最小支持度的項，并降序排列。并將每個事務(wù)中的項都要按照這個順序進行排列。處理后的數(shù)據(jù)庫記錄為：

2.構(gòu)建 FP-Tree，把每個事務(wù)中的數(shù)據(jù)項按降序依次插入到一棵以NULL為根結(jié)點的樹中，同時在每個結(jié)點處記錄該結(jié)點出現(xiàn)的支持度。如果插入時頻繁項節(jié)點已經(jīng)存在了，則把該頻繁項節(jié)點支持度加1；如果該節(jié)點不存在，則創(chuàng)建支持度為1的節(jié)點，并把該節(jié)點鏈接到項頭表中。

3.求出每個節(jié)點的條件模式基

4.為每個節(jié)點建立FP-Tree

5.遞歸 調(diào)用FP-growth(Tree，null)開始進行挖掘。偽代碼如下： procedure FP_growth(Tree, a)if Tree 含單個路徑P then{

for 路徑P中結(jié)點的每個組合（記作b）

產(chǎn)生模式b U a，其支持度support = b 中結(jié)點的最小支持度； } else {

for each a i 在Tree的頭部(按照支持度由低到高順序進行掃描){ 產(chǎn)生一個模式b = a i U a，其支持度support = a i-support；

構(gòu)造b的條件模式基，然后構(gòu)造b的條件FP-樹Treeb； if Treeb 不為空 then 調(diào)用 FP_growth(Treeb, b)； } }

FP-growth的執(zhí)行過程：

1）在FP-growth遞歸調(diào)用的第一層，模式前后a=NULL，得到的其實就是頻繁1-項集。2）對每一個頻繁1-項，進行遞歸調(diào)用FP-growth()獲得多元頻繁項集。②優(yōu)點：

（ppt翻譯）

1.算法結(jié)構(gòu)擁有完整性：

1）沒有破壞事務(wù)的長模式；

2）能保留頻繁模式挖掘的完整信息。2.算法結(jié)構(gòu)擁有緊湊性：

1）不相關(guān)的項被刪除；

2）事務(wù)項按照頻率降序排列，因為更頻繁的項更可能被找到；

3）如果不計算鏈接和節(jié)點數(shù)目，存儲空間小于原始數(shù)據(jù)庫。

3.FP算法的效率比Apriori算法快一個數(shù)量級,效率快的原因有以下4個：

1）沒有候選集，沒有候選測試

2）有緊湊的數(shù)據(jù)結(jié)構(gòu)

3）消除重復(fù)的數(shù)據(jù)庫遍歷

4）基礎(chǔ)操作是計數(shù)和FP-Tree的建立 ③缺點：

（參考http://004km.cn/wiki/Covariance_matrix

我們認為bi代表B的第i行，那么由協(xié)方差矩陣

推知

<>表示向量的內(nèi)積，也就是每一項的積之和。⑤ 計算協(xié)方差矩陣C的特征值和特征向量

若XA=aA,其中A為一列向量，a為一實數(shù)。那么a就被稱為矩陣X的特征值，而A則是特征值a對應(yīng)的特征向量。

順便扯一下，在matlab里面，求解上述A以及a，使用eig函數(shù)。如[D,V] = eig(C)，那么D就是n個列特征向量，而V是對角矩陣，對角線上的元素就是特征值。⑥ 排序

將特征值按從大到小的順序排列，并根據(jù)特征值調(diào)整特征向量的排布。

D'=sort(D);V'=sort(V);

⑦ 計算總能量并選取其中的較大值

若V'為C的對角陣，那么總能量為對角線所有特征值之和S。

由于在步驟⑥里面已對V進行了重新排序，所以當(dāng)v'前幾個特征值之和大于等于S的90%時，可以認為這幾個特征值可以用來“表征”當(dāng)前矩陣。

假設(shè)這樣的特征值有L個。⑧ 計算基向量矩陣W

實際上，W是V矩陣的前L列，所以W的大小就是 MxL。⑨ 計算z-分數(shù)（這一步可選可不選）

Z[i,j]=B[i,j]/sqrt(D[i,i])⑩ 計算降維后的新樣本矩陣

W*表示W(wǎng)的轉(zhuǎn)置的共軛矩陣，大小為 LxM , 而Z的大小為 MxN , 所以Y的大小為 LxN , 即降維為 N 個 L 維向量。

②優(yōu)點： 該算法可以消除數(shù)據(jù)間的冗余，以簡化數(shù)據(jù)，提高計算效率。③缺點：缺乏主成分的物理解釋，也就是缺乏有效的語義解釋。

PCA假設(shè)數(shù)據(jù)各主特征是分布在正交方向上，如果在非正交方向上存在幾個方差較大的方向，PCA的效果就大打折扣了。

PCA技術(shù)的一個很大的優(yōu)點是，它是完全無參數(shù)限制的。在PCA的計算過程中完全不需要人為的設(shè)定參數(shù)或是根據(jù)任何經(jīng)驗?zāi)Ｐ蛯τ嬎氵M行干預(yù)，最后的結(jié)果只與數(shù)據(jù)相關(guān)，與用戶是獨立的。

但是，這一點同時也可以看作是缺點。如果用戶對觀測對象有一定的先驗知識，掌握了數(shù)據(jù)的一些特征，卻無法通過參數(shù)化等方法對處理過程進行干預(yù)，可能會得不到預(yù)期的效果，效率也不高

PCA也存在一些限制，例如它可以很好的解除線性相關(guān)，但是對于高階相關(guān)性就沒有辦法了，對于存在高階相關(guān)性的數(shù)據(jù)，可以考慮Kernel PCA，通過Kernel函數(shù)將非線性相關(guān)轉(zhuǎn)為線性相關(guān)

④改進：

第五篇：一種改進的基于SNMP的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法

龍源期刊網(wǎng) http://.cn

一種改進的基于SNMP的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法

作者：王淅娜 喻建鵬

來源：《軟件》2013年第03期

摘要：通過對網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法的研究，提出了改進的SNMP的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法，并對改進算法的流程進行了描述。該算法具有交換機的發(fā)現(xiàn)完備性，并且能對啞設(shè)備進行處理。關(guān)鍵詞：網(wǎng)絡(luò)拓撲；拓撲發(fā)現(xiàn)；啞設(shè)備；SNMP

中圖分類號：文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2013.03.020