資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究k-medoids演算法在大資料集上的效率如何？
像PAM這樣的經典k-medoids劃分演算法在小型資料集上效率很高，但在大資料集上卻難以擴充套件。對於較大的資料集，可以使用一種基於取樣的方法，稱為CLARA（Clustering Large Applications）。
CLARA背後的方法如下：如果樣本以相當隨機的方式選擇，它必須緊密地定義原始資料集。選擇的代表性物件（medoids）將類似於從整個資料集選擇的那些物件。CLARA從資料集中抽取多個樣本，對每個樣本應用PAM，並將其最佳聚類作為輸出返回。
CLARA的效能基於樣本大小。觀察到PAM在一個給定資料集之間搜尋最佳k個medoids，而CLARA搜尋所選資料集樣本之間的最佳k個medoids。提出了一種稱為CLARANS（Clustering Large Applications depends upon RANdomized Search）的k-medoids型別演算法。它可以將取樣方法與PAM連線起來。雖然CLARA在搜尋的每個階段都有一個固定的樣本，但CLARANS在搜尋的每個階段都會以一定的隨機性抽取樣本。
聚類過程可以看作是對圖的搜尋，其中每個節點都是一個可能的解（一組k個medoids）。如果它們的集合只相差一個物件，則兩個節點是相鄰的（特別是，由圖中的弧連線）。每個節點都可以分配一個成本，該成本由每個物件與其簇的medoid之間的總差異表示。
在每一步中，PAM確定其在搜尋最小成本解時最新節點的所有鄰居。然後，最新節點將被具有最大成本下降的鄰居替換。因為CLARA操作的是整個資料集的樣本，所以它確定的鄰居較少，並將搜尋限制在比初始圖更小的子圖。
實驗表明，CLARANS比PAM和CLARA都更有效率。它可以使用輪廓係數（定義物件真正應用於聚類的程度的物件屬性）來發現最“自然”的聚類數量。CLARANS還允許發現異常值。
CLARANS的計算複雜度為O(n2)，其中n是物件的個數。此外，其聚類質量基於所使用的取樣方法。透過關注探索空間資料結構（包括R*-樹）的方法，可以進一步提高CLARANS處理駐留在磁碟上的資料物件的能力。
447 次瀏覽
