分類是在一群已經知道類別標號的樣本中，訓練一種分類器，讓其能夠對某種未知的樣本進行分類，分類演算法屬于一種有監督的學習，分類演算法的分類程序就是建立一種分類模型來描述預定的資料集或概念集，通過分析由屬性描述的資料庫元組來構造模型，分類的目的就是使用分類對新的資料集進行劃分，其主要涉及分類規則的準確性、過擬合、矛盾劃分的取舍等，
————————————————
聚類是一種將資料點按一定規則分群（分組）的機器學習技術，其主要研究資料間邏輯上或物理上的相互關系，聚類分析本身不是一個特定的演算法，而是要解決的一般任務，它可以通過各種演算法來實作，這些演算法在理解群集的構成以及如何有效地找到它們方面存在顯著差異，由聚類所組成的簇是一組資料物件的集合，這些物件與同一簇中的物件彼此類似，與其他簇中的物件相異，其分析結果不僅可以揭示資料間的內在聯系與區別，還可以為進一步的資料分析與知識發現提供重要依據，
監督學習：當我們根據一組給定的預測因子變數或自變數去預測一個目標變數時，這些問題被稱為監督學習問題，
無監督學習：沒有任何固定目標變數的這些問題被稱為無監督學習問題，在這些問題中，我們只有自變數而沒有目標/因變數，
1、K-Means 聚類演算法原理詳解：
簡單來說K-Means 聚類演算法接受一個未標記的資料集，然后將資料聚類成不同的組，同時，k-means演算法也是一種無監督學習，
簇的兩個屬性：聚類的主要目的不僅僅是創建簇，而是創建好的和有意義的簇，
1）組中的所有資料點應該彼此相似；
2）來自不同組的資料點應盡可能不同；
簇第一個屬性：Inertia評估，Inertia實際上計算簇內所有點到該簇的質心的距離的總和，我們為所有簇計算這個總和，最終Inertia值是所有這些距離的總和，簇內的這個距離稱為簇內距離(intracluster distance.)，因此，Inertia為我們提供了簇內距離的總和：
現在，你認為一個好的簇的Inertia值應該是什么？小的Inertia好還是大的Inertia好？我們希望同一簇中的點彼此相似，因此它們之間的距離應盡可能小，記住這一點，Inertia越小，聚類越好，
簇第二個屬性：Dunn Index，我們現在知道Inertia試圖最小化簇內距離，它正試圖劃分更緊湊的簇，換句話說如果一個簇的質心與該簇中的點之間的距離很小，則意味著這些點彼此更接近，因此，Inertia可確保滿足簇的第一個屬性，但它并不關心第二個屬性，不同的簇應盡可能彼此不同，這就是Dunn Index可以用來評估的地方，
除了質心和點之間的距離，Dunn Index還考慮了兩個簇之間的距離，兩個不同簇的質心之間的距離稱為簇間距離(inter-cluster distance)，Dunn Index指數的公式：
Dunn Index是簇間距離的最小值與簇內距離的最大值之比，我們希望最大化Dunn Index，Dunn Index的值越大，簇就越好，為了最大化Dunn Index的值，分子應該是最大的，在這里，我們采用最小的簇間距離，因此，即使是最近的簇之間的距離也應該更大，這最終將確保簇彼此遠離，此外，分母應該是最小的，以最大化Dunn Index，在這里，我們采取最大的簇內距離，同樣，這里的直覺也是一樣的，簇質心和點之間的最大距離總和應該最小，這最終將確保劃分的簇緊湊，
什么是K-means聚類：
回想一下簇的第一個屬性，它表明簇中的點應該彼此相似，因此，我們的目標是最小化簇內點之間的距離，有一種演算法試圖通過它們的質心最小化簇中點的距離,那就是K-means聚類技術，K-means是一種基于質心的演算法，或基于距離的演算法，我們計算將點分配給一個簇的距離，在K-means中，每個聚類都與一個質心相關聯，K-means演算法的主要目的是最小化點與它們各自的簇質心之間的距離之和，
“求點群中心的演算法”：歐氏距離（Euclidean Distance）：（差的平方和的平方根）
舉個例子來了解K-means實際上是如何作業的：
我們有這8個點，我們想要應用K-means來為這些點劃分簇，下面將演示我們是怎樣做到的，
第一步：選擇簇的數目k
K-means的第一步是選擇簇的數目k，
第二步：從資料中選擇k個隨機點作為質心
接下來，我們為每個簇隨機選擇質心，假設我們想要有2個簇，所以k在這里等于2，然后我們隨機選擇質心：這里，紅色和綠色圓圈代表這些簇的質心，
第三步：將所有點分配給到某個質心距離最近的簇
一旦我們初始化了質心，我們就將每個點分配給到某個質心距離最近的簇：在這里，你可以看到更接近紅點的點被分配給紅色簇，而更接近綠點的點被分配給綠色簇，
第四步：重新計算新形成的簇的質心
現在，一旦我們將所有點分配到任一簇中，下一步就是計算新形成的簇的質心：在這里，紅色和綠色叉號是新的質心，
第五步：重復第三步和第四步
然后我們重復第三步和第四步：計算質心并基于它們與質心的距離將所有點分配給簇的步驟是單次迭代，但我們什么時候應該停止這個程序？它不能永遠運行下去對吧？
停止K-means聚類的標準，基本上有三種停止標準可用于停止K-means演算法：新形成的簇的質心不會改變資料點保留在同一個簇中達到最大迭代次數如果新形成的簇的質心沒有變化，我們就可以停止演算法，即使在多次迭代之后，所有簇都還是相同的質心，我們可以說該演算法沒有學習任何新模式，并且它是停止訓練的標志，另一個明顯的跡象表明，在多次迭代訓練的之后，如果資料點仍然都在同一簇中，我們應該停止訓練程序，最后，如果達到最大迭代次數，我們可以停止訓練，假設我們將迭代次數設定為100，在停止之前，該程序將重復100次迭代，
演算法實作步驟（總結）：
1. 確定要聚類的數量，并隨機初始化它們各自的中心點（質心）；
2. 計算每個點分別到k個聚類中心的聚類，然后將該點分到最近的聚類中心，這樣就行成了k個簇；
3. 再重新計算每個簇的質心（均值，即向量各維取平均）；
4. 重復以上2~3步，直到質心的位置不再發生變化或者達到設定的迭代次數，
K-means聚類演算法面臨的挑戰
1）使用K-means時我們面臨的普遍挑戰之一是簇的大小不同，假設我們有以下幾點：
與中心簇相比，左側和最右側的簇的點的數量比較少，現在，如果我們在這些點上應用K-means聚類，結果將是這樣的：
2）K-means的另一個挑戰是當原始點的密度不同時，比如下面這些原始點：
這里，紅色簇中的點比較松散，而其余簇中的點緊密地堆積在一起，現在，如果我們在這些點上應用K-means，我們將得到這樣的簇：
我們可以看到緊湊的點已分配給同一個簇，而實際松散分布但在同一簇中的點卻分配給不同的簇，效果并不理想，我們能做些什么呢？
解決方案一：是使用更多的簇進行劃分，因此，在所有上述場景中，我們可以擁有更多的簇，而不是使用3個簇，也許設定k = 10可能會產生更有意義的簇，
解決方案二：K-means ++為K-means聚類選擇初始簇質心，還記得我們如何在K-means聚類中隨機初始化質心嗎？這也可能有問題，因為我們每次都可能得到不同的簇，因此，為了解決隨機初始化的這個問題，有一種稱為K-means ++的演算法可用于為K-means選擇初始值或初始簇質心，
K-means++演算法介紹：
在某些情況下，如果簇的初始化不合適，K-means可能導致產生壞的簇，這就是K-means ++產生作用的地方，它指定了在使用標準K-means聚類演算法向前推進之前初始化簇質心的程序，使用K-means ++演算法，我們優化了隨機選擇簇質心的步驟，在使用K-means ++初始化時，即(init='K-means++')，我們更有可能找到與最佳K-means解決方案競爭的解決方案，
使用K-means ++初始化質心的步驟是：
1）從我們想要聚類的資料點隨機均勻地選擇第一個簇；這類似于我們在K-means中所做的，但不是隨機挑選所有質心，而是在這里選擇一個質心；
2）接下來，我們計算每個資料點到已經選擇的簇的質心的距離(D(x))；
3）然后，從資料點中選擇新的簇質心；
4）重復步驟2和3，直到選擇了k個簇，
舉個例子來更清楚地理解這一點，假設我們有以下幾點，我們想在這里劃分3個簇：
現在，第一步是隨機選擇一個資料點作為簇質心：
假設我們選擇綠點作為初始質心，現在，我們將使用此質心計算每個資料點與質心的距離(D(x))：
下一個質心將是其平方距離(D(x)2)離當前質心最遠的那個點：
在這種情況下，紅點將被選為下一個質心，現在，為了選擇最后一個質心，我們將計算所有點到其最近的質心的距離，其中具有最大平方距離的點作為下一個質心：
我們將選擇最后一個質心為：
初始化質心后，我們可以繼續使用K-means演算法，使用K-means ++初始化質心往往會改善聚類結果，雖然相對于隨機初始化而言計算成本很高，但隨后的K-means通常會更快地收斂，
如何在K-means聚類中選擇正確的簇的個數？
每個人在使用K-means時最常見的疑問之一就是如何選擇合適數量的簇，那么，讓我們看看一種技術，它將幫助我們為K-means演算法選擇正確的簇的個數，老實說，我們可以擁有任意數量的簇，你能猜出可能的最大簇數是多少嗎？我們想到將每個點分配給一個單獨的簇，因此，在這種情況下，簇的數量將等于點數或觀察數量，所以，最大可能的簇數將等于資料集中的觀察數，
但我們如何才能確定最佳簇數？我們可以做的一件事是繪制圖形，其中x軸表示簇的數量，y軸將是評估度量，我們暫時說是Inertia（樣本到其最近的聚類中心的平方距離的總和），也可以選擇任何其他評估指標，如Dunn Index；代價函式/畸變函式（Distortion function:要使k-means最后的分類結果最好，也就是要是K-均值最小化，是要最小化所有的資料點與其所關聯的聚類中心點之間的距離之和）；...... ，
接下來，我們將從一個小的簇值開始，比如說2使用2個簇訓練模型，計算該模型的Inertia，最后將其繪制在上圖中，假設我們得到Inertia大約為1000：
現在，我們將增加簇的數量，再次訓練模型，并繪制Inertia，這是我們得到的圖：
當我們將簇值從2更改為4時，Inertia急劇下降，隨著我們進一步增加簇的數量，Inertia的下降變得緩慢并最終變得穩定，Inertia的減小幅度變為常數時對應的簇的個數可以選擇作為我們資料的正確簇的個數，
在這里，我們可以選擇6到10之間的任意數量的簇的個數，我們可以有7個，8個甚至9個簇，你還必須在確定簇的個數時查看計算成本，如果我們增加簇的數量，計算成本也會增加，因此，如果你沒有高計算資源，我的建議是選擇較少數量的簇，K值的選擇主要還是根據經驗以及利用k-means聚類的目的來決定，
【補充】K-Medians 是與 K-Means 有關的另一個聚類演算法，除了不是用均值而是用組的中值向量來重新計算組中心，這種方法的優點是對例外值不敏感（因為使用中值），但對于較大的資料集要慢得多，因為在計算中值向量時，每次迭代都需要對資料進行排序，
k-means 演算法的優點：
1）法簡單快捷，容易理解，速度快，真正在做的是計算點和組中心之間的距離：非常少的計算！因此它具有線性復雜度 O(n)；
2）對所有的資料樣本都進行聚類；
3）對滿足高斯分布、均勻分布的資料型別聚類效果表較好，適合常規資料集，
k-means演算法的缺點：
1）需要事先確定聚類個數；
2）對初始聚類中心敏感，而K-means 也是從隨機選擇的聚類中心開始，所以可能在不同的演算法中產生不同的聚類結果(結果可能不可重復并缺乏一致性，其他聚類方法更加一致)；
3）對孤立點和噪聲點相對敏感，
4）很難發現任意形狀的簇
2、DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）：
是一種基于密度的空間聚類演算法，與KMeans演算法不同，它不需要確定聚類的數量，而是基于資料推測聚類的數目，它能夠針對任意形狀產生聚類， 該演算法將具有足夠密度的區域劃分為簇，并在具有噪聲的空間資料庫中發現任意形狀的簇，它將簇定義為密度相連的點的最大集合，
基本概念：
1.epsoiln-neighborhood(簡稱e-nbhd）密度空間：表示半徑為e且含有若干個點的nbhd，密度等于包含點的個數/空間大小，圖中中心點是（3,2），半徑epsilon是0.5，根據式子密度=點的個數/面積，可以計算得到上圖中密度=31/2pi(0.5)*(0.5)=62/pi，這個數字本身意義不大，但通過計算某一小區域的密度，橫向對比可以得知整個區域的密度分布，由此相近的點可聚類到同一區域內，
2. DBSCAN演算法需要首先確定兩個引數：
1）epsilon：在一個點周圍鄰近區域的半徑
2）minPts：鄰近區域內至少包含點的個數
3. 根據以上兩個引數，結合epsilon-neighborhood的特征，可以把樣本中的點分成三類：
核點（core point）：滿足NBHD(p,epsilon)>=minPts，則為核樣本點
邊緣點（border point）：NBHD(p,epsilon)<minPts，但是該點可由一些核點獲得（density-reachable或者directly-reachable）
離群點（Outlier）：既不是核點也不是邊緣點，則是不屬于這一類的點
上圖中A表示核心物件；B,C表示邊界點；N表示離群點，我們可以認為A是系統在眾多樣本點中隨機選中一個，圍繞這個被選中的樣本點畫一個圓，規定這個圓的半徑以及圓內最少包含的樣本點，如果在指定半徑內有足夠多的樣本點在內，那么這個圓圈的圓心就轉移到這個內部樣本點，繼續去圈附近其它的樣本點，類似傳銷一樣，繼續去發展下線，等到這個滾來滾去的圈發現所圈住的樣本點數量少于預先指定的值，就停止了，那么我們稱最開始那個點為核心點，如A，停下來的那個點為邊界點，如B、C，沒得滾的那個點為離群點，如N，
基于密度這點有什么好處呢，我們知道kmeans聚類演算法只能處理球形的簇，也就是一個聚成實心的團（這是因為演算法本身計算平均距離的局限），但往往現實中還會有各種形狀，比如下面兩張圖，環形和不規則形，這個時候，那些傳統的聚類演算法顯然就悲劇了，于是就思考，樣本密度大的成一類唄，吶這就是DBSCAN聚類演算法，
如果是傳統的Kmeans聚類，我們也來看一下效果：可以看出DBSCAN演算法基于密度聚類的優勢就明顯了，
DBSCAN演算法迭代可視化展示：https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
DBSCAN的實作步驟：（在已知epsilon和minPts的前提下）
1）任意選擇一個點（既沒有指定到一個類也沒有特定為外圍點），計算它的NBHD(p,epsilon)判斷是否為核點，如果是，在該點周圍建立一個類，否則，設定為外圍點，
2）遍歷其他點，直到建立一個類，把directly-reachable的點加入到類中，接著把density-reachable的點也加進來，如果標記為外圍的點被加進來，修改狀態為邊緣點，
3）重復步驟1和2，直到所有的點滿足在類中（核點或邊緣點）或者為外圍點
引數選擇：
epsilon：半徑，是最難指定的 ，大了，圈住的就多了，簇的個數就少了；反之，簇的個數就多了，這對我們最后的結果是有影響的，我們這個時候K距離可以幫助我們來設定半徑r，也就是要找到突變點，比如有一組資料：首先選中一個點，計算它和所有其他的點的距離，從小到大排序，d1，d2，d3，d4，......，可以發現d3和d4之間的差異很大，于是認為前面的距離是比較合適的，那么就可以指定出r半徑的大小為0.12，
data = https://www.cnblogs.com/bonheur/p/【0.1，0.11，0.12，0.3，0.31，0.32，......】
d1 d2 d3 d4 d5 d6
以上雖然是一個可取的方式，但是有時候比較麻煩 ，大部分還是都試一試進行觀察，用k距離需要做大量實驗來觀察，很難一次性把這些值都選準，
MinPts:這個引數就是圈住的點的個數，也相當于是一個密度，一般這個值都是偏小一些，然后進行多次嘗試
總結:
（1）epsilon不變的情況下，調整minPts的大小，則minPts越大，NBHD越密集，產生離群點越多，
（2）在minPts不變的情況下，epsilon越小，聚類越密集，產生離群點越多，
（3）epsilon越小，minPts越多，則密度越高，產生聚類越密集，
DBSCAN最大的特點是事先不必確定聚類的種類，通過基于密度的方法，聚類并找出離群點；不僅需要對大部分在類中的點分析，也需要對離群點分析.
DBSCAN 演算法的優點：
1）不需要指定簇個數，即不需事先知道要形成的簇類數量；
2）可以發現任意形狀的簇類（非線性聚類）；
3）能夠識別出噪聲點，擅長找到離群點（檢測任務），
DBSCAN 演算法的缺點：
1）演算法聚類時采用全域性的表征密度引數，當空間聚類的密度不均勻、聚類間距差相差很大時，聚類質量較差；
2）演算法須指定兩個引數：半徑和最小密度閾值，所以對用戶定義的引數敏感，細微的不同都可能導致差別很大的結果，而引數的選擇無規律可循，難以選擇，只能靠經驗確定；
3）演算法對稀疏的高維資料性能差，因對高維資料，歐幾里得密度定義不能很好理解（可以做降維）；
4）對不滿足給定條件的樣本點會作為噪聲點剔除；
5）因演算法直接對資料庫進行操作，當資料量增大時，要求較大的記憶體支持且I/O消耗也很大；
6）演算法的計算復雜度較高，
聚類演算法中最常用的評估方法——輪廓系數（Silhouette Coefficient）：詳解參考(機器學習之模型評估詳解)文章，
————————————————
參考文章：
1. https://baijiahao.baidu.com/s?id=1643772188521178944&wfr=spider&for=pc
https://baijiahao.baidu.com/s?id=1625408992304959354&wfr=spider&for=pc
https://blog.csdn.net/songguangfan/article/details/90770289
https://www.sohu.com/a/286841039_654419
5. https://blog.csdn.net/huacha__/article/details/81094891
6. https://blog.dominodatalab.com/topology-and-density-based-clustering/?tdsourcetag=s_pcqq_aiomsg
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/177281.html
標籤：Python
上一篇：笨方法學python準備作業
下一篇：分布式任務佇列 1