ROCK 聚类算法
ROCK (RObust Clustering using linKs)聚类算法是一种鲁棒的用于分类属性的聚类算法。该算法属于凝聚型的层次聚类算法。之所以鲁棒是因为在确认两对象（样本点/簇）之间的关系时考虑了他们共同的邻居（相似样本点）的数量，在算法中被叫做链接（Link）的概念。而一些聚类算法只关注对象之间的相似度。
ROCK算法中用到的四个关键概念
- 邻居（Neighbors）：如果两个样本点的相似度达到了阈值（θ），这两个样本点就是邻居。阈值（θ）有用户指定，相似度也是通过用户指定的相似度函数计算。常用的分类属性的相似度计算方法有： Jaccard 系数 ，余弦相似度。
- 链接（Links）：两个对象的共同邻居数量
- 目标函数（Criterion Function）：最大化下面目标函数以获得最优的聚类结果（最终簇之间的链接总数最小，而簇内的链接总数最大）。C i ：第i个簇，k:簇的个数，n i :C i 的大小（样本点的数量）。一般可使用f (θ) = (1-θ)/(1+θ). f(θ)一般具有以下性质：C i 中的每个样本点在C i 中有n i f(θ) 个邻居。（具体请见参考文献2）
4. 相似性的度量（Goodness Measure）：使用该公式计算所有对象的两两相似度，将相似性最高的两个对象合并。通过该相似性度量不断的凝聚对象至k个簇，最终计算上面目标函数值必然是最大的。
，link[C i ,C j ]= 
大概算法思路（伪代码请见参考文献2）：
输入：需要聚类的个数-k，和相似度阈值-θ
算法：
开始每个点都是单独的聚类，根据计算点与点间的相似度，生成相似度矩阵。
根据相似度矩阵和相似度阈值-θ，计算邻居矩阵-A。如果两点相似度>=θ,取值1（邻居），否则取值0.
计算链接矩阵-L=A x A
计算相似性的度量（Goodness Measure），将相似性最高的两个对象合并。回到第2步进行迭代直到形成k个聚类或聚类的数量不在发生变换。
输出：
簇和异常值（不一定存在）
ROCK in R - cba 包:
load('country.RData') d<-dist(countries[,-1]) x<-as.matrix(d) library(cba) rc <- rockCluster(x, n=4, theta=0.2, debug=TRUE) rc$cl 参考文献：
【1】http://www.enggjournals.com/ijcse/doc/IJCSE12-04-05-248.pdf
【2】http://www.cis.upenn.edu/~sudipto/mypapers/categorical.pdf
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
