聚群演算法

A. 聚類演算法--DBSCAN

       DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有雜訊的基於密度的聚類方法)是一種很典型的密度聚類演算法，和K-Means，BIRCH這些一般只適用於凸樣本集的聚類相比，DBSCAN既可以適用於凸樣本集，也可以適用於非凸樣本集。 基於密度的帶有雜訊的空間聚類，可用於異常值監測，通俗來說就是基於密度的聚類演算法 ！

        聚類就是對大量未知標注的數據集，按數據的內在相似性將數據集劃分為多個類別，使類別內的數據相似度較大而類別間的數據相似度較小。聚類演算法是無監督的演算法。

DBSCAN演算法的目的： 是基於密度尋找被低密度區域分離的高密度樣本分為三類： 

稠密區域內部的點（核心點）： 在半徑Eps內含有超過MinPts數目的點 

稠密區域邊緣上的點（邊緣點）： 在半徑Eps內點的數量小於MinPts（即不是核心點），但是其鄰域內至少包含一個核心點 

稀疏區域中的點（雜訊或者背景點）： 任何不是核心點或者邊界點的點

特點 ： 發現任意形狀的簇、對雜訊數據不敏感、一次掃描、需要密度參數作為停止條件，計算量大和復雜度高 。

    DBSCAN是一種基於密度的聚類演算法，這類密度聚類演算法一般假定類別可以通過樣本分布的緊密程度決定。同一類別的樣本，他們之間的緊密相連的，也就是說，在該類別任意樣本周圍不遠處一定有同類別的樣本存在。

    通過將緊密相連的樣本劃為一類，這樣就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃為各個不同的類別，則我們就得到了最終的所有聚類類別結果。

    前面我們定性描述了密度聚類的基本思想，在這里我們就看看DBSCAN是如何描述密度聚類的。DBSCAN是基於一組鄰域來描述樣本集的緊密程度的，參數(ϵϵ, MinPts)用來描述鄰域的樣本分布緊密程度。其中，ϵϵ描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為ϵϵ的鄰域中樣本個數的閾值。

    假設我們的樣本集是D=(x1,x2,...,xm)(x1,x2,...,xm)，則DBSCAN具體的密度描述定義如下：

        1） ϵϵ-鄰域：對於xj∈Dxj∈D，其ϵϵ-鄰域包含樣本集D中與xjxj的距離不大於ϵϵ的子樣本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 這個子樣本集的個數記為|Nϵ(xj)||Nϵ(xj)|

        2）核心對象：對於任一樣本xj∈Dxj∈D，如果其ϵϵ-鄰域對應的Nϵ(xj)Nϵ(xj)至少包含MinPts個樣本，即如果|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts，則xjxj是核心對象。

        3）密度直達：如果xixi位於xjxj的ϵϵ-鄰域中，且xjxj是核心對象，則稱xixi由xjxj密度直達。注意反之不一定成立，即此時不能說xjxj由xixi密度直達, 除非且xixi也是核心對象。

        4）密度可達：對於xixi和xjxj,如果存在樣本樣本序列p1,p2,...,pTp1,p2,...,pT,滿p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直達，則稱xjxj由xixi密度可達。也就是說，密度可達滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT−1p1,p2,...,pT−1均為核心對象，因為只有核心對象才能使其他樣本密度直達。注意密度可達也不滿足對稱性，這個可以由密度直達的不對稱性得出。

       5）密度相連：對於xixi和xjxj,如果存在核心對象樣本xkxk，使xixi和xjxj均由xkxk密度可達，則稱xixi和xjxj密度相連。注意密度相連關系是滿足對稱性的。

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其ϵϵ-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達的樣本在以紅色核心對象為中心的超球體內，如果不在超球體內，則不能密度直達。圖中用綠色箭頭連起來的核心對象組成了密度可達的樣本序列。在這些密度可達的樣本序列的ϵϵ-鄰域內所有的樣本相互都是密度相連的。

    DBSCAN的聚類定義很簡單： 由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇 。

    這個DBSCAN的簇裡面可以有一個或者多個核心對象。如果只有一個核心對象，則簇裡面其他的非核心對象樣本都在這個核心對象的ϵϵ-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的ϵϵ-鄰域中一定有一個其他的核心對象，否則這個核心對象無法密度可達。這些核心對象的ϵϵ-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

       那麼怎麼才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。基本上這就是DBSCAN演算法的主要內容了，但是我們還有三個問題沒有考慮。

    1）一些異常樣本點或者說少量游離於簇外的樣本點，這些點不在任何一個核心對象的周圍，在DBSCAN中，我們一般將這些樣本點標記為噪音點。

    2）距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般採用最近鄰思想，採用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類演算法的最近鄰思想完全相同。對應少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，比如樣本量較大，則一般採用KD樹或者球樹來快速的搜索最近鄰。

    3）某些樣本可能到兩個核心對象的距離都小於ϵϵ，但是這兩個核心對象由於不是密度直達，又不屬於同一個聚類簇，那麼如何界定這個樣本的類別呢？一般來說，此時DBSCAN採用先來後到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說DBSCAN的演算法不是完全穩定的演算法。

DBSCAN通過檢查數據集中的每個對象的ε-鄰域來尋找聚類，如果一個點p的ε-鄰域包含對於m個對象，則創建一個p作為核心對象的新簇。然後，DBSCAN反復地定址這些核心對象直接密度可達的對象，這個過程可能涉及密度可達簇的合並。當沒有新的點可以被添加到任何簇時，該過程結束。演算法中的ε和m是根據先驗只是來給出的。

DBSCAN聚類演算法原理的基本要點：

    1.DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反應了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里得距離來進行度量。

    2.DBSCAN演算法需要用戶輸入2個參數： 一個參數是半徑(Eps)，表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量(MinPts)。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點 。

    3.DBSCAN聚類聚類使用到一個 k-距離 的概念，k-距離是指：給定數據集P={p(i); i=0,1,……n},對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中 所有點之間的距離 ， 距離按照從小到大的順序排序 ，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}， 則d(k)就被稱為k-距離 。也就是說， k-距離是點p(i)到所有點(除了p(i)點)之間距離第K近的距離 。對待聚類集合中 每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)} 。

    4.根據經驗計算半徑Eps：根據得到的所有點的 k-距離集合E ，對集合E進行 升序排序 後得到k-距離集合 E' ，需要擬合一條排序後的E'集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察， 將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值 。

    5.根據經驗計算最少點的數量MinPts： 確定MinPts的大小，實際上也是確定k-距離中k的值 ，DBSCAN演算法中取k=4，則MinPts=4。

    6.另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變。Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為離群點，MinPts過小，會導致發現大量的核心點。

我們需要知道的是，DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。

對於演算法的實現，我們概要地描述一下實現的過程：

    1.解析樣本數據文件。

    2.計算每個點與其他所有點之間的歐幾里得距離。

    3.計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。

    4.將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢

    5.根據散點圖確定半徑Eps的值

    6.根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與核心點距離小於半徑Eps的點映射。

    7.根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，並得到離群點。

    8.將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。

    9.選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其離群點，使用散點圖對比聚類效果。

    和傳統的K-Means演算法相比，DBSCAN最大的不同就是不需要輸入類別數K，當然它最大的優勢是可以發現任意形狀的聚類簇，而不是像K-Means，一般僅僅使用於凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH演算法類似。

    那麼我們什麼時候需要用DBSCAN來聚類呢？一般來說，如果數據集是稠密的，並且數據集不是凸的，那麼用DBSCAN會比K-Means聚類效果好很多。 如果數據集不是稠密的，則不推薦用DBSCAN來聚類 。

    優點：

        1）可以對任意形狀的稠密數據集進行聚類，相對的，K-Means之類的聚類演算法一般只適用於凸數據集。不用指明類別的數量，能靈活找到並分離各種形狀和大小的類。能很好地處理雜訊和離群點。

        2）可以在聚類的同時發現異常點，對數據集中的異常點不敏感。

        3）聚類結果沒有偏倚，相對的，K-Means之類的聚類演算法初始值對聚類結果有很大影響。

    缺點：

         1）在不同密度的類方面有一定難度。如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合( HDBSCAN適合密度不均勻問題 )。

        2）如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰近時建立的KD樹或者球樹進行規模限制來改進。當數據量增大時，要求較大的內存支持I/O消耗也很大；演算法聚類效果依賴與距離公式選取，實際應用中常用歐式距離，對於高維數據，存在「維數災難」。

        3）調參相對於傳統的K-Means之類的聚類演算法稍復雜，主要需要對距離閾值ϵϵ，鄰域樣本數閾值MinPts聯合調參，不同的參數組合對最後的聚類效果有較大影響。

        4）對於從兩類均可達的邊界點，由於各個點是被隨機訪問的，因此DBSCAN不能保證每次都返回相同的聚類。

    DBSCAN類的重要參數分為兩類，一類是DBSCAN演算法本身的參數，一類是最近鄰度量的參數，下面我們對這些參數做一個總結。

    1） eps： DBSCAN演算法參數，即我們的ϵ-鄰域的距離閾值，和樣本距離超過ϵ的樣本點不在ϵ-鄰域內。 默認值是0.5 ，一般需要通過在多組值裡面選擇一個合適的閾值。eps過大，則更多的點會落在核心對象的ϵ-鄰域，此時我們的類別數可能會減少，本來不應該是一類的樣本也會被劃分為一類。反之則類別數可能會增大，本來是一類的樣本卻被劃分開。

   2） min_samples： DBSCAN演算法參數，即樣本點要成為核心對象所需要的ϵ-鄰域的樣本數閾值。默認值是5。一般需要通過在多組值裡面選擇一個合適的閾值。通常和eps一起調參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內部分本來是一類的樣本可能會被標為噪音點，類別數也會變多。反之min_samples過小的話，則會產生大量的核心對象，可能會導致類別數過少。

    3） metric： 最近鄰距離度量參數。可以使用的距離度量比較多，一般來說DBSCAN使用默認的歐式距離(即p=2的閔可夫斯基距離)就可以滿足我們的需求。可以使用的距離量度參數有：歐式距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、帶權重閔可夫斯基距離、標准化歐式距離、馬氏距離。

還有一些其他不是實數的距離度量，一般在DBSCAN演算法用不上，這里也就不列了。

    4）algorithm：最近鄰搜索演算法參數，演算法一共有三種，第一種是蠻力實現，第二種是KD樹實現，第三種是球樹實現。這三種方法與K近鄰法(KNN)原理中演算法一致。對於這個參數，一共有4種可選輸入，"brute"對應第一種蠻力實現,"kd_tree"對應於第二種KD樹實現，"ball_tree"對應於第三種的球樹實現，"auto"則會在上面三種演算法中做權衡，選擇一個擬合最好的最優演算法。 需要注意的是，如果輸入樣本特徵是稀疏的時候，無論我們選擇哪種演算法，最後sklearn都會去用蠻力實現"brute" 。個人的經驗，一般情況使用默認的"auto"就夠了。如果數據量很大或者特徵也很多，用「auto」建樹時間可能會很長，效率不高，建議選擇KD樹實現「kd_tree」,此時如果發現"kd_tree"速度比較慢或者已經知道樣本分布不是很均勻時，可以嘗試用"ball_tree"。

    5） leaf_size ：最近鄰搜索演算法參數，為使用KD樹或者球樹時，停止建子樹的葉子節點數量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數越深，建樹時間越長，反之，則生成的KD樹或者球樹會小，層數較淺，建樹時間較短。默認是30，因為這個值一般隻影響演算法是運行速度和使用內存大小，因此一般情況下可以不管它。

    6） p ：最近鄰距離度量參數。只有用於閔可夫斯基距離和帶權重閔客服斯基距離中p值的選擇，p=1為曼哈頓距離，p=2為歐式距離。如果使用默認的歐式距離不需要管這個參數。

以上就是DBSCAN類的主要參數介紹，其實需要調參的就是兩個參數eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響。

B. 類聚群分是什麼意思

「類聚群分」是一個源自傳統哲學和自然科學領域的概念，其核心含義是指根據事物的特性、屬性或功能進行分類和歸類，將具有相似性質的事物聚集在一起，同時將不同性質的事物區分開來。 這一概念廣泛應用於哲學、生物學、社會學以及現代數據科學等多個領域。從本質上講，「類聚群分」體現了一種系統化的思維方式，旨在通過觀察和分析，對復雜的現象進行簡化和組織，從而幫助人們更好地理解和處理世界。

具體來說，「類聚」指的是將具有相同或相似特徵的事物歸為一類，強調的是共性與統一性；而「群分」則側重於區分不同的類別，突出差異性和多樣性。這一思想在古代中國的《周易》中已有體現，例如通過八卦的符號系統對自然現象進行分類描述。在生物學中，「類聚群分」的理念被用來構建物種分類體系，如林奈的雙名法將生物按照界、門、綱、目、科、屬、種等層次進行劃分。這種分類方法不僅揭示了生物之間的親緣關系，還為科學研究提供了清晰的框架。

在現代社會中，「類聚群分」的思想得到了進一步的發展和應用。例如，在機器學習和數據分析領域，聚類演算法（Clustering）正是基於「類聚群分」的原理設計的。這些演算法通過對大量數據點的分析，自動識別出具有相似特徵的數據組，並將其歸為同一類別，同時將不相似的數據組分開。這種方法在客戶細分、圖像識別、推薦系統等領域有著廣泛的應用價值。此外，在社會學研究中，「類聚群分」也常用於分析人群的行為模式，例如通過調查問卷將受訪者劃分為不同的群體，以便更深入地理解社會結構和文化差異。

值得注意的是，「類聚群分」並非僅僅是一種技術手段，它還蘊含著深刻的哲學意義。這一概念反映了人類對秩序和規律的追求，體現了我們試圖從紛繁復雜的現實中尋找簡單規律的努力。然而，在實際應用中，我們也需要警惕過度簡化或刻板化分類可能帶來的問題。例如，在社會實踐中，如果僅以單一標准對人群進行「類聚群分」，可能會導致歧視或偏見的產生。因此，在運用這一思想時，我們需要結合具體的背景和條件，靈活調整分類的標准和方式。

綜上所述，「類聚群分」既是一種古老的智慧，也是一種現代的工具。它幫助我們認識世界、組織信息，並在各個領域發揮著重要作用。無論是自然科學還是社會科學，這一概念都為我們提供了一個強大的框架，使我們能夠更有效地應對復雜的問題和挑戰。

C. 人工魚群演算法有哪些

具體演算法如下：

1、起源人工魚群演算法是李曉磊等人於2002年在動物群體智能行為研究的基礎上提出的一種新型方盛優化演算法，該演算法根據水域中魚生存數目最多的地方就是本水域中富含營養物質最多的地方這一特點來模擬魚群的覓食行為而實現尋優。

2、演算法主要利用魚的三大基本行為：覓食、聚群和追尾行為，採用自上而下的尋優模式從構造個體的底層行為開始，通過魚群中各個體的局部尋優，達到全局最優值在群體中凸顯出來的目的。

3該方法採用自下而上的尋優思路，首先設計單個個體的感知、行為機制，然後將一個或一群實體放置在環境中，讓他們在環境的交互作用中解決問題。

4、生態學基礎在一片水域中，魚存在的數目最多的地方就是本水域富含營養物質最多的地方，依據這一特點來模仿魚群的覓食、聚群、追尾等行為，從而實現全局最優，這就是魚群演算法的基本思想。魚類活動中，覓食行為、群聚行為、追尾行為和隨機行為與尋優命題的解決有較為密切的關系，如何利用簡單有效的方式來構造和實現這些行為將是演算法實現的主要為題。

5、人工魚的結構模型人工魚是真實魚抽象化、虛擬化的一個實體，其中封裝了自身數據和一系列行為，可以接受環境的刺激信息，做出相應的活動。其所在的環境由問題的解空間和其他人工魚的狀態，它在下一時刻的行為取決於自身的狀態和環境的狀態，並且它還通過自身的活動來影響環境，進而影響其他人工魚的活動。