1. 順序聚類
事實(shí)上，將n個(gè)對(duì)象，聚類到k個(gè)聚類中這件事本身是一個(gè)NP難問(wèn)題。熟悉組合數(shù)學(xué)應(yīng)該知道這個(gè)問(wèn)題的解事第二類Stirling數(shù)：
。這樣問(wèn)題也就出現(xiàn)了，如果k值固定，那么計(jì)算還是可行的，如果k值不固定，就要對(duì)所有的可能k都進(jìn)行計(jì)算，那運(yùn)行時(shí)間可想而知了。然而并不是所有的可行聚類方案都是合理的，所謂的合理，我理解就是說(shuō)接近你的聚類目標(biāo)的，之所以我們要分類，必然有初始動(dòng)機(jī)，那么可以根據(jù)這個(gè)動(dòng)機(jī)制定可行的聚類方案，這樣，復(fù)雜度的問(wèn)題就回避了。
順序算法（sequential algorithms）是一種非常簡(jiǎn)單的聚類算法，大多數(shù)都至少將所有特征向量使用一次或幾次，最后的結(jié)果依賴于向量參與算法的順序。這種聚類算法一般是不預(yù)先知道聚類數(shù)量k的，但有可能給出一個(gè)聚類數(shù)上界q。本文將主要介紹基本順序算法（Basic Sequential Algorithmic Scheme,BSAS）和其幾個(gè)變種，并給出代碼實(shí)現(xiàn)。
首先看BSAS，這個(gè)算法方案需要用戶定義參數(shù)：不相似性閾值θ和允許的最大聚類數(shù)q。算法的基本思想：由于要考慮每個(gè)新向量，根據(jù)向量到已有聚類的距離，將它分配到一個(gè)已有的聚類中，或者一個(gè)新生成的聚類中。算法的偽碼描述如下：
1. m=1 /*{聚類數(shù)量}*/
2. Cm={x1}
3. For i=2 to N
4. 找Ck: d(xi,Ck)=min1£j£md(xi,Cj)
5. If (d(xi,Ck)>Θ) AND (m<q) then
6. m=m+1
7. Cm={xi}
8. Else
9. Ck=CkÈ{xi}
10. 如果需要，更新向量表達(dá)
11. End {if}
12. End {for}
由上面的描述可以看出BSAS算法對(duì)向量順序非常依賴，無(wú)論是聚類數(shù)量還是聚類本身，不同的向量順序會(huì)導(dǎo)致完全不同的聚類結(jié)果。另一個(gè)影響聚類算法結(jié)果的重要因素是閾值θ的選擇，這個(gè)值直接影響最終聚類的數(shù)量，如果θ太小，就會(huì)生成很多不必要的聚類，因?yàn)楹芏嗲闆r下向量與聚類的合并條件都受到θ的限制，而如果θ太大，則聚類數(shù)量又會(huì)不夠。BSAS比較適合致密聚類，其對(duì)數(shù)據(jù)集進(jìn)行一次掃描，每次迭代中計(jì)算當(dāng)前向量與聚類間的距離，因?yàn)樽詈蟮木垲悢?shù)m被認(rèn)為遠(yuǎn)小于N，故BSAS的時(shí)間復(fù)雜度為O(N)。
由于BSAS算法依賴于q，因此這里介紹一種自動(dòng)估計(jì)聚類數(shù)q的簡(jiǎn)單方法，該方法也適用于其他的聚類算法，令BSAS(Θ)為具有給定不相似閾值θ的BSAS算法。
1. For Θ=a to b step c
2. 算法BSAS(Θ)執(zhí)行s次，每一次都使用不同的順序表示數(shù)據(jù)。
3. 估計(jì)聚類數(shù)，mΘ作為從s次BSAS(Θ)算法得來(lái)的最常出現(xiàn)的聚類數(shù)。
4. Next Θ
其中a和b是數(shù)據(jù)集的所有向量對(duì)的最小和最大不相似級(jí)別，c的選擇直接受d(x,C)的影響。
2. 算法實(shí)現(xiàn)
package util.clustering;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
/** *//**
* @author Jia Yu
*
*/
public class BSAS <T extends Clusterable<T>> 
{
/** *//**
* Basic Sequential Algorithmic Scheme
* 適用于致密聚類
*/
public BSAS() {
}
/** *//**
* Basic Sequential Algorithmic Scheme
* 考慮樣本空間中每個(gè)向量，根據(jù)向量到已有的聚類中心的距離，將它分配到一個(gè)已有聚類中，或者一個(gè)新生成的聚類中。
* time complexity is O(N)
* BSAS算法對(duì)整個(gè)數(shù)據(jù)集只進(jìn)行一次掃描。
* @param points 待聚類的向量
* @param Phi 用戶定義的不相似性閾值
* @param q 用戶定義的允許的最大聚類數(shù)
* @return
*/
public List<Cluster<T>> cluster(final Collection<T> points,final double Phi,final int q){
int m = 0;
int n = points.size();
double disOfXandCj = 0;
double disOfXandCk;
List<T> ptList = new ArrayList<T>(points);
Cluster<T> C = new Cluster<T>(ptList.get(m));
C.addPoint(ptList.get(m));
Cluster<T> Ck = C;
List<Cluster<T> > cList = new ArrayList<Cluster<T> >();
cList.add(C);
for(int i=1;i<n;i++){
disOfXandCk = Double.MAX_VALUE;
Iterator<Cluster<T> > cListIt = cList.iterator();
while(cListIt.hasNext()){
Cluster<T> Cj = cListIt.next();
disOfXandCj = getDisOfPointAndCluster(ptList.get(i),Cj);
if(disOfXandCk > disOfXandCj){
disOfXandCk = disOfXandCj;
Ck = Cj;
}
}
if(disOfXandCk > Phi && m < q){ //不滿足條件，則產(chǎn)生新的聚類
m++;
Cluster<T> cm = new Cluster<T>(ptList.get(i));
cm.addPoint(ptList.get(i));
cList.add(cm);
}
else{ //滿足條件的將點(diǎn)加入已有聚類，并更新聚類中心
if(cList.contains(Ck))
cList.remove(Ck);
Ck.addPoint(ptList.get(i));
final T newCenter = Ck.getCenter().centroidOf(Ck.getPoints());
Cluster<T> tempCluster = new Cluster<T>(newCenter);
for(int j=0;j<Ck.getPoints().size();j++){
tempCluster.addPoint(Ck.getPoints().get(j));
}
cList.add(tempCluster);
}
}
return cList;
}
/** *//**
* 選擇不同的測(cè)度，有不同的算法。
* 這里默認(rèn)dis(x,C)為點(diǎn)到聚類中心的距離。
*/
private double getDisOfPointAndCluster(T t, Cluster<T> cj) {
return t.distanceFrom(cj.getCenter());
}
}
3. 程序框架
我的聚類程序主要擴(kuò)展自Apache Commons Math開(kāi)源框架，下面是其結(jié)構(gòu)，我簡(jiǎn)單加入了Clusterer類作為抽象模板類，使用模板方法模式修改了框架，為后續(xù)加入的例如BSAS算法提供模板。
4. 小結(jié)
順序算法簡(jiǎn)單易實(shí)現(xiàn)，對(duì)于學(xué)習(xí)聚類來(lái)說(shuō)是入門的最好選擇，考慮到篇幅的限制，不能將代碼全部發(fā)上來(lái)，如果有需要可以向我索要，Apache Commons Math框架可以到Apache的網(wǎng)站上下載。另外還有很多介紹不夠詳細(xì)，感興趣的朋友可以繼續(xù)深入研究BSAS的擴(kuò)展。
5. 參考文獻(xiàn)及推薦閱讀
[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas
[2]模式識(shí)別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛(ài)俠, 張廣源等譯