串行聚类算法
时间：2019-07-10 09:57:01
手机看文章
扫描二维码
随时随地手机看文章
[导读]这一类算法比较简单。我们考虑一下规则。* 在算法中所有特征向量只呈现一次；* 实际聚类成几类我们事先不知道；（在算法执行过程中，新的类被创建）我们给出如下记号，d(x,C) 表示 特征向量x与C类之间
这一类算法比较简单。我们考虑一下规则。
* 在算法中所有特征向量只呈现一次；
* 实际聚类成几类我们事先不知道；（在算法执行过程中，新的类被创建）
我们给出如下记号，d(x,C) 表示 特征向量x与C类之间的不相似度（dissimilarity）,我们不考虑它的具体定义，大家可以根据自己的实际情况人为选择。
需要人为定义两个参数：一个阈值，一个是最大类别数。
基本思想是：被考虑的每一个向量，根据它与现存的类之间的不相似度，它要么被分到某个已经创建的类，要么被放到重新创建的一个新类。
设m是目前为止，已经创建的类的个数。看如下算法：
threshold 和maxclass表示的两个预先给定的参数。
m = 1;
C_m = {x_1};
for i = 2 to N
find C_k : d(x_i, C_k) = min(1<=j threshold) AND (m<maxclass) then
m = m+1;
C_m = {x_i};
else
C_k = C_k U {x_i};
end if
end for大家根据自己的需要来设计自己的d(x_i, C_j)的定义。
这种方法叫做 BSAS （Basic Sequential Algorithm Scheme）
评价：Sergios 的评价，我稍作理解
* 如果使用similarity表示近邻测度，只需要改下 阈值，以及min改成max就行了。
* 如果我们用类代表的方式给出近邻测度的话，BSAS方法比较适合Compact类型的类，如果有证据表明，某些类不是compact类型的，这个方法就不好了。
* 时间复杂度为O（N），与特征向量的个数一致
这个方法有一些变种的应用，详细参开《Pattern Recognition》
下载文档
