1、一、()泛化誤差上界：對二分類問題，當假設空間是有限個函數(shù)的集合時，對任意一個函數(shù),至少以概率，以下不等式成立：其中，即的泛化能力：.證明：在證明中要用到Hoeffding不等式，故先敘述如下：設是獨立隨機變量是之和，；為這組隨機變量的均值，則，以下不等式成立：對任意函數(shù),是個獨立的隨機變量樣本均值，是隨機變量的期望值。如果損失函數(shù)取值于區(qū)間，即對所有,那么有上述Hoeffding不等式，對，以下不等式成立：由于是一有限集合，故或者等價的，對任意，有令則故至少以概率有.2、 ()以損失函數(shù)推導向量最小化感知機的損失函數(shù) 感知機學習算法是誤分類驅(qū)動的，具體采用隨機梯度下降法。首先，任意

2、選取一個超平面，然后用梯度下降法不斷極小化目標函數(shù)，極小化的過程不是一次使中所有的誤分類點的梯度下降，而是一次隨機選取一個誤分類點使其梯度下降.隨機梯度下降是一種迭代求解思路，而迭代法參數(shù)尋優(yōu)的基本原理：沿著（代價）函數(shù)下降的方向?qū)ふ覅?shù)，能夠找到極值點.在我們已經(jīng)學過的數(shù)學知識中，導數(shù)和方向?qū)?shù)是能找到函數(shù)變化方向的。導數(shù)表示了曲線的斜率（傾斜度），方向?qū)?shù)表示了曲面沿著任意方向的斜率（傾斜度）。一維時，導數(shù)就足夠了。但多維時，就需要借助方向?qū)?shù)了，而我們更希望能找到變化率最大的方向。因此，多維下借用方向?qū)?shù)變化最大的情況：梯度，梯度的方向是函數(shù)某點增長最快的方向，梯度的大小是該點的最大變化

3、率.故對于損失函數(shù)的梯度是對和求偏導：三、（）如圖所示的訓練數(shù)據(jù)集，其正實例點是，負實例點是，試用感知機學習算法的原始形式求感知機模型.這里，.解 構(gòu)建最優(yōu)化問題：按照感知機學習算法的原始形式，求解，.(1) 取初值，(2) 對，未能被正確分類，更新，.，得到線性模型(3) 對，顯然，被正確分類，不修改，.對，被誤分類，更新，.，得到線性模型，得到線性模型(5)對，被誤分類，更新，故得到線性模型（6）對，被誤分類點，更新，.，故得到線性模型（7） 對，被誤分類點，更新，.，故得到線性模型（8） 對，被誤分類點，更新，.，故得到線性模型而該模型對正實例點，負實例點，都有，則沒有分類點，損失函數(shù)達

4、到最小.故分離超平面為感知機模型為迭代過程如表4、 從統(tǒng)計角度考慮哪些因素影響近鄰法的準確度.我們知道近鄰法是一種應用廣泛的非參數(shù)分類方法 ,可用于線性不可分的多類樣本識別。它的優(yōu)點是事先并不要求知道待分樣本的分布函數(shù)。目前廣泛使用的近鄰法是以待分類樣本為中心做超球體 ,逐漸擴大超球半徑直至超球內(nèi)包含個已知模式樣本為止, 判斷這個近鄰樣本中多數(shù)屬于哪一類 ,就把待分類樣本歸為哪一類。分類算法描述如下:假設有個類別，.測試樣本和與其最近的樣本之間的距離為,，其中的下標表示類,上標表示類個樣本中第個樣本.在超球半徑的前提下, 求，表示這個近鄰中屬于的樣本數(shù) .上述方法的弱點就是 ,半徑的選取十分困

5、難.值過大, 超球體的覆蓋面積廣,會導致其他類樣本被錯誤的覆蓋, 從而加大樣本的誤識率·反之若值過小 ,則不能完全覆蓋該類別中可能的樣本點.并且近鄰點具有相似的預測值 ,所以的大小也會影響近鄰法的準確度.該方法易受噪聲影響,尤其是樣本點中孤立點的影響·而我們知道近鄰法模型由三個部分構(gòu)成：距離度量，的值，分類決策規(guī)則。所以值的選取也會影響到分類結(jié)果. 因為值的選取是根據(jù)每類樣本的數(shù)目和分散程度選取的 ,對不同的應用選取的值也不同·所以我們是要在是在值選定的情況下, 對近鄰點的搜索區(qū)域進行合理的定位 ,即選取合適的的大小，即全局到局部 ,同時還要保障分類結(jié)果的準確性.

6、具體方法：首先將樣本空間的樣本點進行小規(guī)模有目的性的聚類,聚類后樣本空間中樣本分布的區(qū)域被劃分成,若干個半徑一定的小超球體·如果能保證超球體內(nèi)主體類樣本數(shù)遠遠大于雜質(zhì)類樣本數(shù), 那么搜索時就可根據(jù)其條件將搜索范圍縮小到某些超球體內(nèi),在這些超球體內(nèi)尋找待分樣本點的個近鄰點· 定義代表全體聚類的集合 ,即中包含全部聚類中的數(shù)據(jù)·代表確定的近鄰點的集合, 為最近間隔, 為競爭點集, 即可能成為近鄰點的集合·聚類后計算指定點到每個聚類中心的距離, 如圖 1 所示依據(jù)這些距離, 聚類集被劃分 ,離最近的聚類為,下一個距離較近的聚類為 ,依次編號·然后將聚

7、類中的所有點添加到中,計算中所有點與的距離, 將滿足條件的點轉(zhuǎn)移到集合中·這樣近鄰點的搜索區(qū)域就可以被大致定位·求近鄰點的關鍵是確定點到中聚類的搜索距離 ,為此需創(chuàng)建最近間隔 ·每次近鄰點的搜索范圍便是以待分類點為圓心，值為半徑的球體.在整個搜索過程中最近間隔一直處在變化過程中,值修改時采用使間隔內(nèi)包含盡量少的需要計算的近鄰點的原則,已確保搜索的準確性·當聚類被初始劃分時 ,由于采用局部聚類的方法,因此可能造成兩個聚類存在重疊區(qū)域·為避免重疊區(qū)域的點因重搜索而影響算法效率, 所以在計算最近間隔時 ,還必須考慮中的聚類是否有重疊區(qū)·當最

8、近間隔被初始創(chuàng)建時,檢查與其他聚類是否有重疊區(qū)域, 如果沒有且, 則中所有點皆放入中, 此時.如果有重疊區(qū)域或,則·當被確定后, 中所有點依據(jù)值,將滿足條件的點轉(zhuǎn)移到中·若中的點搜索完畢 ,則按編號將下一個聚類中的點添加到中 ,重復上述操作 ,直到中包含個元素時為止.5、 根據(jù)表2計算:(1) 后驗概率；(2) 離散屬性的類條件概率；(3) 連續(xù)屬性的類條件概率分布的參數(shù) （樣本均值和方差）Id有房婚姻狀況年收入拖欠貸款1真單身125KNo2否已婚100KNo3否單身70KNo4真已婚120KNo5否離婚95KYes6否已婚60KNo7真離婚220KNo8否單身85KYes9否已婚75KNo10否單身90KYes表2 從該數(shù)據(jù)集計算得到的先驗概率以及每個離散屬性的類條件概率、連續(xù)屬性的類條件概率分布的參數(shù)（樣本均值和方差）如下：先驗概率：P(Yes)=；P(No)=年收入：如果類=No:樣本均值=；樣本方差=2975;如果類=Yes:樣本均值=90；樣本方差=25待預測記錄：=有房=否，婚姻狀況=已婚，年收入=120K