 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 10 | 1/1 | 返回列表 |
| 查看: 4265 | 回復(fù): 9 | |||||
| 【獎(jiǎng)勵(lì)】 本帖被評價(jià)5次，作者stephenliu89增加金幣 4 個(gè) | |||||
[資源]
【原創(chuàng)】一個(gè)簡單的kNN分類算法 (k-Nearest Neighbor algorithm) 的C++實(shí)現(xiàn)（附源碼）
|
|||||
鄰近算法 KNN算法的決策過程 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è)理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。 KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(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)值大）來改進(jìn)。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷γ恳粋�(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對已知樣本點(diǎn)進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。 KNN-主要應(yīng)用領(lǐng)域 ·文本分類·聚類分析·數(shù)據(jù)挖掘·機(jī)器學(xué)習(xí)·預(yù)測分析·減少維度·模式識別·圖像處理 我的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 << "請輸入已知點(diǎn)的個(gè)數(shù)："; cin >> m; for ( i = 1; i <= m; i++) { cout <<"請輸入點(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()//對距離進(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 <<"請輸入kNN的k值："; cin >> k; for ( i = 1; i <= 99; i++) types[ i ] = 0; for ( i = 1; i <= k; i++)//對已排序的前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 <<"請輸入未知類別點(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 <<"請輸入未知類別點(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 --------------------------------- 我的評價(jià)： 這是kNN分類算法的最簡單的一種情況，當(dāng)k取不同值時(shí)分類可能會出現(xiàn)不同。樣本過大時(shí)，由于要比較的次數(shù)增多，效率降低。 |
回復(fù)此樓» 收錄本帖的淘帖專輯推薦
 【計(jì)算機(jī)工具軟件與技巧】專輯 | ML相關(guān) | source |
» 猜你喜歡
311求調(diào)劑
已經(jīng)有9人回復(fù)
-
302求調(diào)劑
已經(jīng)有4人回復(fù)
-
被我言中：新模板不強(qiáng)調(diào)格式了，假專家開始管格式了
已經(jīng)有4人回復(fù)
-
303求調(diào)劑
已經(jīng)有5人回復(fù)
-
考研求調(diào)劑
已經(jīng)有4人回復(fù)
-
085601專碩，總分342求調(diào)劑，地區(qū)不限
已經(jīng)有4人回復(fù)
-
085601材料工程專碩求調(diào)劑
已經(jīng)有5人回復(fù)
-
一志愿天津大學(xué)化學(xué)工藝專業(yè)（081702）315分求調(diào)劑
已經(jīng)有6人回復(fù)
-
能源材料化學(xué)課題組招收碩士研究生8-10名
已經(jīng)有6人回復(fù)
-
296求調(diào)劑
已經(jīng)有5人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對您同樣有幫助:
- C++一道題目，疑惑
已經(jīng)有7人回復(fù)
- 科學(xué)計(jì)算首選語言是C++
已經(jīng)有20人回復(fù)
- 求助一個(gè)簡單程序
已經(jīng)有3人回復(fù)
- 請教一個(gè)C++讀文件的問題，
已經(jīng)有12人回復(fù)
- 一個(gè)簡單的C++程序運(yùn)行問題
已經(jīng)有8人回復(fù)
- Visual C++常用數(shù)值算法集【轉(zhuǎn)載】
已經(jīng)有187人回復(fù)
- Visual C++ CAD應(yīng)用程序開發(fā)技術(shù)源代碼（基于OPenGL技術(shù)開發(fā)的）
已經(jīng)有76人回復(fù)
- 數(shù)據(jù)結(jié)構(gòu)及算法經(jīng)典
已經(jīng)有227人回復(fù)
- 求一個(gè)簡單好用的科學(xué)計(jì)算器軟件。。
已經(jīng)有4人回復(fù)
- 分類算法識別率為多少是可以接受的？
已經(jīng)有5人回復(fù)
- 如何考察一個(gè)查詢算法的時(shí)間
已經(jīng)有6人回復(fù)
- 請問分類和回歸樹算法在哪個(gè)軟件里面可以實(shí)現(xiàn)？
已經(jīng)有3人回復(fù)
- java算法大全源碼包（近100種）
已經(jīng)有8人回復(fù)
- 一直沒怎么接觸過算法，如何實(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è)簡單的式子，卻算不正確
已經(jīng)有10人回復(fù)
- 【分享】37碼走埃及【已搜索無重復(fù)】
已經(jīng)有4人回復(fù)
- 【分享】數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用 C++語言描述
已經(jīng)有9人回復(fù)
- 【求助】求c++編一個(gè)簡單計(jì)算器的源代碼
已經(jīng)有6人回復(fù)
- 【分享】c++ 課件及配套源碼筆記
已經(jīng)有6人回復(fù)
yalefield
金蟲 (文壇精英)
- 程序強(qiáng)帖: 3
- 應(yīng)助: 129 (高中生)
- 貴賓: 0.17
- 金幣: 21238.9
- 帖子: 12101
- 在線: 759.1小時(shí)
- 蟲號: 96063
2樓2010-09-05 11:27:26
3樓2010-09-05 12:00:14
4樓2010-09-05 12:01:46
yalefield
金蟲 (文壇精英)
- 程序強(qiáng)帖: 3
- 應(yīng)助: 129 (高中生)
- 貴賓: 0.17
- 金幣: 21238.9
- 帖子: 12101
- 在線: 759.1小時(shí)
- 蟲號: 96063
5樓2010-09-05 16:57:35
6樓2010-09-05 19:13:59
7樓2012-04-13 16:22:29
 本帖僅樓主可見 |
8樓2014-03-24 20:57:40
9樓2014-03-25 08:14:34
10樓2020-10-14 15:11:36
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 stephenliu89 的主題更新
| 10 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 311求調(diào)劑 +8 | 冬十三 2026-03-15 | 9/450 |
|
|---|---|---|---|---|
|
|
[考研] 302求調(diào)劑 +4 | 呼呼呼。。。。 2026-03-17 | 4/200 |
|
|
|
[考研] 301求調(diào)劑 +5 | yy要上岸呀 2026-03-17 | 5/250 |
|
|
|
[考研] 268求調(diào)劑 +8 | 一定有學(xué)上- 2026-03-14 | 9/450 |
|
|
|
[考研] 301求調(diào)劑 +4 | A_JiXing 2026-03-16 | 4/200 |
|
|
|
[考研] 302求調(diào)劑 +9 | 負(fù)心者當(dāng)誅 2026-03-11 | 9/450 |
|
|
[考研] 085601求調(diào)劑 +4 | Du.11 2026-03-16 | 4/200 |
|
|
|
[考研] 材料專碩274一志愿陜西師范大學(xué)求調(diào)劑 +5 | 薛云鵬 2026-03-13 | 5/250 |
|
|
|
[考研] 一志愿211 0703方向310分求調(diào)劑 +3 | 努力奮斗112 2026-03-15 | 3/150 |
|
|
|
[考研] 318求調(diào)劑 +3 | Yanyali 2026-03-15 | 3/150 |
|
|
|
[考研] 277材料科學(xué)與工程080500求調(diào)劑 +3 | 自由煎餅果子 2026-03-16 | 3/150 |
|
|
|
[考研] 0703化學(xué)調(diào)劑 290分有科研經(jīng)歷，論文在投 +7 | 膩膩gk 2026-03-14 | 7/350 |
|
|
|
[考研] 327求調(diào)劑 +6 | 拾光任染 2026-03-15 | 11/550 |
|
|
|
[考研] 0856專碩279求調(diào)劑 +5 | 加油加油！? 2026-03-15 | 5/250 |
|
|
|
[考研] 331求調(diào)劑（0703有機(jī)化學(xué) +5 | ZY-05 2026-03-13 | 6/300 |
|
|
|
[考研] 0856材料與化工301求調(diào)劑 +5 | 奕束光 2026-03-13 | 5/250 |
|
|
|
[考研] （081700）化學(xué)工程與技術(shù)-298分求調(diào)劑 +12 | 11啦啦啦 2026-03-11 | 35/1750 |
|
|
|
[考研] 材料工程調(diào)劑 +4 | 咪咪空空 2026-03-11 | 4/200 |
|
|
|
[考研] 材料專碩350 求調(diào)劑 +4 | 王金科 2026-03-12 | 4/200 |
|
|
|
[考研] 308求調(diào)劑 +3 | 是Lupa啊 2026-03-12 | 3/150 |
|