 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 4275 | 回復(fù): 9 | |||||
| 【獎(jiǎng)勵(lì)】 本帖被評(píng)價(jià)5次，作者stephenliu89增加金幣 4 個(gè) | |||||
| 當(dāng)前只顯示滿足指定條件的回帖，點(diǎn)擊這里查看本話題的所有回帖 | |||||
[資源]
【原創(chuàng)】一個(gè)簡(jiǎn)單的kNN分類算法 (k-Nearest Neighbor algorithm) 的C++實(shí)現(xiàn)（附源碼）
|
|||||
鄰近算法 KNN算法的決策過(guò)程 k-Nearest Neighbor algorithm 是K最鄰近結(jié)點(diǎn)算法（k-Nearest Neighbor algorithm）的縮寫形式，是電子信息分類器算法的一種 該算法[5]的基本思路是[6]：在給定新文本后，考慮在訓(xùn)練文本集中與該新文本距離最近（最相似）的 K 篇文本，根據(jù)這 K 篇文本所屬的類別判定新文本所屬的類別 左圖中，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。 K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。 KNN算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。 該算法在分類時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。 KNN-主要應(yīng)用領(lǐng)域 ·文本分類·聚類分析·數(shù)據(jù)挖掘·機(jī)器學(xué)習(xí)·預(yù)測(cè)分析·減少維度·模式識(shí)別·圖像處理 我的kNN分類算法程序：   ------------------- Code written by Stephen Liu ----------------------- #include #include #define MAX 1000 using namespace std; int m, i, j; int types[100]; class str { public: float x; float y; float distance; int type; }; str data[ MAX ];//輸入的已知類別的數(shù)據(jù) str point;//需要根據(jù)kNN判斷類別的未知數(shù)據(jù) str temp; void input_data() { cout << "請(qǐng)輸入已知點(diǎn)的個(gè)數(shù)："; cin >> m; for ( i = 1; i <= m; i++) { cout <<"請(qǐng)輸入點(diǎn) " << i <<" 的坐標(biāo)x , y 和所屬類別：" ; cin >> data.x >> data.y >> data.type; } } void Distance()//計(jì)算未知類別點(diǎn)與所有已知類別點(diǎn)的距離 { for ( i = 1; i <= m; i++ ) data.distance = sqrt ( (data.x - point.x) * (data.x - point.x) + (data.y - point.y) * (data.y - point.y) ); } void sort()//對(duì)距離進(jìn)行從小到大排序 { for( i = 1; i <= m; i++) for(j = m; j > i; j--) { if(data[ j ].distance < data[ j - 1 ].distance) { temp=data[ j ]; data[ j ]=data[ j - 1 ]; data[ j - 1]=temp; } } } int kNN( ) { int the_type,num = 0, k; cout <<"請(qǐng)輸入kNN的k值："; cin >> k; for ( i = 1; i <= 99; i++) types[ i ] = 0; for ( i = 1; i <= k; i++)//對(duì)已排序的前k位距離類別進(jìn)行統(tǒng)計(jì) types[ data.type ] ++; for ( i = 1; i <= 99; i++)//找出未知類別點(diǎn)屬于的類別 { if (types > num ) { num = types; the_type = i; } } return ( the_type); } int main() { input_data(); cout <<"請(qǐng)輸入未知類別點(diǎn)的坐標(biāo)x,y（輸入0 0退出)："; cin >> point.x >> point.y; do { Distance(); sort(); cout <<"點(diǎn)( " << point.x << " , " << point.y <<" )屬于類"<< kNN() << endl; cout <<"請(qǐng)輸入未知類別點(diǎn)的坐標(biāo)x,y（輸入0 0退出)："; cin >> point.x >> point.y; } while ( point.x != 0 && point.y != 0); cout <<"======= kNN分類算法 Stephen Liu E-mail:stephenliu1989@163.com 2010.8 ======= "; system("pause"  ;return 0; } ------------------------- Code end --------------------------------- 我的評(píng)價(jià)： 這是kNN分類算法的最簡(jiǎn)單的一種情況，當(dāng)k取不同值時(shí)分類可能會(huì)出現(xiàn)不同。樣本過(guò)大時(shí)，由于要比較的次數(shù)增多，效率降低。 |
回復(fù)此樓» 收錄本帖的淘帖專輯推薦
 【計(jì)算機(jī)工具軟件與技巧】專輯 | ML相關(guān) | source |
» 猜你喜歡
269求調(diào)劑
已經(jīng)有4人回復(fù)
-
一志愿河北工業(yè)大學(xué)0817化工278分求調(diào)劑
已經(jīng)有7人回復(fù)
-
一志愿211 初試270分 求調(diào)劑
已經(jīng)有5人回復(fù)
-
265求調(diào)劑
已經(jīng)有10人回復(fù)
-
327求調(diào)劑
已經(jīng)有3人回復(fù)
-
材料專業(yè)求調(diào)劑
已經(jīng)有9人回復(fù)
-
291求調(diào)劑
已經(jīng)有7人回復(fù)
-
070300化學(xué)求調(diào)劑
已經(jīng)有8人回復(fù)
-
材料專碩英一數(shù)二306
已經(jīng)有8人回復(fù)
-
請(qǐng)教下大家 2026年國(guó)家基金申請(qǐng)是雙盲審嗎？
已經(jīng)有4人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- C++一道題目，疑惑
已經(jīng)有7人回復(fù)
- 科學(xué)計(jì)算首選語(yǔ)言是C++
已經(jīng)有20人回復(fù)
- 求助一個(gè)簡(jiǎn)單程序
已經(jīng)有3人回復(fù)
- 請(qǐng)教一個(gè)C++讀文件的問(wèn)題，
已經(jīng)有12人回復(fù)
- 一個(gè)簡(jiǎn)單的C++程序運(yùn)行問(wèn)題
已經(jīng)有8人回復(fù)
- Visual C++常用數(shù)值算法集【轉(zhuǎn)載】
已經(jīng)有187人回復(fù)
- Visual C++ CAD應(yīng)用程序開(kāi)發(fā)技術(shù)源代碼（基于OPenGL技術(shù)開(kāi)發(fā)的）
已經(jīng)有76人回復(fù)
- 數(shù)據(jù)結(jié)構(gòu)及算法經(jīng)典
已經(jīng)有227人回復(fù)
- 求一個(gè)簡(jiǎn)單好用的科學(xué)計(jì)算器軟件。。
已經(jīng)有4人回復(fù)
- 分類算法識(shí)別率為多少是可以接受的？
已經(jīng)有5人回復(fù)
- 如何考察一個(gè)查詢算法的時(shí)間
已經(jīng)有6人回復(fù)
- 請(qǐng)問(wèn)分類和回歸樹(shù)算法在哪個(gè)軟件里面可以實(shí)現(xiàn)？
已經(jīng)有3人回復(fù)
- java算法大全源碼包（近100種）
已經(jīng)有8人回復(fù)
- 一直沒(méi)怎么接觸過(guò)算法，如何實(shí)現(xiàn)算法改進(jìn)。
已經(jīng)有4人回復(fù)
- 什么是Nelder–Mead simplex algorithm
已經(jīng)有5人回復(fù)
- 關(guān)于knn分類器的使用：在分類前需要正態(tài)化處理嗎？
已經(jīng)有4人回復(fù)
- 一個(gè)簡(jiǎn)單的式子，卻算不正確
已經(jīng)有10人回復(fù)
- 【分享】37碼走埃及【已搜索無(wú)重復(fù)】
已經(jīng)有4人回復(fù)
- 【分享】數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用 C++語(yǔ)言描述
已經(jīng)有9人回復(fù)
- 【求助】求c++編一個(gè)簡(jiǎn)單計(jì)算器的源代碼
已經(jīng)有6人回復(fù)
- 【分享】c++ 課件及配套源碼筆記
已經(jīng)有6人回復(fù)
4樓2010-09-05 12:01:46
yalefield
金蟲 (文壇精英)
- 程序強(qiáng)帖: 3
- 應(yīng)助: 129 (高中生)
- 貴賓: 0.17
- 金幣: 21238.9
- 帖子: 12101
- 在線: 759.1小時(shí)
- 蟲號(hào): 96063
2樓2010-09-05 11:27:26
3樓2010-09-05 12:00:14
yalefield
金蟲 (文壇精英)
- 程序強(qiáng)帖: 3
- 應(yīng)助: 129 (高中生)
- 貴賓: 0.17
- 金幣: 21238.9
- 帖子: 12101
- 在線: 759.1小時(shí)
- 蟲號(hào): 96063
5樓2010-09-05 16:57:35
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
