談談對論文A Hybrid Approach to Clustering in Big Data的了解
在這篇論文中作者提出了一種新的聚類方法,叫clusiVAT算法,并且與 k-means, single pass k-means, online k-means,和clustering using representatives (CURE) 等算法進行了對比。
對聚類的了解
聚類(clustrering)是一種無監督學習方法,主要分成原型聚類(k均值算法,LVQ算法(學習向量量化算法)、高斯混合聚類)密度聚類(DBSCAN算法)、層次聚類(single-linkage算法)。
了解這篇論文需要一些前提知識:
論文中提到的常見聚類算法
常見的由層次聚類算法(hierarchical clustering),基于簇中心的(centroid-based clustering)聚類算法等。作者用以下四種算法作為參考,來展現clusiVAT算法的優秀之處。
(1):k-means算法
(2):online k-means算法
(3)pass k-means算法
(4)clustering using representatives(CURE)
一些基礎知識:
(1) single-linkage clustering,一種層次聚類方法,基于bottom up的聚類方式,聚類時每次将元素最接近的兩個cluster歸為一類。
論文的主要成就
(1)與上述四種算法在大資料集下比較了clusiVAT算法的性能
(2)在24個 2-D資料集上展示了clusiVAT算法的CPU time和partition accuracy(PA).
(3)為了展現clusiVAT算法對無标簽樣本的内部聚類性能,作者用Surry大學的indoor office environment energy usage data來做了測試,發現clusiVAT算法有最大的Dunn指數(在clusiVAT算法和其他4種算法之中)。
(4)做Friedman test
clusiVAT算法
clusiVAT算法基于reordered dissimilarity images(RDIs),也叫作cluster heat maps,那到底是什麼意思呢?在圖像中,VAT實際上是對由像素組成的非相似矩陣D進行重排序(按照modified MST方法)形成矩陣D*,形成不同的簇,這些簇在圖像上看來就像一塊斑(dark blocks).
首先來看VAT算法:
按照論文的意思,D*是由D通過modified MST生成的,如圖:
辨別黃線的部分就是MST的核心了,把最小權值的邊保留下來,由于對生成最小生成樹的Prim算法了解不深,黃線部分僞代碼還是不了解。。。
iVAT算法改進了VAT算法,有更小的時間複雜度O(n^2)
siVAT算法在iVAT和VAT算法的基礎上改進得可以處理很大的資料集。