❶ excel怎麼用k近鄰演算法
K近鄰演算法的原理非常簡單：對於一個新的數據而言，K近鄰演算法的目的就是在已有數據中尋找與它最相似的K個數據，或者說「離它最近」的K個數據，如果這K個點大多數屬於某一個類別，則該樣本也屬於這個類別。
❷ 八：聚類演算法K-means（20191223-29)
學習內容：無監督聚類演算法K-Means
k-means：模型原理、收斂過程、超參數的選擇
聚類分析是在數據中發現數據對象之間的關系，將數據進行分組，組內的相似性越大，組間的差別越大，則聚類效果越好。
不同的簇類型： 聚類旨在發現有用的對象簇，在現實中我們用到很多的簇的類型，使用不同的簇類型劃分數據的結果是不同的。
基於原型的： 簇是對象的集合，其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近，如(b)所示的原型即為中心點，在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ，最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。
基於密度的 ：簇是對象的密度區域，(d)所示的是基於密度的簇，當簇不規則或相互盤繞，並且有早上和離群點事，常常使用基於密度的簇定義。
關於更多的簇介紹參考《數據挖掘導論》。
基本的聚類分析演算法
1. K均值： 基於原型的、劃分的距離技術，它試圖發現用戶指定個數(K)的簇。
2. 凝聚的層次距離： 思想是開始時，每個點都作為一個單點簇，然後，重復的合並兩個最靠近的簇，直到嘗試單個、包含所有點的簇。
3. DBSCAN: 一種基於密度的劃分距離的演算法，簇的個數有演算法自動的確定，低密度中的點被視為雜訊而忽略，因此其不產生完全聚類。
不同的距離量度會對距離的結果產生影響，常見的距離量度如下所示：
優點：易於實現
缺點：可能收斂於局部最小值，在大規模數據收斂慢
演算法思想：
選擇K個點作為初始質心
repeat
將每個點指派到最近的質心，形成K個簇
重新計算每個簇的質心
until 簇不發生變化或達到最大迭代次數
這里的「重新計算每個簇的質心」，是根據目標函數來計算的，因此在開始時要考慮 距離度量和目標函數。
考慮歐幾里得距離的數據，使用 誤差平方和（Sum of the Squared Error,SSE） 作為聚類的目標函數，兩次運行K均值產生的兩個不同的簇集，使用SSE最小的那個。
k表示k個聚類中心，ci表示第幾個中心，dist表示的是歐幾里得距離。
這里有一個問題就是為什麼，我們更新質心是讓所有的點的平均值，這里就是SSE所決定的。
k均值演算法非常簡單且使用廣泛，但是其有主要的兩個缺陷：
1. K值需要預先給定 ，屬於預先知識，很多情況下K值的估計是非常困難的，對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景，可以進行迭代運算，然後找出Cost Function最小時所對應的K值，這個值往往能較好的描述有多少個簇類。
2. K-Means演算法對初始選取的聚類中心點是敏感的 ，不同的隨機種子點得到的聚類結果完全不同
3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇，銀冠指定足夠大的簇的個數是他通常可以發現純子簇。
4. 對離群點的數據進行聚類時，K均值也有問題 ，這種情況下，離群點檢測和刪除有很大的幫助。
下面對初始質心的選擇進行討論：
當初始質心是隨機的進行初始化的時候，K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕，可能只能得到局部的最優解，而無法得到全局的最優解。
多次運行，每次使用一組不同的隨機初始質心，然後選擇一個具有最小的SSE的簇集。該策略非常的簡單，但是效果可能不是很好，這取決於數據集合尋找的簇的個數。
關於更多，參考《數據挖掘導論》
為了克服K-Means演算法收斂於局部最小值的問題，提出了一種 二分K-均值(bisecting K-means)
將所有的點看成是一個簇
當簇小於數目k時
對於每一個簇
計算總誤差
在給定的簇上進行K-均值聚類,k值為2 計算將該簇劃分成兩個簇後總誤差
選擇是的誤差最小的那個簇進行劃分
在原始的K-means演算法中，每一次的劃分所有的樣本都要參與運算，如果數據量非常大的話，這個時間是非常高的，因此有了一種分批處理的改進演算法。
使用Mini Batch（分批處理）的方法對數據點之間的距離進行計算。
Mini Batch的好處：不必使用所有的數據樣本，而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少，所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。
聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集，每個子集成為一個「簇」。通過這樣的劃分，每個簇可能對應於一些潛在的概念（也就是類別）；需說明的是，這些概念對聚類演算法而言事先是未知的，聚類過程僅能自動形成簇結構，簇對應的概念語義由使用者來把握和命名。
聚類是無監督的學習演算法，分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集（也就是說提前知道訓練集里的數據屬於哪個類別），機器學習演算法在訓練集上學習到相應的參數，構建模型，然後應用到測試集上。而聚類演算法是沒有標簽的，聚類的時候，需要實現的目標只是把相似的東西聚到一起。
聚類的目的是把相似的樣本聚到一起，而將不相似的樣本分開，類似於「物以類聚」，很直觀的想法是同一個簇中的相似度要盡可能高，而簇與簇之間的相似度要盡可能的低。
性能度量大概可分為兩類： 一是外部指標， 二是內部指標 。
外部指標：將聚類結果和某個「參考模型」進行比較。
內部指標：不利用任何參考模型，直接考察聚類結果。
對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大
初學者會很容易就把K-Means和KNN搞混，其實兩者的差別還是很大的。
K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的簇類別。
當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。
優點：
簡單， 易於理解和實現 ；收斂快，一般僅需5-10次迭代即可，高效
缺點：
1，對K值得選取把握不同對結果有很大的不同
2，對於初始點的選取敏感，不同的隨機初始點得到的聚類結果可能完全不同
3，對於不是凸的數據集比較難收斂
4，對噪點過於敏感，因為演算法是根據基於均值的
5，結果不一定是全局最優，只能保證局部最優
6，對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。
K-means演算法簡單理解，易於實現（局部最優），卻會有對初始點、雜訊點敏感等問題；還容易和監督學習的分類演算法KNN混淆。
參考閱讀：
1.《 深入理解K-Means聚類演算法 》
2.《 K-Means 》
❸ 實驗二 K-近鄰演算法及應用
（1）簡單，易於理解，易於實現，無需估計參數。
（2）訓練時間為零。它沒有顯示的訓練，不像其它有監督的演算法會用訓練集train一個模型（也就是擬合一個函數），然後驗證集或測試集用該模型分類。KNN只是把樣本保存起來，收到測試數據時再處理，所以KNN訓練時間為零。
（3）KNN可以處理分類問題，同時天然可以處理多分類問題，適合對稀有事件進行分類。
（4）特別適合於多分類問題(multi-modal,對象具有多個類別標簽)， KNN比SVM的表現要好。
（5）KNN還可以處理回歸問題，也就是預測。
（6）和樸素貝葉斯之類的演算法比，對數據沒有假設，准確度高，對異常點不敏感。
（1）計算量太大，尤其是特徵數非常多的時候。每一個待分類文本都要計算它到全體已知樣本的距離，才能得到它的第K個最近鄰點。
（2）可理解性差，無法給出像決策樹那樣的規則。
（3）是慵懶散學習方法，基本上不學習，導致預測時速度比起邏輯回歸之類的演算法慢。
（4）樣本不平衡的時候，對稀有類別的預測准確率低。當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。
（5）對訓練數據依賴度特別大，對訓練數據的容錯性太差。如果訓練數據集中，有一兩個數據是錯誤的，剛剛好又在需要分類的數值的旁邊，這樣就會直接導致預測的數據的不準確。
需要一個特別容易解釋的模型的時候。
比如需要向用戶解釋原因的推薦演算法。
通過此次實驗我了解了K近鄰演算法及其思路，該方法的思路是：如果一個樣本在特徵空間中的k個最相似的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
所謂k近鄰演算法，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的k個實例。
❹ 12 - SVM, KNN，LR, RF簡要介紹
這里接 第11篇 的介紹。
支持向量機是可對類別進行分類的有監督的學習演算法。其在樣本的特徵空間中找出間隔最大的超平面對樣本進行分類。SVM根據其學習演算法不同可劃分為線性可分SVM、線性近似可分SVM與非線性SVM。實現上述三種SVM主要依靠核函數—線性核函數、高斯核函數、多項式核函數與Sigmoid核函數，後三種核函數為非線性，一般建議使用高斯核函數。
如上圖，對於二分類，SVM需要確定一條最優直線使兩類樣本分開，在圖1-4中A可以看到有多條直線可將兩組分開，但最優的是圖1-4中B的w*x+b=0直線。對於最優直線的確定，需要使最優直線到最近點的距離最大，最近點被稱為支持向量（如圖1-4中B的紅點/圈），這里的距離是求出點到直線的距離最大，這是在二維空間，當在三維及其以上的空間時，直線變為超平面，距離則需要求點到超平面的幾何距離（Westreich et al 2010）。
SVM的優點：（1）適用各種形式的數據，如文本、圖像等；（2）泛化能力較好，即其過擬合的風險小；（3）相對較好地處理高維度數據；（4）核函數的應用使其能很好的適應各種情況。其缺點：（1）對大規模數據難以處理；（2）只依靠少數支持向量決定最終結果，如有異常值，則結果容易出現較大偏差；（3）對缺失值敏感（Westreich et al 2010）。
K最近鄰演算法是通過計算樣本特徵之間的距離，根據距離k進行分類，屬於無參數分類和回歸方法（Altman 1992）。距離k的度量可以使用閔可夫斯基距離、歐氏距離與曼哈頓距離等距離公式進行計算，一般其取20以內的正整數，較大的k取值會降低噪音對分析的影響，且一般對於二分類問題，取k為奇數將有利於判別。
閔可夫斯基距離公式為：
上述公式中，當p=2時，變為歐氏距離，當p=1時，變為曼哈頓距離（Hechenbichler and Schliep 2004）。
KNN屬於「懶惰學習」，即只是將訓練集數據儲存起來，再來新樣本時進行距離計算，根據投票結果判別新樣本屬於哪一類。例如圖1-6，藍色方框與紅色三角為已知的訓練集，當有綠色圓圈新樣本進行判別時，假設k為1，則有兩個紅色三角與一個為藍色方框參與判別，這樣投票結果為2:1，故綠色圓圈屬於紅色三角形一類；假如k為2，則有兩個紅色三角與三個為藍色方框參與判別，這樣投票結果為2:3，故綠色圓圈屬於藍色方框。所以k值需要選擇，一般是根據經驗進行設置，並且每個樣本（如紅三角）對判別決策所佔的比重也可以進行設定即為權重KNN（Hechenbichler and Schliep 2004）。
邏輯回歸是一種有監督的學習方法，其函數基本的公式：
上述公式為Sigmoid函數，圖為1-7，其輸出值在[0, 1]之間，需要選擇一個閾值，通常是0.5，當p(x) > 0.5時，x為A類，如果p(x) < 0.5時，x為B類。閾值可以調整，其代表對於這個事情的把握度，如上述的閾值為0.5，如計算的p(x1)=0.3，則有50%的把握認為x1屬於B類（Press 2013）。
LR的運算基本過程：（1）假設p(x)=1，構造sigmoid函數，即利用最大似然取對數作為誤差函數，用梯度下降求最小的誤差函數值，求出a與b；（2）根據訓練數據集多組數據，重復循環（1）n次，計算數據集梯度，更新sigmoid參數，確定最終的sigmoid函數；（3）輸入預測集數據；（4）運用最終sigmoid函數求解分類（Dreiseitl and Ohno-Machado 2002）。
LR的優點：（1）容易接收新數據，對模型更新；（2）能夠容易解決變數間的共線性問題；（3）運算速度快，適合二分類問題。其缺點：（1）適用的數據和具體場景較少；（2）不適用於樣本具有很大的特徵值（即變數過多）；（3）容易欠擬合，分類准確性較低；（4）使用前提是應變數和自變數有線性關系，只是廣義線性模型，不能處理非線性問題。
隨機森林是將多個決策樹集合在一起的一種演算法，基本單元為決策樹，並且可以用於回歸和分類（Breiman 2001, Liaw and Wiener 2002）。其名字由「隨機」與「森林」組成，「隨機」有兩個含義，一指在訓練集中隨機且有放回的抽取n個樣本進行建模，二指每個節點在特徵值M中隨機抽取k（k<M）個進行建模，且每個節點處的k應相同，這兩個隨機使該演算法不容易過擬合（Ho 1998）。「森林」即為多個決策樹組成，其要求基本同上述的決策樹，但這里的決策樹沒有剪枝的過程，讓其盡量生長（Cutler et al 2012）。其將多個決策樹組合在一起是採用集成學習方法，該演算法的中心思想是讓每個決策樹產生一個結果，再對這些結果進行統計，哪種結果數量最多，即為最終結果。
RF實現的過程（1）隨機有放回的從樣本N中選出n個子樣本；（2）每個節點在特徵值M中隨機選出k個特徵值；（3）重復第一與第二步s次，創建s個決策樹；（4）對s個決策樹結果分析，哪一類決策樹最多，則最終判別為哪一類。
RF演算法主要有兩個參數，第一個為抽取每個樣本的特徵值k，第二個為決策樹的數量。特徵值k一般建議為全部特徵值的開方（Geurts et al 2006）。在確定較優的k後，一般取決策樹數為500進行嘗試，查看隨著決策樹的數量增多，袋外錯誤率是否會穩定在一個定值，取能達到這個定值的最小決策樹數的數量。
隨機森林演算法優點：（1）能夠有效處理大數據；（2）能處理高維度變數的樣本，不需要降維；（3）能較好處理缺失值問題。其缺點：（1）不能直觀進行解釋（2）過度擬合某些具有雜訊分類。
上述的八種演算法，一般多用於二分類問題，如「有或無」與「好或壞」等，但在實際應用中也有較多的多分類問題，如彩虹可以劃分7種顏色，當判別一個新的顏色屬於這7種顏色的哪一種時，這就需要解決一個七分類問題。多分類是二分類的一個拓展，解決辦法有兩種，第一種是一對多，即先從K類中選出一種，剩餘K-1類歸為一種，這樣需要建立K個判別模型，當有新數據進行判別時，新樣本需在K個判別模型中，同時進行判別，看被判別為哪一類的可能性最大，就判別為哪類；
❺ 02 KNN演算法 - KD Tree
KD Tree 是KNN演算法中用於計算最近鄰的快速簡便的構建方式。
當樣本量少的時候，用 brute 直接搜索最近鄰的方式是可行的。即計算到所有樣本的距離。但當樣本量龐大時，直接計算所有樣本距離的工作量很大，這種情況使用 KD Tree 可以節約大量時間成本。
KD樹採用從m個樣本的n維特徵中，分別計算n個特徵取值的方差，用 方差最大 的第k維特徵n k 作為 根節點 。對於這個特徵，選擇取值中的 中位數 n kv 作為樣本的劃分點，對於小於該值的樣本劃分到 左子樹 ，對於大於等於該值的樣本劃分到 右子樹 ，對左右子樹採用同樣的方式找 方差最大的特徵 作為 根節點 ，遞歸產生KD Tree。
為什麼要選擇方差最大的進行劃分？
構建樹的目的是加快我的搜索過程。
既然我想加快我的搜索過程，要就意味著我最終的數據落在某個葉子節點上。我希望只需搜索整個二叉樹的某一些列即可，那麼最好的劃分方式，就是讓我的每個分支上數據的差異性最大化。
那麼衡量數據差異性的最基礎的數學指標是什麼？
是方差。方差越大，意味著數據的離散程度就越大，我將離散程度由大到小的數據一分為二，方差小意味著數據更集中到了一起。
現在有一個二維樣本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、計算x1和x2每一列對應的方差
a、通過pandas計算出的是 樣本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通過numpy計算出的是 總體方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一個樹的劃分：基於x 1 進行劃分
[2,4,5,7,8,9]的中位數是5和7的平均值6。
雖然嚴格意義上說中位數是6，但是在計算機中我們人為得定義x 1 的中位數是7。
左側：（2,3）（5,4）（4,7） （7,2）
右側: （9,6）（8,1）
第二個樹的劃分：根據右側（9,6）（8,1）的x 2 進行劃分
下側：x 2 ≤ 6；上側x 2 ＞6
第二個樹的劃分：根據左側（2,3）（5,4）（4,7） （7,2）的x 2 進行劃分
尋找2、3、4、7的中位數 4 進行劃分
....
注意：每次生成的劃分都是一個矩形。當葉子節點無法被繼續劃分的時候，KD樹的構建完成，遞歸結束。
我們生成了KD Tree後，現在就可以去預測測試集裡面的樣本目標點了。
1、對於一個目標點，先在KD樹里找到包含目標點的葉子節點。
2、以目標點為圓心，以 目標點 到 葉子節點樣本實例 的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。
3、然後返回葉子節點的父節點，檢查另一個子節點包含的超矩形體是否和超球體相交。
4、如果相交就倒這個子節點尋找著是否有更加近的近鄰，有的話就更新最近鄰。
5、如果不相交，直接返回父節點中的父節點，在另一個子樹繼續搜索最近鄰。當回溯到根節點時，演算法結束。
6、此時保存的最近鄰節點就是最終的最近鄰。
如果現在想找(2,4.5)這點的最近鄰，該如何操作？
1、畫出二叉樹：
2、尋找(2,4.5)這點：
一個比較好的理解方式：首先找到第一個最近鄰，然後畫出一個圓。然後逐漸收縮圓的半徑，查看每次縮小後的圓是否能夠和矩形相交於一個更小的最近鄰點，如果有則更新。直到回到根節點。
❻ R語言-KNN演算法
1、K最近鄰(k-NearestNeighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
2、KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
3、KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。
簡言之，就是將未標記的案例歸類為與它們最近相似的、帶有標記的案例所在的類 。
原理及舉例
工作原理：我們知道樣本集中每一個數據與所屬分類的對應關系，輸入沒有標簽的新數據後，將新數據與訓練集的數據對應特徵進行比較，找出「距離」最近的k（通常k<20）數據，選擇這k個數據中出現最多的分類作為新數據的分類。
演算法描述
1、計算已知數據集中的點與當前點的距離
2、按距離遞增次序排序
3、選取與當前數據點距離最近的K個點
4、確定前K個點所在類別出現的頻率
5、返回頻率最高的類別作為當前類別的預測
距離計算方法有"euclidean"（歐氏距離）,」minkowski」（明科夫斯基距離）, "maximum"（切比雪夫距離）, "manhattan"（絕對值距離）,"canberra"（蘭式距離）, 或 "minkowski"（馬氏距離）等
Usage
knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)
Arguments
train
matrix or data frame of training set cases.
test
matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case.
cl
factor of true classifications of training set
k
number of neighbours considered.
l
minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even
ifkis increased by ties.)
prob
If this is true, the proportion of the votes for the
winning class are returned as attributeprob.
use.all
controls handling of ties. If true, all distances equal
to thekth largest are
included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.
kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))
參數：
formula A formula object.
train Matrix or data frame of training set cases.
test Matrix or data frame of test set cases.
na.action A function which indicates what should happen when the data contain 』NA』s.
k Number of neighbors considered.
distance Parameter of Minkowski distance.
kernel Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".
ykernel Window width of an y-kernel, especially for prediction of ordinal classes.
scale Logical, scale variable to have equal sd.
contrasts A vector containing the 』unordered』 and 』ordered』 contrasts to use
kknn的返回值如下：
fitted.values Vector of predictions.
CL Matrix of classes of the k nearest neighbors.
W Matrix of weights of the k nearest neighbors.
D Matrix of distances of the k nearest neighbors.
C Matrix of indices of the k nearest neighbors.
prob Matrix of predicted class probabilities.
response Type of response variable, one of continuous, nominal or ordinal.
distance Parameter of Minkowski distance.
call The matched call.
terms The 』terms』 object used.
iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)
library（kknn）
data（iris）
dim(iris)
m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))
建立訓練數據集
data.train<-iris[-val,]
建立測試數據集
data.test<-iris[val,]
調用kknn 之前首先定義公式
formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width
iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")
summary(iris.kknn)
# 獲取fitted.values
fit <- fitted(iris.kknn)
# 建立表格檢驗判類准確性
table(iris.valid$Species, fit)
# 繪畫散點圖，k-nearest neighbor用紅色高亮顯示
pcol <- as.character(as.numeric(iris.valid$Species))
pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]
二、R語言knn演算法
install.packages("class")
library(class)
對於新的測試樣例基於距離相似度的法則，確定其K個最近的鄰居，在K個鄰居中少數服從多數
確定新測試樣例的類別
1、獲得數據
2、理解數據
對數據進行探索性分析，散點圖
如上例
3、確定問題類型，分類數據分析
4、機器學習演算法knn
5、數據處理，歸一化數據處理
normalize <- function(x){
num <- x - min(x)
denom <- max(x) - min(x)
return(num/denom)
}
iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))
summary(iris_norm)
6、訓練集與測試集選取
一般按照3:1的比例選取
方法一、set.seed(1234)
ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))
iris_train <-iris[ind==1, 1:4]
iris_test <-iris[ind==2, 1:4]
train_label <-iris[ind==1, 5]
test_label <-iris[ind==2, 5]
方法二、
ind<-sample(1:150,50)
iris_train<-iris[-ind,]
iris_test<-iris[ind,1:4]
iris_train<-iris[-ind,1:4]
train_label<-iris[-ind,5]
test_label<-iris[ind,5]
7、構建KNN模型
iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)
8、模型評價
交叉列聯表法
table（test_label,iris_pred)
實例二
數據集
http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data
導入數據
dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)
names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')
table(wdbc.data$Diagnosis)## M = malignant, B = benign
wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))
❼ K-近鄰演算法簡介
1.K-近鄰(KNearestNeighbor,KNN)演算法簡介 ：對於一個未知的樣本，我們可以根據離它最近的k個樣本的類別來判斷它的類別。
以下圖為例，對於一個未知樣本綠色小圓，我們可以選取離它最近的3的樣本，其中包含了2個紅色三角形，1個藍色正方形，那麼我們可以判斷綠色小圓屬於紅色三角形這一類。
我們也可以選取離它最近的5個樣本，其中包含了3個藍色正方形，2個紅色三角形，那麼我們可以判斷綠色小圓屬於藍色正方形這一類。
3.API文檔
下面我們來對KNN演算法中的參數項做一個解釋說明：
'n_neighbors'：選取的參考對象的個數（鄰居個數），默認值為5，也可以自己指定數值，但不是n_neighbors的值越大分類效果越好，最佳值需要我們做一個驗證。
'weights': 距離的權重參數，默認uniform。
'uniform': 均勻的權重，所有的點在每一個類別中的權重是一樣的。簡單的說，就是每個點的重要性都是一樣的。
'distance'：權重與距離的倒數成正比，距離近的點重要性更高，對於結果的影響也更大。
'algorithm':運算方法，默認auto。
'auto'：根絕模型fit的數據自動選擇最合適的運算方法。
'ball_tree'：樹模型演算法BallTree
'kd_tree'：樹模型演算法KDTree
'brute'：暴力演算法
'leaf_size'：葉子的尺寸，默認30。只有當algorithm = 'ball_tree' or 'kd_tree'，這個參數需要設定。
'p'：閔可斯基距離，當p = 1時，選擇曼哈頓距離；當p = 2時，選擇歐式距離。
n_jobs：使用計算機處理器數目，默認為1。當n=-1時，使用所有的處理器進行運算。
4.應用案例演示
下面以Sklearn庫中自帶的數據集--手寫數字識別數據集為例，來測試下kNN演算法。上一章，我們簡單的介紹了機器學習的一般步驟：載入數據集 - 訓練模型 - 結果預測 - 保存模型。這一章我們還是按照這個步驟來執行。
[手寫數字識別數據集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits
5.模型的方法
每一種模型都有一些它獨有的屬性方法（模型的技能，能做些什麼事），下面我們來了解下knn演算法常用的的屬性方法。
6.knn演算法的優缺點
優點：
簡單，效果還不錯，適合多分類問題
缺點：
效率低（因為要計算預測樣本距離每個樣本點的距離，然後排序），效率會隨著樣本量的增加而降低。
❽ 核密度估計與k近鄰估計的區別
核密度估計實際上是表現一組數據的分布情況，轉錄組中用來展示所有樣本基因的表達量豐度分布。kNN是一種基本分類與回歸方法。
k-NN的輸入為實例的特徵向量，對應於特徵空間中的點，輸出為實例的類別，可以取多類。k近鄰實際上利用訓練數據集對特徵向量空間進行劃分，並作為其分類的「模型」。k值的選擇、距離度量及分類決策規則是k近鄰的三個基本要素。核密度估計（kerneldensityestimation）是在概率論中用來估計未知的密度函數，屬於非參數檢驗方法之一，Ruppert和Cline基於數據集密度函數聚類演算法提出修訂的核密度估計方法。
K最近鄰(k-NearestNeighbor，KNN)，是一種常用於分類的演算法，是有成熟理論支撐的、較為簡單的經典機器學習演算法之一。
❾ 簡單數字識別(knn演算法)
knn演算法，即k-NearestNeighbor，後面的nn意思是最近鄰的意思，前面的k是前k個的意思，就是找到前k個離得最近的元素
離得最近這個詞具體實現有很多種，我使用的是歐式幾何中的距離公式
二維中兩點x(x1,y1),y(x2,y2)間距離公式為sqrt( (x1-x2)^2+(y1-y2)^2 )
推廣到n維就是
x(x1,x2, … ,xn),y(y1,y2, … ,yn)
sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)
knn演算法是要計算距離的，也就是數字之間的運算，而圖像是png，jpg這種格式，並不是數字也不能直接參與運算，所以我們需要進行一下轉換
如圖所示一個數字8，首先要確定的是這一步我做的是一個最簡單的轉換，因為我假定背景和圖之間是沒有雜物的，而且整個圖只有一個數字（0-9）如果遇到其他情況，比如背景色不純或者有其他干擾圖像需要重新設計轉換函數
接下來就是最簡單的轉換，將圖片白色部分（背景）變0，有圖像的部分變1。轉換後的大小要合適，太小會影響識別准確度，太大會增加計算量。所以我用的是書上的32*32，轉換後結果如圖所示
這樣一來，圖片就變成了能進行計算的數字了。
接下來我們需要創建一個庫，這個庫裡面存著0-9這些數字的各種類似上圖的實例。因為我們待識別的圖像要進行對比，選出前k個最近的，比較的對象就是我們的庫。假定庫中有0-9十個數字，每個數字各有100個這種由0和1表示的實例，那麼我們就有了一共1000個實例。
最後一步就是進行對比，利用開頭說的歐式幾何距離計算公式，首先這個32*32的方陣要轉換成一個1*1024的1024維坐標表示，然後拿這個待識別的圖像和庫中的1000個實例進行距離計算，選出前k個距離最近的。比如50個，這50個裡面出現次數最多的數字除以50就是結果數字的概率。比如50個裡面數字8出現40次，那麼待識別數字是8的可能性就是40/50 = 80%
個人理解：
只能識別單個數字，背景不能有干擾。如果想多數字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉01的方法。
數字識別非常依賴庫中的圖像，庫中的圖像的樣子嚴重影響圖像的識別（因為我們是和庫中的一一對比找出距離最近的前k個），所以數字的粗細，高低，胖瘦等待都是決定性因素，建庫時一定全面考慮數字的可能樣子
計算量比較大，待識別圖像要和庫中所有實例一一計算，如果使用32*32，就已經是1024維了。如果庫中有1000個，那就是1024維向量之間的1000次計算，圖像更清晰，庫更豐富只會使計算量更大
對於其他可以直接計算距離的數值型問題，可以用歐式距離，也可以用其他能代表距離的計算公式，對於非數值型的問題需要進行合適的轉換，轉換方式很重要，我覺得首先信息不能丟失，其次要精確不能模糊，要實現圖片轉換前後是一對一的關系
參考資料：機器學習實戰 [美] Peter Harrington 人民郵電出版社
python源碼
import numpy
import os
from PIL import Image
import heapq
from collections import Counter
def pictureconvert(filename1,filename2,size=(32,32)):
#filename1待識別圖像，filename2 待識別圖像轉換為01txt文件輸出，size圖像大小，默認32*32
image_file = Image.open(filename1)
image_file = image_file.resize(size)
width,height = image_file.size
f1 = open(filename1,'r')
f2 = open(filename2,'w')
for i in range(height):
for j in range(width):
pixel = image_file.getpixel((j,i))
pixel = pixel[0] + pixel[1] + pixel[2]
if(pixel == 0):
pixel = 0
elif(pixel != 765 and pixel != 0):
pixel = 1
# 0代表黑色（無圖像），255代表白色（有圖像）
# 0/255 = 0,255/255 = 1
f2.write(str(pixel))
if(j == width-1):
f2.write('\n')
f1.close()
f2.close()
def imgvector(filename):
#filename將待識別圖像的01txt文件轉換為向量
vector = numpy.zeros((1,1024),numpy.int)
with open(filename) as f:
for i in range(0,32):
linestr = f.readline()
for j in range(0,32):
vector[0,32*i+j] = int(linestr[j])
return vector
def compare(filename1,filename2):
#compare直接讀取資源庫識別
#filename1資源庫目錄，filename2 待識別圖像01txt文檔路徑
trainingfilelist = os.listdir(filename1)
m = len(trainingfilelist)
labelvector = []
trainingmatrix = numpy.zeros((m, 1024), numpy.int8)
for i in range(0,m):
filenamestr = trainingfilelist[i]
filestr = filenamestr.split('.')[0]
classnumber = int(filestr.split('_')[0])
labelvector.append(classnumber)
trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)
textvector = imgvector(filename2)
resultdistance = numpy.zeros((1,m))
result = []
for i in range(0,m):
resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])
resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)
for i in resultindices:
result.append(labelvector[i])
number = Counter(result).most_common(1)
print('此數字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))
def distinguish(filename1,filename2,filename3,size=(32,32)):
# filename1 png，jpg等格式原始圖像路徑，filename2 原始圖像轉換成01txt文件路徑，filename3 資源庫路徑
pictureconvert(filename1,filename2,size)
compare(filename3,filename2)
url1 = "/Users/wang/Desktop/number.png"
url2 = "/Users/wang/Desktop/number.txt"
traininglibrary = "/Users/wang/Documents/trainingDigits"
distinguish(url1,url2,traininglibrary)
❿ 技術 | 文本聚類與分類
按照處理的對象和處理的方法不同，可將常見文本分類/聚類任務分為以下幾種：
① 文檔聚類： 把一組未知類別的文檔劃分為若干類別，例如將介紹奧運會的新聞都歸到某一類；
② 文檔分類： 給定一個文檔，將其劃分到預定義好的某一個類別中，例如將所有介紹奧運會的新聞都標記為「體育」；
③ 詞彙聚類： 把一組未知類別的詞彙劃分為若干類別，例如將各種運動的項目名稱（詞彙）都歸為一類；
④ 詞彙分類： 給定一個詞彙，將其劃分到預定義好的某一個類別中，例如將籃球、足球等都比較為球類，將打獵、射箭等都標記為射擊。
要實現上述目的，通常有以下幾個核心問題要解決：
1. 特徵選擇
1.1 用什麼作為特徵項
用於表示文本的基本單位通常稱為文本的特徵或特徵項。特徵項必須滿足：能夠標識文本內容、能夠將目標文本與其他文本相區分、個數不能太多、特徵項分離要比較容易實現。在中文文本中可以採用字、詞或短語作為表示文本的特徵項。
相比較而言，詞比字具有更強的表達能力，而詞和短語相比，詞的切分難度比短語的切分難度小得多。因此，目前大多數中文文本分類系統都採用詞作為特徵項，稱作特徵詞。這些特徵詞作為文檔的中間表示形式，用來實現文檔與文檔、文檔與用戶目標之間的相似度計算 。
1.2 選取哪些作為特徵項
如果把所有的詞都作為特徵項，那麼特徵向量的維數將過於巨大，從而導致計算量太大，在這樣的情況下，要完成文本分類幾乎是不可能的。特徵提取的主要功能是在不損傷文本核心信息的情況下盡量減少要處理的單詞數，以此來降低向量空間維數，從而簡化計算，提高文本處理的速度和效率。
特徵選取的方式有2種：用映射或變換的方法把原始特徵變換為較少的新特徵（將原始特徵用新特徵表示）；從原始特徵中挑選出一些最具代表性的特徵（只保留部分原始特徵，不產生新特徵），即根據某個特徵評估函數計算各個特徵的評分值，然後按評分值對這些特徵進行排序，選取若干個評分值最高的作為特徵詞，常見的特徵評估函數包括TF-IDF、信息增益、互信息等。
2. 文本表示
2.1 如何表示文檔
為了讓計算機能夠「計算」文本，就需要我們將文本數據轉換成計算機可以處理的結構化數據。常見的文本表示模型有布爾模型、向量空間模型、統計主題模型等。其中，向量空間模型概念簡單，把對文本內容的處理簡化為向量空間中的向量運算，並且它以空間上的相似度表達語義的相似度，直觀易懂，目前應用最廣。
2.2 如何確立權重
一篇文檔有很多詞，有些詞表達的語義很重要，有些相對次要，那麼如何確定哪些重要？哪些次要呢？因此，需要進一步對每個詞的重要性進行度量。常見的確立詞彙權重的演算法有TF-IDF、詞頻法等。
3. 相似性計算
要實現文本的分類和聚類，需要設計一種演算法計算出文檔與文檔、詞彙與詞彙之間的相似性。
3.1 文檔相似性
設定我們要比較X和Y間的差異，它們都包含了N個維的特徵，即X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）。下面來看看主要可以用哪些方法來衡量兩者的差異，主要分為距離度量和相似度度量。
a. 距離度量
距離度量（Distance）用於衡量個體在空間上存在的距離，距離越遠說明個體間的差異越大。常見的距離有歐幾里得距離(Euclidean Distance)、明可夫斯基距離(Minkowski Distance)、曼哈頓距離(Manhattan Distance)、切比雪夫距離(Chebyshev Distance)、馬哈拉諾比斯距離(Mahalanobis Distance)。
b. 相似性度量
相似度度量（Similarity），即計算個體間的相似程度，與距離度量相反，相似度度量的值越小，說明個體間相似度越小，差異越大。常見的相似性度量有向量空間餘弦相似度(Cosine Similarity)、皮爾森相關系數(Pearson Correlation Coefficient)、Jaccard相似系數(Jaccard Coefficient)、調整餘弦相似度(Adjusted Cosine Similarity)。
歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。下面藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：
從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標（即個體特徵維度的數值）直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似度cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。
根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題（因為餘弦相似度對絕對數值不敏感）。
3.2 詞彙相似性
目前我接觸的常見詞彙相似性的方法有：
a. 傳統圖情領域：基於共現頻次這一基本統計量衍生出來的，如association strength、inclusion index、Jaccard』s coefficient、Salton』s cosine（Ochiia系數）等；
b. 計算機領域：一是基於語義詞典的方法，即依據詞典分類體系挖掘所包含的詞義知識，常用的詞典包括Wordnet、Hownet等；二是基於語料庫的方法，這里的語料庫較為多元，例如網路預料、唐詩宋詞預料等；；三是進行詞向量化，如Word2vec。
4. 文本分類/聚類演算法
有了文本表示方法，又有了計算相似性的公式，下一步就可以在此基礎上討論文本分類/聚類的演算法了。
4.1 文本分類
醫生對病人進行診斷就是一個典型的分類過程，任何一個醫生都無法直接看到病人的病情，只能觀察病人表現出的症狀和各種化驗檢測數據來推斷病情，這時醫生就好比一個分類器，而這個醫生診斷的准確率，與他當初受到的教育方式（構造方法）、病人的症狀是否突出（待分類數據的特性）以及醫生的經驗多少（訓練樣本數量）都有密切關系。
分類器是對樣本進行分類的方法的統稱，包含決策樹、邏輯回歸、樸素貝葉斯、神經網路等演算法。舉個例子：假如你想區分小明是好學生還是壞學生，那麼區分「好學生」和「壞學生」就是一個分類任務。
4.1.1 K最鄰近
「別和其他壞學生在一起，否則你也會和他們一樣。」 —— 家長
主要思想是通過離待預測樣本最近的K個樣本的類別來判斷當前樣本的類別。從K最近鄰演算法的角度來看，就是讓目標樣本與其他正樣本距離更近、與其他負樣本距離更遠，從而使得其近鄰中的正樣本比例更高，更大概率被判斷成正樣本。
4.1.2 樸素貝葉斯
「根據以往抓獲的情況來看，十個壞學生有九個愛打架。」 —— 教導主任
「十個壞學生有九個愛打架」就意味著「壞學生」打架的概率P(打架|壞學生)=0.9，假設根據訓導處歷史記錄壞學生占學生總數P(壞學生)=0.1、打架發生的概率是P(打架)=0.09，那麼這時如果發生打架事件，就可以通過貝葉斯公式判斷出當事學生是「壞學生」的概率P(壞學生|打架)=P(打架|壞學生)×P(壞學生)÷P(打架)=1.0，即該學生100%是「壞學生」。
4.1.3 決策樹
「先看抽不抽煙，再看染不染頭發，最後看講不講臟話。」 ——社區大媽
假設「抽煙」、「染發」和「講臟話」是社區大媽認為的區分「好壞」學生的三項關鍵特徵，那麼這樣一個有先後次序的判斷邏輯就構成一個決策樹模型。在決策樹中，最能區分類別的特徵將作為最先判斷的條件，然後依次向下判斷各個次優特徵。決策樹的核心就在於如何選取每個節點的最優判斷條件，也即特徵選擇的過程。
而在每一個判斷節點，決策樹都會遵循一套IF-THEN的規則：
IF 「抽煙」 THEN -> 「壞學生」 ELSE IF 「染發」 THEN -> 「壞學生」 ELSE IF 「講臟話」 THEN -> 「壞學生」 ELSE -> 「好學生」
4.1.4 邏輯回歸
「上課講話扣1分，不交作業扣2分，比賽得獎加5分。」 ——紀律委員
我們稱邏輯回歸為一種線性分類器，其特徵就在於自變數x和因變數y之間存在類似y=ax+b的一階的、線性的關系。假設「上課講話」、「不交作業」和「比賽得獎」的次數分別表示為x1、x2、和x3，且每個學生的基礎分為0，那麼最終得分y=-1 x1-2 x2+5*x3+0。其中-1、-2和5分別就對應於每種行為在「表現好」這一類別下的權重。
對於最終得分y，邏輯回歸還通過Sigmoid函數將其變換到0-1之間，其含義可以認為是當前樣本屬於正樣本的概率，即得分y越高，屬於「表現好」的概率就越大。也就是說，假如紀律委員記錄了某位同學分別「上課講話」、「不交作業」和「比賽得獎」各一次，那麼最終得分y=-2-1+5=2，而對2進行Sigmoid變換後約等於0.88，即可知該同學有88%的概率為「好學生」。
4.1.5 支持向量機
「我想個辦法把表現差的學生都調到最後一排。」 ——班主任
支持向量機致力於在正負樣本的邊界上找到一條分割界線（超平面），使得它能完全區分兩類樣本的同時，保證劃分出的間隔盡量的大。如果一條分割界線無法完全區分（線性不可分），要麼加上鬆弛變數進行適當的容忍，要麼通過核函數對樣本進行空間上的映射後再進行劃分。對於班主任來講，調換學生們的座位就相當於使用了核函數，讓原本散落在教室里的「好」、「壞」學生從線性不可分變得線性可分了。
4.2 文本聚類
4.2.1 基於分層的聚類
hierarchical methods： 對數據集進行逐層分解，直到滿足某種條件為止。可分為「自底向上」和「自頂向下」兩種。例如「自底向上」指初始時每個數據點組成一個單獨的組，在接下來的迭代中，按一定的距離度量將相互鄰近的組合並成一個組，直至所有的記錄組成一個分組或者滿足某個條件為止。代表演算法有：BIRCH，CURE，CHAMELEON等。自底向上的凝聚層次聚類如下圖所示。
4.2.2 基於劃分的聚類
partitioning methods： 給定包含N個點的數據集，劃分法將構造K個分組，每個分組代表一個聚類，這里每個分組至少包含一個數據點，每個數據點屬於且僅屬於一個分組。對於給定的K值，演算法先給出一個初始的分組方法，然後通過反復迭代的方法改變分組，使得每一次改進之後的分組方案較前一次好，這里好的標准在於同一組中的點越近越好，不同組中的點越遠越好。代表演算法有：K-means，K-medoids，CLARANS。K-means聚類過程圖解如下：
4.2.3 基於密度的聚類
density-based methods： 基於密度的方法的特點是不依賴於距離，而是依賴於密度，從而克服基於距離的演算法只能發現「球形」聚簇的缺點。其核心思想在於只要一個區域中點的密度大於某個閾值，就把它加到與之相近的聚類中去。代表演算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。DBSCAN的聚簇生成過程的簡單理解如下圖。
4.2.3 基於網格的聚類
gird-based methods： 這種方法通常將數據空間劃分成有限個單元的網格結構，所有的處理都是以單個的單元為對象。這樣做起來處理速度很快，因為這與數據點的個數無關，而只與單元個數有關。代表演算法有：STING，CLIQUE，WaveCluster。基於Clique的聚類過程可直觀如下圖進行理解。
4.2.4 基於模型的聚類
model-based methods： 基於模型的方法給每一個聚類假定一個模型，然後去尋找能很好的擬合模型的數據集。模型可能是數據點在空間中的密度分布函數或者其它。這樣的方法通常包含的潛在假設是：數據集是由一系列的潛在概率分布生成的。通常有兩種嘗試思路：統計學方法和神經網路方法。其中，統計學方法有COBWEB演算法、GMM(Gaussian Mixture Model)，神經網路演算法有SOM(Self Organized Maps)演算法。下圖是GMM過程的一個簡單直觀地理解。
4.2.5 基於圖論的聚類
圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。典型演算法有譜聚類。
聚類問題的研究不僅僅局限於上述的硬聚類，即每一個數據只能被歸為一類，模糊聚類也是聚類分析中研究較為廣泛的一個分支。模糊聚類通過隸屬函數來確定每個數據隸屬於各個簇的程度，而不是將一個數據對象硬性地歸類到某一簇中。目前已有很多關於模糊聚類的演算法被提出，如著名的FCM演算法等。