聚類算法的公式
發(fā)布時(shí)間：2025-08-26 | 來(lái)源：互聯(lián)網(wǎng)轉(zhuǎn)載和整理
聚類的定義
聚類就是對(duì)大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個(gè)類別，使類別內(nèi)的數(shù)據(jù)相似度較大而類別間的數(shù)據(jù)相似度較小。聚類算法是無(wú)監(jiān)督的算法。
常見(jiàn)的相似度計(jì)算方法
閔可夫斯基距離Minkowski/歐式距離
在上述的計(jì)算中，當(dāng)p=1時(shí)，則是計(jì)算絕對(duì)值距離，通常叫做曼哈頓距離，當(dāng)p=2時(shí)，表述的是歐式距離。
杰卡德相似系數(shù)(Jaccard)
杰卡德相關(guān)系數(shù)主要用于描述***之間的相似度，在目標(biāo)檢測(cè)中，iou的計(jì)算就和此公式相類似
余弦相似度
余弦相似度通過(guò)夾角的余弦來(lái)描述相似性
Pearson相似系數(shù)
相對(duì)熵(K-L距離)
相對(duì)熵的相似度是不對(duì)稱的相似度，D(p||q)不一定等于D(q||p)。
聚類的基本思想
給定一個(gè)有N個(gè)對(duì)象的數(shù)據(jù)集，劃分聚類的技術(shù)將構(gòu)造數(shù)據(jù)的K個(gè)劃分，每個(gè)劃分代表一個(gè)簇，K<=n。也就是說(shuō)聚類將數(shù)據(jù)劃分為k個(gè)簇，而且這k個(gè)劃分滿足下列條件：
每個(gè)簇至少包含一個(gè)對(duì)象，每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇。
具體的步驟為，對(duì)于給定的k，算法首先給出一個(gè)初始的劃分方法。以后通過(guò)反復(fù)迭代的方法改變劃分，使得每一次改進(jìn)之后的劃分方案都較前一次更好。
密度聚類
密度聚類方法的指導(dǎo)思想是，只要一個(gè)區(qū)域中的點(diǎn)的密度大于某個(gè)閾值，就把它加到與之相近的聚類中去。這類算法能夠克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)，可以發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感。但計(jì)算密度單元的計(jì)算復(fù)雜度大，需要建立空間索引來(lái)降低計(jì)算量。
DBSCAN算法
DBSCAN是一個(gè)比較有代表性的基于密度聚類的聚類算法，它對(duì)簇的定義為密度相連的點(diǎn)的最大***，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有噪聲的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的聚類。
DBSCAN相關(guān)定義
對(duì)象的ε-鄰域：給定對(duì)象在半徑ε內(nèi)的區(qū)域。
核心對(duì)象：對(duì)于給定的數(shù)據(jù)m，如果一個(gè)對(duì)象的ε-鄰域至少包含有m個(gè)對(duì)象，則成為該對(duì)象的核心對(duì)象。
直接密度可達(dá)：給定一個(gè)對(duì)象***D，如果p是在q的ε-鄰域內(nèi)，而q是一個(gè)核心對(duì)象，則對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。
密度可達(dá)：如果存在一個(gè)對(duì)象鏈p1p2···pn，p1=q，pn=p，對(duì)pi屬于D，pi+1是從pi關(guān)于ε和m直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于ε和m密度可達(dá)的。
密度相連：如果對(duì)象***D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于ε和m密度可達(dá)的，那么對(duì)象p和q是關(guān)于ε和m密度相連的。
簇：一個(gè)基于密度的簇是最大的密度相連對(duì)象的***。
噪聲：不包含在任何簇中的對(duì)象稱為噪聲。
DBSCAN通過(guò)檢查數(shù)據(jù)集中的每個(gè)對(duì)象的ε-鄰域來(lái)尋找聚類，如果一個(gè)點(diǎn)p的ε-鄰域包含對(duì)于m個(gè)對(duì)象，則創(chuàng)建一個(gè)p作為核心對(duì)象的新簇。然后DBSCAN反復(fù)地尋找這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及密度可達(dá)簇的合并。當(dāng)沒(méi)有新的點(diǎn)可以被添加到任何簇時(shí)，該過(guò)程結(jié)束。算法的中ε和m是根據(jù)先驗(yàn)知識(shí)來(lái)給出的。