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

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

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

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

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

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

中圖分類號(hào)：TM933 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 無線信號(hào)傳播模型

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

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

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

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

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

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

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

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

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

1dA?dB（假設(shè)圓A與圓B相交，圓心距交點(diǎn)的距離分別為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 改進(jìn)的三角形加權(quán)質(zhì)心定位算法

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

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

1d，進(jìn)而提

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

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

1?11n?m

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

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

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

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

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

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

11中原本起主要作用的dB所?dAdB起作用稍微弱化，以防止過度修正，這樣可以進(jìn)一步充分利用數(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 改進(jìn)后的定位算法實(shí)現(xiàn)步驟

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

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

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

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

(6)定義定位誤差為Er，其真實(shí)位置為(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é)點(diǎn)依據(jù)RSSI從大到小排列的集合： 仿真

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

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

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

/個(gè) 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值大的前三個(gè)并利用理論模型和經(jīng)驗(yàn)?zāi)Ｐ蛯⑵滢D(zhuǎn)化為錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離，即：

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

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

81

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

圖2 兩種算法的誤差分析對(duì)比

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

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

參 考 文 獻(xiàn)

[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é)報(bào), 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] 劉運(yùn)杰, 金明錄, 崔承毅.基于RSSI的無線傳感器網(wǎng)絡(luò)修正加權(quán)質(zhì)心

定位算法[J].傳感技術(shù)學(xué)報(bào), 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ìn)算法[J].傳感技術(shù)學(xué)

報(bào), 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é)點(diǎn)改進(jìn)質(zhì)心定位算法[J].微計(jì)

算機(jī)信息(測(cè)控自動(dòng)化), 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] 李娟, 王珂, 李莉.基于錨圓交點(diǎn)加權(quán)質(zhì)心的無線傳感器網(wǎng)絡(luò)定位算

法[J].吉林大學(xué)學(xué)報(bào)(工學(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.作者簡(jiǎn)介:

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

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

張琦(1986—)，男，碩士研究生，主要研究方向?yàn)闊o線自組網(wǎng)。張峰(1987—)，男，碩士研究生，主要研究方向?yàn)闊o線自組網(wǎng)。

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

（田春雨

編發(fā)）

第二篇：基于DV―Hop定位算法的改進(jìn)

基于DV―Hop定位算法的改進(jìn)

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

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

關(guān)鍵詞：

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

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

0引言

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

節(jié)點(diǎn)定位技術(shù)分為基于測(cè)距（Range Based）的定位算法和無需測(cè)距（Range Free）的定位算法兩類[3]1283，[5]39，[8]3。基于測(cè)距的定位算法原理是：通過測(cè)量節(jié)點(diǎn)與節(jié)點(diǎn)間的直線距離或角度信息估算未知節(jié)點(diǎn)的坐標(biāo)位置，目前這類測(cè)距技術(shù)主要有RSSI（Received Signal Strength Indicator）、TOA（Time of Arrival）、TDOA（Time Difference on Arrival）和AOA（Angle of Arrival）等[1]77，[5]40。基于測(cè)距定位算法的優(yōu)點(diǎn)是定位精度較高，缺點(diǎn)是網(wǎng)絡(luò)中的節(jié)點(diǎn)需要增加特殊的測(cè)距設(shè)備，從而導(dǎo)致節(jié)點(diǎn)成本較高。而無需測(cè)距的定位算法原理是：不需要測(cè)量節(jié)點(diǎn)間的實(shí)際距離以及節(jié)點(diǎn)間的方位角，只根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間的連通性、同向性等信息，就可以估算出未知節(jié)點(diǎn)的坐標(biāo)位置，常用的無需測(cè)距技術(shù)有：APIT（Approximate PointinTriangulation test）、質(zhì)心算法、DVHop（Distance VectorHop）和Amorphous等算法[5]40，[9]。無需測(cè)距定位算法的優(yōu)點(diǎn)是：組網(wǎng)成本低、網(wǎng)絡(luò)資源開銷少，缺點(diǎn)是定位誤差率稍高。實(shí)踐證明無需測(cè)距定位技術(shù)更能適合多數(shù)WSN的應(yīng)用，而在眾多無需測(cè)距的定位算法中，DVHop算法以其算法過程的簡(jiǎn)單性和實(shí)效性成為目前應(yīng)用較多的種類之一[7]2468。WSN中的節(jié)點(diǎn)分為兩類：一類是預(yù)先已知自身位置信息的傳感器節(jié)點(diǎn)，稱之為信標(biāo)節(jié)點(diǎn)（或“錨節(jié)點(diǎn)”），信標(biāo)節(jié)點(diǎn)的坐標(biāo)信息既可以通過全球定位系統(tǒng)（Global Positioning System，GPS）等技術(shù)自動(dòng)獲得，也可以在部署網(wǎng)絡(luò)時(shí)靠人工設(shè)置[8]6；第二類節(jié)點(diǎn)是預(yù)先并不知道自身的位置，通常稱之為待定位節(jié)點(diǎn)或者未知節(jié)點(diǎn)。這些未知節(jié)點(diǎn)的位置信息就需要利用本文和相關(guān)研究所探討的相關(guān)定位算法進(jì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個(gè)階段[1]77，[5]40，[11]。首先，接收并存儲(chǔ)未知節(jié)點(diǎn)與它鄰近的每個(gè)信標(biāo)節(jié)點(diǎn)間最小跳數(shù)；信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播包含自身地理位置信息的分組，這樣網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都能記錄下自己到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。其次，計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的跳距；每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)上述第一個(gè)階段的操作，記錄下了自己與其他信標(biāo)節(jié)點(diǎn)的坐標(biāo)值以及它們間的跳數(shù)。最后利用式（1），就可以估算出自己的平均每跳跳距。其中：（xi，yi）、（xj，yj）是信標(biāo)節(jié)點(diǎn)i和j的坐標(biāo)，hj是信標(biāo)節(jié)點(diǎn)i與j之間的跳數(shù)。

平均每跳跳距：

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

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

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

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

一

問題的提出

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

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

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

2.1從新課程標(biāo)準(zhǔn)對(duì)算法的要求中研究算法教學(xué)定位

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

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

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

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

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

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

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

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

學(xué)生這一階段的認(rèn)知結(jié)構(gòu)特點(diǎn)表現(xiàn)為：易于接受具體的、特殊的、有趣的數(shù)學(xué)知識(shí)，難以接受抽象的、一般的、枯燥乏味的數(shù)學(xué)知識(shí)。所以在教材的安排中體現(xiàn)了一種從特殊到一般的思想。教材中也是從具體實(shí)例出發(fā)引出這一類問題的通法?？紤]到這一認(rèn)知特點(diǎn)，我們提出以下教學(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é)生的識(shí)圖能力和程序框圖的應(yīng)用，以及學(xué)生對(duì)條件語句和循環(huán)語句的理解。

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

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

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

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

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

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

第四篇：機(jī)器學(xué)習(xí)算法優(yōu)缺點(diǎn)改進(jìn)總結(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(支持向量機(jī))（此算法是重點(diǎn)，必考題）此處有一道必考題

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ì)。（以下兩個(gè)表格來自兩篇該領(lǐng)域經(jīng)典論文）

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

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

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

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

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

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

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

2）收斂是穩(wěn)定的，因?yàn)槊看蔚乃迫缓瘮?shù)是不斷增加的。

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

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

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

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

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

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

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

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

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

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

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

機(jī)分割，然后重復(fù)EM效果進(jìn)行初始點(diǎn)選擇。

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

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

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

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

回歸模型：

i

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

即誤差值的平方。

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

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

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

具備很好的準(zhǔn)確性

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

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

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

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

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

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

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

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

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

其中

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

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

2）不太依賴特征的選擇，而且只需要用線性模型就能夠訓(xùn)練出不錯(cuò)的擬合模型、③缺點(diǎn)：1）計(jì)算量較大。（因?yàn)榫植考訖?quán)回歸的損失數(shù)隨著預(yù)測(cè)值的不同而不同，這樣θ

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

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

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

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

④改進(jìn)：

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

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

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

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

1）簡(jiǎn)單、有效。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

③缺點(diǎn)：只能處理線性問題

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

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

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

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

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

（1）即感知機(jī)無法找到一個(gè)線性模型對(duì)異或問題進(jìn)行劃分。

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

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

（1）判別分析概念

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

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

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

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

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

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

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

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

LDA不適合對(duì)非高斯分布的樣本進(jìn)行降維。

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

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

③針對(duì)“小樣本問題”的改進(jìn)方法

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

LDA與PCA的比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)懶惰算法，對(duì)測(cè)試樣本分類時(shí)的計(jì)算量大，內(nèi)存開銷大，評(píng)分慢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

補(bǔ)充樸素貝葉斯優(yōu)點(diǎn)：

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

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

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

補(bǔ)充樸素貝葉斯算法缺點(diǎn)：

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

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

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

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

激活函數(shù)

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

②優(yōu)點(diǎn)：

（1）高度的并行性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

比原始的更新規(guī)則多出了η * λ * sgn(w)/n這一項(xiàng)。當(dāng)w為正時(shí)，更新后的w變小。當(dāng)w為負(fù)時(shí)，更新后的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í)樣本，使用反向傳播算法對(duì)網(wǎng)絡(luò)的權(quán)值和偏差進(jìn)行反復(fù)的調(diào)整訓(xùn)練，使輸出的向量與期望向量盡可能地接近，當(dāng)網(wǎng)絡(luò)輸出層的誤差平方和小于指定的誤差時(shí)訓(xùn)練完成，保存網(wǎng)絡(luò)的權(quán)值和偏差。②優(yōu)點(diǎn)：

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

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

主要包括以下幾個(gè)方面的問題。

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

（2）BP算法可以使權(quán)值收斂到某個(gè)值，但并不保證其為誤差平面的全局最小值，這是因?yàn)椴捎锰荻认陆捣赡墚a(chǎn)生一個(gè)局部最小值

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

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

（5）網(wǎng)絡(luò)的預(yù)測(cè)能力（也稱泛化能力、推廣能力）與訓(xùn)練能力（也稱逼近能力、學(xué)習(xí)能力）的矛盾。一般情況下，訓(xùn)練能力差時(shí)，預(yù)測(cè)能力也差，并且一定程度上，隨訓(xùn)練能力地提高，預(yù)測(cè)能力也提高。但這種趨勢(shì)有一個(gè)極限，當(dāng)達(dá)到此極限時(shí)，隨訓(xùn)練能力的提高，預(yù)測(cè)能力反而下降，即出現(xiàn)所謂“過擬合”現(xiàn)象。此時(shí)，網(wǎng)絡(luò)學(xué)習(xí)了過多的樣本細(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)，而從問題中選取典型樣本實(shí)例組成訓(xùn)練集是一個(gè)很困難的問題。④改進(jìn).變步長法

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

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

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

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

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

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

①算法思想

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

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

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

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

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

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

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

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

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

補(bǔ)充：

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

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

所以，ID3的思想便是：

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

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

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

②優(yōu)點(diǎn)：

（1）分類精度高；

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

優(yōu)點(diǎn)補(bǔ)充：

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

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

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

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

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

（4）在建造決策樹時(shí)，每個(gè)結(jié)點(diǎn)僅含一個(gè)屬性，是一種單變?cè)乃惴ǎ率股傻臎Q策樹結(jié)點(diǎn)之間的相關(guān)性不夠強(qiáng)。雖然在一棵樹上連在一起，但聯(lián)系還是松散的。

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

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

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

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

④改進(jìn)：（1）對(duì)決策樹進(jìn)行剪枝?？梢圆捎媒徊骝?yàn)證法和加入正則化的方法。

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

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

（2）C4.5 Algorithm 補(bǔ)充：

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

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

②優(yōu)點(diǎn)：

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

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

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

2）在取值序列中生成total-1個(gè)分割點(diǎn)。第i（0

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

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

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

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

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

樹剪枝

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

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

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

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

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

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

③缺點(diǎn)：

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

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

（1）SLIQ算法

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

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

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

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

然而它仍然存在如下缺點(diǎn)：

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

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

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

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

（3）隨機(jī)森林(Random Forest)（對(duì)C4.5,ID3改進(jìn)，提高準(zhǔn)確率）

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

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

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

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

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

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

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

Lecture 5 Classifier Assessment and Ensemble Methods

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

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

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

? Bagging與Boosting的區(qū)別

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

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

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

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

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

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

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

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

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

對(duì)于boosting算法，存在兩個(gè)問題：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4、綜合方法的改進(jìn)

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

Adaboosting

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

一、挖掘步驟：

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

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

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

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

注：L-S表示在項(xiàng)集L中除去S子集的項(xiàng)集

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

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

方法

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

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

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

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

方法

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

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

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

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

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

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

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

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

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

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

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

3.求出每個(gè)節(jié)點(diǎn)的條件模式基

4.為每個(gè)節(jié)點(diǎn)建立FP-Tree

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

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

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

for each a i 在Tree的頭部(按照支持度由低到高順序進(jìn)行掃描){ 產(chǎn)生一個(gè)模式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，得到的其實(shí)就是頻繁1-項(xiàng)集。2）對(duì)每一個(gè)頻繁1-項(xiàng)，進(jìn)行遞歸調(diào)用FP-growth()獲得多元頻繁項(xiàng)集。②優(yōu)點(diǎn)：

（ppt翻譯）

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

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

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

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

2）事務(wù)項(xiàng)按照頻率降序排列，因?yàn)楦l繁的項(xiàng)更可能被找到；

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

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

1）沒有候選集，沒有候選測(cè)試

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

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

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

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

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

推知

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

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

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

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

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

⑦ 計(jì)算總能量并選取其中的較大值

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

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

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

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

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

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

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

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

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

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

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

④改進(jìn)：

第五篇：一種改進(jìn)的SUSAN興趣點(diǎn)檢測(cè)算法

龍?jiān)雌诳W(wǎng) http://.cn

一種改進(jìn)的SUSAN興趣點(diǎn)檢測(cè)算法作者：郭峰 韓溟 王道平

來源：《現(xiàn)代電子技術(shù)》2011年第10期