什麼是變色龍演算法？

變色龍是一種層次聚類演算法，它使用動態建模來決定簇對之間的相似性。它是基於對ROCK和CURE等兩種層次聚類演算法觀察到的缺點而改進的。

ROCK及其相關設計強調簇的互連性，而忽略了關於簇接近性的資料。CURE及其相關設計考慮簇的接近性，但忽略了簇的互連性。在變色龍演算法中，簇的相似性是根據簇內物件的連線程度和簇的接近程度來評估的。特別是，如果兩個簇的互連性高且彼此靠近，則將它們合併。

它不基於靜態的、使用者提供的模型，可以自動適應被合併簇的內部特徵。合併過程支援發現自然且均勻的簇，並且考慮到可以定義相似性函式，它適用於所有型別的資料。

變色龍演算法需要k近鄰圖技術來構建稀疏圖，其中圖的每個頂點定義一個數據物件，如果一個物件屬於另一個物件的k個最相似物件之一，則這兩個頂點（物件）之間存在一條邊。邊的權重反映物件之間的相似性。

變色龍演算法使用圖劃分演算法將k近鄰圖劃分為大量相對較小的子簇。它可以使用凝聚層次聚類演算法，該演算法基於子簇的相似性重複合併子簇。它可以確定最相似子簇對，同時考慮簇的互連性和接近性。

k近鄰圖動態地捕捉鄰域的概念：物件的鄰域半徑由物件所駐留區域的密度決定。在密集區域，鄰域表示較窄；在稀疏區域，鄰域表示較寬。

這種影響導致比基於密度的演算法（如DBSCAN，它使用全域性鄰域）更自然的簇。此外，區域的密度被記錄為邊的權重。特別是，密集區域的邊的權重往往高於稀疏區域的邊的權重。

圖劃分演算法劃分k近鄰圖，以使邊割最小化。也就是說，將簇C細分為子簇C_i和C_j以最小化如果將C一分為二為C_i和C_j，則可能被切割的邊的權重。邊割表示為EC(C_i, C_j)，並確定簇C_i和C_j之間的絕對互連性。

Ginni

更新於：2021年11月24日

4K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習