Unit12K最近鄰算法K-NearestNeighbor暑假期間，小張同學在一家糕點坊做社會實踐，具體負責網(wǎng)上銷售和營銷策劃。一次，店里安排了一場促銷活動，需要預(yù)測活動日準備的新鮮面包個數(shù)。已知該店空氣質(zhì)量指數(shù)、是否是周末或節(jié)假日、有沒有促銷活動、銷售面包數(shù)量等歷史銷售數(shù)據(jù)，見下圖所示。請據(jù)此設(shè)計一個算法幫助小張同學測算出該活動日需要準備的面包個數(shù)。①理解和運用順序表、鏈表、數(shù)組等。②認識、理解和運用K最近鄰算法、貪婪算法。③運用大O表示法分析K最近鄰算法的時間復(fù)雜度。NP完全問題（Non-deterministicPolynomialComplete）日常的生活經(jīng)驗告訴我們：找一個問題的解很困難，但驗證一個解很容易。在計算機領(lǐng)域，一般可以將問題分為可解問題和不可解問題。不可解問題也可以分為兩類：無解。如停機問題等；有解，但時間復(fù)雜度很高?？山鈫栴}也分為：多項式問題（PolynomialProblem，P問題）非確定性多項式問題（Non-deterministicPolynomialProblem，NP問題）P問題：P問題是一個判定問題類，這些問題可以用一個確定性算法在多項式時間內(nèi)判定或解出。如果一個判定性問題的復(fù)雜度是該問題的一個實例的規(guī)模n的多項式函數(shù)，那么我們說這種可以在多項式時間內(nèi)解決的判定性問題屬于P問題。P問題就是所有復(fù)雜度為多項式時間的問題的集合，多項式問題是可解問題。NP問題：所有的非確定性多項式時間可解的判定問題構(gòu)成NP問題。非確定性算法：非確定性算法將問題分解成猜測和驗證兩個階段。算法的猜測階段是非確定性的，算法的驗證階段是確定性的，它驗證猜測階段給出解的正確性。NPC問題（NPComplete）：NP問題中的某些問題的復(fù)雜性與整個類的復(fù)雜性相關(guān)聯(lián)，這些問題中任何一個如果存在多項式時間的算法，那么所有NP問題都是多項式時間可解的，這些問題被稱為NP完全問題（NPC問題）。NPC問題是世界七大數(shù)學難題之一。多項式復(fù)雜程度的非確定性問題。簡單的寫法是NP

=

P？。NPC問題目前沒有多項式算法，只能用窮舉法逐個檢驗，最終得到答案。但是窮舉法的計算時間隨問題的復(fù)雜程度呈指數(shù)增長，很快問題就會變得不可計算了?，F(xiàn)實生活中，圍棋或象棋的博弈問題、國際象棋的n皇后問題、密碼學中的大素數(shù)分解問題、旅行商問題、集合覆蓋問題等，都屬于NPC問題。貪婪算法（GreedyAlgorithm）貪婪算法（又稱貪心算法）是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，算法得到的是在某種意義上的局部最優(yōu)解。貪婪算法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計技術(shù)。貪婪算法的特點是一步一步地進行，常以當前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度做最優(yōu)選擇，而不考慮各種可能的整體情況，省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。對于NPC問題運用貪婪算法求其近似解是個不錯的選擇。貪婪算法的思想如下：建立數(shù)學模型來描述問題。把求解的問題分成若干個子問題。對每一子問題求解，得到子問題的局部最優(yōu)解。把子問題的局部最優(yōu)解合成原來求解問題的一個解。貪婪算法的使用條件如下：1．貪婪選擇性質(zhì)一個問題的整體最優(yōu)解可通過一系列局部的最優(yōu)解的選擇達到，并且每次的選擇可以依賴以前做出的選擇，但不可以依賴后面將要做出的選擇。2．最優(yōu)子結(jié)構(gòu)性質(zhì)當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪婪算法求解的關(guān)鍵所在。用貪婪算法求解存在以下問題：不能保證解是最佳的。因為貪婪算法總是從局部出發(fā)，并沒從整體考慮。貪婪算法一般用來解決求最大或最小解。貪婪算法只能確定某些問題的可行性范圍。例題12-01設(shè)有M臺完全相同的機器運行N個獨立的任務(wù)，運行任務(wù)i所需要的時間為Ti天，要求確定一個調(diào)度方案，使得完成所有任務(wù)所需要的時間最短。假設(shè)任務(wù)已經(jīng)按照其運行的時間從大到小來排序，請按照最長運行時間作業(yè)優(yōu)先的策略，安排這M臺機器的任務(wù)。定義的變量如下（數(shù)組的下標從0開始）：m是機器數(shù)，n是任務(wù)數(shù)，max為完成所有任務(wù)的時間。數(shù)組t[]記錄任務(wù)的運行時間（長度為n）。二維數(shù)組s[i][j]表示i機器運行的j任務(wù)的編號（長度為mn）。數(shù)組d[]是記錄機器運行的時間（長度為m）；數(shù)組count[]是記錄i機器運行的任務(wù)數(shù)（長度為m）。min,i,j,k為臨時變量。例題12-02有一位旅行商，他需要前往5個城市，同時要確保旅程盡可能的短，請幫助這位旅行商確定一個先后順序，能確保旅程最短。5個城市的位置如圖所示，長度單位:km。1．計算每一條可能的路徑要找出前往這5個城市的最短路徑，為此，必須計算每一條可能的路徑。在圖中，5個城市有多少種可能的路線呢？5！=120種，增加一個城市就會有720種可能，如果是10個城市，那么這個數(shù)字變成10！=3628800，需要計算的可能路線超過350萬種，計算時間隨問題的規(guī)模增大呈階乘增長，很快問題就會變得不可計算了。因此，這是一個典型的NPC問題。2．運用貪婪算法求其解任選一個城市為出發(fā)點，如a城市。當每次選擇要去的下一個城市時，都選還沒有去過的最近的城市。如圖所示，運用貪婪算法求出的一條路徑為

a→b→d→c→e，總長度

143km。當然這個解不一定保證它就是最優(yōu)解。K最近鄰算法（K-NearestNeighbor）也稱為KNN算法，是由Cover和Hart在1968年提出的，這是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一，是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。算法中，所選擇的鄰居都是已經(jīng)正確分類的對象，在定類決策上只依據(jù)最鄰近的一個或幾個樣本的類別來決定待分樣本所屬的類別。1．算法思想當無法判定當前待分類點是從屬于已知分類中的哪一類時，依據(jù)統(tǒng)計學的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重，按照少數(shù)服務(wù)多數(shù)的原則把它歸為（或分配）到權(quán)重更大的那一類。2．K最近鄰算法的分類時間復(fù)雜度K最近鄰算法是一種惰性學習（即時學習或懶學習，Lazy-Learning）算法，分類器不需要使用訓練集進行訓練，訓練時間復(fù)雜度為0。K最近鄰算法的分類時間復(fù)雜度和訓練集中的文檔數(shù)目成正比，也就是說，如果訓練集中文檔總數(shù)為n，那么，K最近鄰算法的分類時間復(fù)雜度為O(n)。3．K最近鄰算法的適用K最近鄰算法雖然從原理上也依賴于極限定理（LimitTheorem），但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于K最近鄰算法主要靠周圍有限的鄰近樣本，而不是靠判別類域的方法來確定所屬類別的，因此對類域的交叉或重疊較多的待分樣本集來說，K最近鄰算法較其他方法更為適合。4．K最近鄰算法的設(shè)計計算測試數(shù)據(jù)與各個訓練數(shù)據(jù)之間的距離。按照距離的遞增關(guān)系進行排序。選取距離最小的K個點。確定前K個點所在類別的出現(xiàn)頻率。返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類。5．K最近鄰算法的基本要素K最近鄰算法使用的模型實際上對應(yīng)于對特征空間的劃分。K值的選擇，距離度量和分類決策規(guī)則是該算法的三個基本要素。（1）K值的選擇K值的選擇會對算法的結(jié)果產(chǎn)生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預(yù)測結(jié)果起作用，但容易發(fā)生過擬合（Overfitting）；如果K值較大，優(yōu)點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預(yù)測起作用，使預(yù)測發(fā)生錯誤。（2）距離度量距離度量一般采用Lp距離，當p=2時，即為歐氏距離，在度量之前，應(yīng)該將每個屬性的值規(guī)范化，這樣有助于防止具有較大初始值域的屬性比具有較小初始值域的屬性的權(quán)重過大。（3）分類決策規(guī)則分類決策規(guī)則是少數(shù)服從多數(shù)的表決規(guī)則，即由輸入實例的K個最臨近的訓練實例中的多數(shù)類決定輸入實例的類別。6．K最近鄰算法的優(yōu)缺點優(yōu)點：K最近鄰算法思路簡單，易于理解，易于實現(xiàn)，無須估計參數(shù)。缺點：當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。針對這一問題，可以采用權(quán)值的方法來改進。計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。常用的改進方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。小張同學暑假期間在一家糕點坊做社會實踐，具體負責網(wǎng)上銷售和營銷策劃。一次，店里安排了一場促銷活動，需要預(yù)測活動日準備的新鮮面包個數(shù)。已知該店空氣質(zhì)量指數(shù)、是否是周末或節(jié)假日、有沒有促銷活動、銷售面包數(shù)量等歷史銷售數(shù)據(jù)，如圖所示。空氣質(zhì)量指數(shù)、是否是周末或節(jié)假日、有沒有促銷活動是我們抽取的3個特征量。試完成以下任務(wù)：找出最接近的K（K=4）個鄰居。求出這K個鄰居的平均值（即預(yù)測的活動日準備的面包個數(shù)），填入表格最后一個單元格內(nèi)。距離公式為：算法分析:這是一個運用K最近鄰算法預(yù)測一個結(jié)果的問題。解題步驟如下：計算出活動日數(shù)據(jù)與各個歷史數(shù)據(jù)之間的距離（歐拉公式）。按照距離的遞增關(guān)系進行排序。選取距離最小的K個點（K=4）。求出K個最近鄰日子里賣出的面包數(shù)的算數(shù)平均數(shù)。按照K最近鄰算法的思路，我們需要進行以下操作。記錄下歷史數(shù)據(jù)（二維數(shù)組arry[][]存儲）。求出到活動日的距離（一位數(shù)組dist[]存儲）。計算得出預(yù)測值。1、根據(jù)任務(wù)要求和算法分析設(shè)計程序；2、編碼、調(diào)試、運行；3、做好記錄；4、總結(jié)。KNN用于分類和回歸，需要考慮最近的鄰居。能否挑出合適的特征事關(guān)KNN算法的成敗。貪婪算法尋求局部最優(yōu)解，企圖以這種方式獲得全局最優(yōu)解。對于NP完全問題，還沒有找到快速解決方案。面臨NP完全問題時，最佳的做法是使用近似算法。貪婪算法易于實現(xiàn)、運行速度快，是不錯的近似算法。單元數(shù)據(jù)結(jié)構(gòu)算法講解實操01線性表順序表數(shù)組順序查找二分查找二分查找02順序表數(shù)組鏈表簡單選擇排序簡單選擇排序03線性表順序表鏈表棧遞歸算法遞歸算法04線性表順序表數(shù)組鏈表快速排序快速排序05線性表順序表數(shù)組鏈表散列表散列表查找算法散列表查找06