1. 順序聚類
事實上，將n個對象，聚類到k個聚類中這件事本身是一個NP難問題。熟悉組合數(shù)學(xué)應(yīng)該知道這個問題的解事第二類Stirling數(shù)：
。這樣問題也就出現(xiàn)了，如果k值固定，那么計算還是可行的，如果k值不固定，就要對所有的可能k都進(jìn)行計算，那運行時間可想而知了。然而并不是所有的可行聚類方案都是合理的，所謂的合理，我理解就是說接近你的聚類目標(biāo)的，之所以我們要分類，必然有初始動機(jī)，那么可以根據(jù)這個動機(jī)制定可行的聚類方案，這樣，復(fù)雜度的問題就回避了。
順序算法（sequential algorithms）是一種非常簡單的聚類算法，大多數(shù)都至少將所有特征向量使用一次或幾次，最后的結(jié)果依賴于向量參與算法的順序。這種聚類算法一般是不預(yù)先知道聚類數(shù)量k的，但有可能給出一個聚類數(shù)上界q。本文將主要介紹基本順序算法（Basic Sequential Algorithmic Scheme,BSAS）和其幾個變種，并給出代碼實現(xiàn)。
首先看BSAS，這個算法方案需要用戶定義參數(shù)：不相似性閾值θ和允許的最大聚類數(shù)q。算法的基本思想：由于要考慮每個新向量，根據(jù)向量到已有聚類的距離，將它分配到一個已有的聚類中，或者一個新生成的聚類中。算法的偽碼描述如下：
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算法對向量順序非常依賴，無論是聚類數(shù)量還是聚類本身，不同的向量順序會導(dǎo)致完全不同的聚類結(jié)果。另一個影響聚類算法結(jié)果的重要因素是閾值θ的選擇，這個值直接影響最終聚類的數(shù)量，如果θ太小，就會生成很多不必要的聚類，因為很多情況下向量與聚類的合并條件都受到θ的限制，而如果θ太大，則聚類數(shù)量又會不夠。BSAS比較適合致密聚類，其對數(shù)據(jù)集進(jìn)行一次掃描，每次迭代中計算當(dāng)前向量與聚類間的距離，因為最后的聚類數(shù)m被認(rèn)為遠(yuǎn)小于N，故BSAS的時間復(fù)雜度為O(N)。
由于BSAS算法依賴于q，因此這里介紹一種自動估計聚類數(shù)q的簡單方法，該方法也適用于其他的聚類算法，令BSAS(Θ)為具有給定不相似閾值θ的BSAS算法。
1. For Θ=a to b step c
2. 算法BSAS(Θ)執(zhí)行s次，每一次都使用不同的順序表示數(shù)據(jù)。
3. 估計聚類數(shù)，mΘ作為從s次BSAS(Θ)算法得來的最常出現(xiàn)的聚類數(shù)。
4. Next Θ
其中a和b是數(shù)據(jù)集的所有向量對的最小和最大不相似級別，c的選擇直接受d(x,C)的影響。
2. 算法實現(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
* 考慮樣本空間中每個向量，根據(jù)向量到已有的聚類中心的距離，將它分配到一個已有聚類中，或者一個新生成的聚類中。
* time complexity is O(N)
* BSAS算法對整個數(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{ //滿足條件的將點加入已有聚類，并更新聚類中心
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;
}
/** *//**
* 選擇不同的測度，有不同的算法。
* 這里默認(rèn)dis(x,C)為點到聚類中心的距離。
*/
private double getDisOfPointAndCluster(T t, Cluster<T> cj) {
return t.distanceFrom(cj.getCenter());
}
}
3. 程序框架
我的聚類程序主要擴(kuò)展自Apache Commons Math開源框架，下面是其結(jié)構(gòu)，我簡單加入了Clusterer類作為抽象模板類，使用模板方法模式修改了框架，為后續(xù)加入的例如BSAS算法提供模板。
4. 小結(jié)
順序算法簡單易實現(xiàn)，對于學(xué)習(xí)聚類來說是入門的最好選擇，考慮到篇幅的限制，不能將代碼全部發(fā)上來，如果有需要可以向我索要，Apache Commons Math框架可以到Apache的網(wǎng)站上下載。另外還有很多介紹不夠詳細(xì)，感興趣的朋友可以繼續(xù)深入研究BSAS的擴(kuò)展。
5. 參考文獻(xiàn)及推薦閱讀
[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas
[2]模式識別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛俠, 張廣源等譯