聚类算法的java实现_聚类算法之BIRCH（Java实现）
BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)天生就是為處理超大規模(至少要讓你的內存容不下)的數據集而設計的，它可以在任何給定的內存下運行。關于BIRCH的更多特點先不介紹，我先講一下算法的完整實現細節，對算法的實現過程搞清楚后再去看別人對該算法的評價才會感受深刻。
你不需要具備B樹的相關知識，我接下來會講得很清楚。
BIRCH算法的過程就是要把待分類的數據插入一棵樹中，并且原始數據都在葉子節點上。這棵樹看起來是這個樣子：
在這棵樹中有3種類型的節點：Nonleaf、Leaf、MinCluster，Root可能是一種Nonleaf，也可能是一種Leaf。所有的Leaf放入一個雙向鏈表中。每一個節點都包含一個CF值，CF是一個三元組$(N,\vec{LS},\vec{SS})$，其中data point instance的個數，$\vec{LS}$和$\vec{SS}$是與數據點同維度的向量，$\vec{LS}$是線性和，$\vec{SS}$是平方和。比如有一個MinCluster里包含3個數據點(1,2,3)，(4,5,6)，(7,8,9)，則
N=3,
$\vec{LS}=(1+4+7,2+5+8,3+6+9)=(12,15,18)$，
$\vec{SS}=(1+16+49,4+25+64,9+36+81)$。
就拿這個MinCluster為例，我們可以計算它的
簇中心$$\vec{X_0}=\frac{\sum_{i=1}^{N}\vec{X_i}}{N}$$
簇半徑$$R=\sqrt{\frac{\sum_{i=1}^{N}{(\vec{X_i}-\vec{X_0})}^2}{N}}$$
簇直徑$$D=\sqrt{\frac{\sum_{i=1}^{N}\sum_{j=1}^{N}{(\vec{X_i}-\vec{X_j})}^2}{N(N-1)}}$$
我們還可以計算兩個簇之間的距離$$D_2=\sqrt{\frac{\sum_{i=1}^{N_1}\sum_{j=N_1+1}^{N_1+N_2}{(\vec{X_i}-\vec{X_j})}^2}{N_1N_2}}$$
當然你也可以使用D0，D1，D3等等，不過在這里我們使用D2。
有意思的是簇中心、簇半徑、簇直徑以及兩簇之間的距離D0到D3都可以由CF來計算，比如
簇直徑$$D=\sqrt{\frac{SS_1}{N_1}+\frac{SS_2}{N_2}-\frac{2LS_1LS_2}{N_1N_2}}$$
簇間距離$D_2=\sqrt{\frac{2N*SS-2LS^2}{N(N-1)}}$,這里的N，LS和SS是指兩簇合并后大簇的N，LS和SS。所謂兩簇合并只需要兩個對應的CF相加那可
CF1 + CF2 = (N1 + N2 , LS1 + LS2, SS1 + SS2)
每個節點的CF值就是其所有孩子節點CF值之和，以每個節點為根節點的子樹都可以看成 是一個簇。
Nonleaf、Leaf、MinCluster都是有大小限制的，Nonleaf的孩子節點不能超過B個，Leaf最多只能有L個MinCluster，而一個MinCluster的直徑不能超過T。
算法起初，我們掃描數據庫，拿到第一個data point instance--(1,2,3),我們創建一個空的Leaf和MinCluster，把點(1,2,3)的id值放入Mincluster，更新MinCluster的CF值為(1,(1,2,3)，(1,4,9))，把MinCluster作為Leaf的一個孩子，更新Leaf的CF值為(1,(1,2,3)，(1,4,9))。實際上只要往樹中放入一個CF(這里我們用CF作為Nonleaf、Leaf、MinCluster的統稱)，就要更新從Root到該葉子節點的路徑上所有節點的CF值。
當又有一個數據點要插入樹中時，把這個點封裝為一個MinCluster(這樣它就有了一個CF值)，把新到的數據點記為CF_new，我們拿到樹的根節點的各個孩子節點的CF值，根據D2來找到CF_new與哪個節點最近，就把CF_new加入那個子樹上面去。這是一個遞歸的過程。遞歸的終止點是要把CF_new加入到一個MinCluster中，如果加入之后MinCluster的直徑沒有超過T，則直接加入，否則譔CF_new要單獨作為一個簇，成為MinCluster的兄弟結點。插入之后注意更新該節點及其所有祖先節點的CF值。
插入新節點后，可能有些節點的孩子數大于了B(或L)，此時該節點要分裂。對于Leaf，它現在有L+1個MinCluster，我們要新創建一個Leaf，使它作為原Leaf的兄弟結點，同時注意每新創建一個Leaf都要把它插入到雙向鏈表中。L+1個MinCluster要分到這兩個Leaf中，怎么分呢？找出這L+1個MinCluster中距離最遠的兩個Cluster(根據D2)，剩下的Cluster看離哪個近就跟誰站在一起。分好后更新兩個Leaf的CF值，其祖先節點的CF值沒有變化，不需要更新。這可能導致祖先節點的遞歸分裂，因為Leaf分裂后恰好其父節點的孩子數超過了B。Nonleaf的分裂方法與Leaf的相似，只不過產生新的Nonleaf后不需要把它放入一個雙向鏈表中。如果是樹的根節點要分裂，則樹的高度加1。
CF.java
package birch;
public class CF {
private int N;
private double[] LS;
private double[] SS;
public CF() {
LS=new double[BIRCH.dimen];
SS=new double[BIRCH.dimen];
}
// 根據一個data point instance創建一個Clustering Feature
public CF(double[] data) {
int len = data.length;
this.N = 1;
this.LS = data;
this.SS=new double[len];
for (int i = 0; i < len; i++)
this.SS[i] = Math.pow(data[i], 2);
}
//復制構造函數(深復制)
public CF(CF cf){
this.N=cf.getN();
int len=cf.getLS().length;
this.LS=new double[len];
this.SS=new double[len];
for(int i=0;i
this.LS[i]=cf.getLS()[i];
this.SS[i]=cf.getSS()[i];
}
}
// 采用D2計算兩個CF Entry之間的距離
public double getDistanceTo(CF entry) {
double dis = 0.0;
int len = this.LS.length;
// 采用D2
for (int i = 0; i < len; i++) {
dis += this.SS[i] / this.N + entry.getSS()[i] / entry.getN() - 2
* this.LS[i] * entry.getLS()[i] / (this.N * entry.getN());
}
return Math.sqrt(dis);
}
//采用D0計算兩個簇心之間的歐氏距離
//public double getDistanceTo(CF entry) {
//int len=entry.getLS().length;
//double[] a=new double[len];
//double[] b=new double[len];
//for(int i=0;i
//a[i]=this.getLS()[i]/this.N;
//b[i]=this.getSS()[i]/this.N;
//}
//return calEuraDist(a,b,len);
//}
// 加上或減去一個CF的值
public void addCF(CF entry, boolean add) {
int opt = 1; // 默認為相加
if (!add) // 如果add為false則為相減
opt = -1;
this.N = this.N + entry.getN() * opt;
int len = this.LS.length;
for (int i = 0; i < len; i++) {
this.LS[i] = this.LS[i] + entry.getLS()[i] * opt;
this.SS[i] = this.SS[i] + entry.getSS()[i] * opt;
}
}
//計算兩個向量的歐氏距離
public static double calEuraDist(double[] arr1,double[] arr2,int len){
double result=0.0;
for(int i=0;i
result+=Math.pow(arr1[i]-arr2[i],2.0);
}
return Math.sqrt(result);
}
public int getN() {
return N;
}
public void setN(int n) {
N = n;
}
public double[] getLS() {
return LS;
}
public void setLS(double[] lS) {
LS = lS;
}
public double[] getSS() {
return SS;
}
public void setSS(double[] sS) {
SS = sS;
}
}
MinCluster.java
package birch;
import java.util.ArrayList;
//最小簇
public class MinCluster {
private CF cf;
private ArrayList inst_marks;
public MinCluster(){
cf=new CF();
inst_marks=new ArrayList();
}
public CF getCf() {
return cf;
}
public void setCf(CF cf) {
this.cf = cf;
}
public ArrayList getInst_marks() {
return inst_marks;
}
public void setInst_marks(ArrayList inst_marks) {
this.inst_marks = inst_marks;
}
//計算簇的直徑
public static double getDiameter(CF cf){
double diameter=0.0;
int n=cf.getN();
for(int i=0;i
double ls=cf.getLS()[i];
double ss=cf.getSS()[i];
diameter=diameter+(2*n*ss-2*ls*ls);
}
diameter=diameter/(n*n-n);
return Math.sqrt(diameter);
}
//計算和另外一個簇合并后的直徑
public static double getDiameter(MinCluster cluster1,MinCluster cluster2){
CF cf=new CF(cluster1.getCf());
cf.addCF(cluster2.getCf(), true);
return getDiameter(cf);
}
public void mergeCluster(MinCluster cluster){
this.getCf().addCF(cluster.getCf(), true);
for(int i=0;i
this.getInst_marks().add(cluster.getInst_marks().get(i));
}
}
}
TreeNode.java
package birch;
public abstract class TreeNode extends CF {
private TreeNode parent;
public TreeNode() {
}
public TreeNode(double[] data) {
super(data);
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public void addCFUpToRoot(CF cf){
TreeNode node=this;
while(node!=null){
node.addCF(cf, true);
node=node.getParent();
}
}
abstract void split();
abstract void absorbSubCluster(MinCluster cluster);
}
NonleafNode.java
package birch;
import java.util.ArrayList;
public class NonleafNode extends TreeNode {
private int B=5;
private ArrayList children;
public NonleafNode() {
children=new ArrayList();
}
public NonleafNode(double[] data) {
super(data);
}
// 節點分裂
public void split() {
// 找到距離最遠的兩個孩子節點
int c1 = 0;
int c2 = 0;
double maxDist = 0;
int len = this.getChildren().size();
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
double dist = this.getChildren().get(i)
.getDistanceTo(this.getChildren().get(j));
if (dist > maxDist) {
maxDist = dist;
c1 = i;
c2 = j;
}
}
}
// 以距離最遠的孩子節點為中心，把B+1個孩子分為兩個大簇。其中一個簇仍留作本節點的孩子，另外一簇需要新創建一個節點來領養它們
NonleafNode newNode = new NonleafNode();
newNode.addChild(this.getChildren().get(c2));
//如果本節點已經是Root節點，則需要創建一個新的Root節點
if(this.getParent()==null){
NonleafNode root= new NonleafNode();
root.setN(this.getN());
root.setLS(this.getLS());
root.setSS(this.getSS());
root.addChild(this);
this.setParent(root);
}
newNode.setParent(this.getParent());
((NonleafNode)this.getParent()).addChild(newNode);
for (int i = 0; i < len; i++) {
if (i != c1 && i != c2) {
if (this.getChildren().get(i)
.getDistanceTo(this.getChildren().get(c2)) < this
.getChildren().get(i)
.getDistanceTo(this.getChildren().get(c1))) {
newNode.addChild(this.getChildren().get(i));
}
}
}
for (TreeNode entry : newNode.getChildren()) {
newNode.addCF(entry, true);
this.deleteChild(entry);
this.addCF(entry, false);
}
//如果本節點分裂導致父節點的孩子數超過了分枝因子，引發父節點分裂
NonleafNode pn=(NonleafNode)this.getParent();
if(pn.getChildren().size()>B){
this.getParent().split();
}
}
public void absorbSubCluster(MinCluster cluster){
//從本節點的孩子中尋找與cluster最近的子節點
CF cf=cluster.getCf();
int nearIndex=0;
double minDist=Double.MAX_VALUE;
for(int i=0;i
double dist=cf.getDistanceTo(this.getChildren().get(i));
if(dist
nearIndex=i;
}
}
//讓那個最近的子節點absorb掉這個新到的cluster
this.getChildren().get(nearIndex).absorbSubCluster(cluster);
}
public ArrayList getChildren() {
return children;
}
public void setChildren(ArrayList children) {
this.children = children;
}
public void addChild(TreeNode child) {
this.children.add(child);
}
public void deleteChild(TreeNode child) {
this.children.remove(children.indexOf(child));
}
public int getB() {
return B;
}
public void setB(int b) {
B = b;
}
}
LeafNode.java
package birch;
import java.util.ArrayList;
public class LeafNode extends TreeNode {
private int L=10;
private double T=2.8;
private ArrayList children;
private LeafNode pre;
private LeafNode next;
public LeafNode() {
children=new ArrayList();
}
public LeafNode(double[] data) {
super(data);
}
// 節點分裂
public void split() {
// 找到距離最遠的兩個孩子節點
int c1 = 0;
int c2 = 0;
double maxDist = 0;
int len = this.getChildren().size();
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
double dist = this.getChildren().get(i).getCf()
.getDistanceTo(this.getChildren().get(j).getCf());
if (dist > maxDist) {
maxDist = dist;
c1 = i;
c2 = j;
}
}
}
// 以距離最遠的孩子節點為中心，把B+1個孩子分為兩個大簇。其中一個簇仍留作本節點的孩子，另外一簇需要新創建一個節點來領養它們
LeafNode newNode = new LeafNode();
newNode.addChild(this.getChildren().get(c2));
// 如果本節點已經是Root節點，則需要創建一個新的Root節點
if (this.getParent() == null) {
NonleafNode root = new NonleafNode();
root.setN(this.getN());
root.setLS(this.getLS());
root.setSS(this.getSS());
this.setParent(root);
root.addChild(this);
}
//建立新節點和本節點的父節點的父子關系
newNode.setParent(this.getParent());
((NonleafNode)this.getParent()).addChild(newNode);
//把離newNode近的孩子節點歸到newNode這個簇里面
for (int i = 0; i < len; i++) {
if (i != c1 && i != c2) {
if (this.getChildren().get(i).getCf()
.getDistanceTo(this.getChildren().get(c2).getCf()) < this
.getChildren().get(i).getCf()
.getDistanceTo(this.getChildren().get(c1).getCf())) {
newNode.addChild(this.getChildren().get(i));
}
}
}
//把離newNode近的孩子節點從本節點中刪除
for (MinCluster cluster : newNode.getChildren()) {
newNode.addCF(cluster.getCf(), true);
this.deleteChild(cluster);
this.addCF(cluster.getCf(), false);
}
// 把新增加的LeafNode添加到LeafNode雙向鏈表中
if (this.getNext() != null) {
newNode.setNext(this.getNext());
this.getNext().setPre(newNode);
}
this.setNext(newNode);
newNode.setPre(this);
// 如果本節點分裂導致父節點的孩子數超過了分枝因子，引發父節點分裂
NonleafNode pn = (NonleafNode) this.getParent();
if (pn.getChildren().size() > pn.getB()) {
this.getParent().split();
}
}
@Override
public void absorbSubCluster(MinCluster cluster) {
// 先試圖找到葉子節點的孩子(一些subcluster)中與cluster最近的簇
CF cf = cluster.getCf();
int nearIndex = 0;
double minDist = Double.MAX_VALUE;
int len = this.getChildren().size();
if (len > 0) {
for (int i = 0; i < len; i++) {
double dist = cf.getDistanceTo(this.getChildren().get(i)
.getCf());
if (dist < minDist) {
nearIndex = i;
}
}
// 計算兩個簇合并后的直徑
double mergeDiameter = MinCluster.getDiameter(cluster, this
.getChildren().get(nearIndex));
// 如果合并后發現簇的直徑超過了閾值，則把cluster作為一個單獨的孩子插入本葉子節點下
if (mergeDiameter > T) {
this.addChild(cluster);
if (this.getChildren().size() > L) {
this.split();
}
}
// 如果不超過閾值，則直接合并兩個簇
else {
this.getChildren().get(nearIndex).mergeCluster(cluster);
}
}
// 創建B樹之初，葉子節點還沒有children
else {
this.addChild(cluster);
}
this.addCFUpToRoot(cluster.getCf());
}
public ArrayList getChildren() {
return children;
}
public void setChildren(ArrayList children) {
this.children = children;
}
public void addChild(MinCluster child) {
this.children.add(child);
}
public void deleteChild(MinCluster child) {
this.children.remove(children.indexOf(child));
}
public LeafNode getPre() {
return pre;
}
public void setPre(LeafNode pre) {
this.pre = pre;
}
public LeafNode getNext() {
return next;
}
public void setNext(LeafNode next) {
this.next = next;
}
public int getL() {
return L;
}
public void setL(int l) {
L = l;
}
public double getT() {
return T;
}
public void setT(double t) {
T = t;
}
}
BIRCH.java
package birch;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
public class BIRCH {
public static final int dimen=4;
LeafNode leafNodeHead=new LeafNode();
int point_num=0;//point instance計數
//逐條掃描數據庫，建立B-樹
public TreeNode buildBTree(String filename){
//先建立一個葉子節點
LeafNode leaf=new LeafNode();
TreeNode root=leaf;
//把葉子節點加入存儲葉子節點的雙向鏈表
leafNodeHead.setNext(leaf);
leaf.setPre(leafNodeHead);
//打開文件，從文件中讀取原始數據
File file = new File(filename);
if(!file.exists()){
System.out.println("Data File Not Exists.");
System.exit(2);
}
try {
FileReader fr = new FileReader(file);
BufferedReader br=new BufferedReader(fr);
String line=null;
while((line=br.readLine())!=null && line.trim()!=""){
point_num++;
String[] cont=line.split("[,|\\s+]");
//讀入point instance
double[] data=new double[dimen];
for(int i=0;i
data[i]=Double.parseDouble(cont[i]);
}
String mark=String.valueOf(point_num)+cont[data.length];
//根據一個point instance創建一個MinCluster
CF cf=new CF(data);
MinCluster subCluster=new MinCluster();
subCluster.setCf(cf);
subCluster.getInst_marks().add(mark);
//把新到的point instance插入樹中
root.absorbSubCluster(subCluster);
//要始終保證root是樹的根節點
while(root.getParent()!=null){
root=root.getParent();
}
}
br.close();
} catch (IOException e) {
e.printStackTrace();
}
return root;
}
//打印B-樹的所有葉子節點
public void printLeaf(LeafNode header){
//point_num清0
point_num=0;
while(header.getNext()!=null){
System.out.println("\n一個葉子節點:");
header=header.getNext();
for(MinCluster cluster:header.getChildren()){
System.out.println("\n一個最小簇:");
for(String mark:cluster.getInst_marks()){
point_num++;
System.out.print(mark+"\t");
}
}
}
}
//打印指定根節點的子樹
public void printTree(TreeNode root){
if(!root.getClass().getName().equals("birch.LeafNode")){
NonleafNode nonleaf=(NonleafNode)root;
for(TreeNode child:nonleaf.getChildren()){
printTree(child);
}
}
else{
System.out.println("\n一個葉子節點:");
LeafNode leaf=(LeafNode)root;
for(MinCluster cluster:leaf.getChildren()){
System.out.println("\n一個最小簇:");
for(String mark:cluster.getInst_marks()){
System.out.print(mark+"\t");
point_num++;
}
}
}
}
public static void main(String[] args) {
BIRCH birch=new BIRCH();
TreeNode root=birch.buildBTree("/home/orisun/test/iris.shuffled");
birch.point_num=0;
birch.printTree(root);
System.out.println();
//birch.printLeaf(birch.leafNodeHead);
//確認被分類的point instance和掃描數據庫時錄入的point instance的個數是一致的
System.out.println(birch.point_num);
}
}
最后我們來總結一BIRCH的優勢和劣勢。
優點：
節省內在。葉子節點放在磁盤分區上，非葉子節點僅僅是存儲了一個CF值，外加指向父節點和孩子節點的指針。
快。合并兩個兩簇只需要兩個CF算術相加即可；計算兩個簇的距離只需要用到(N,LS,SS)這三個值足矣。
一遍掃描數據庫即可建立B樹。
可識別噪聲點。建立好B樹后把那些包含數據點少的MinCluster當作outlier。
由于B樹是高度平衡的，所以在樹上進行插入或查找操作很快。
缺點：
結果依賴于數據點的插入順序。本屬于同一個簇的點可能由于插入順序相差很遠而分到不同的簇中，即使同一個點在不同的時刻被插入，也會被分到不同的簇中。
對非球狀的簇聚類效果不好。這取決于簇直徑和簇間距離的計算方法。
對高維數據聚類效果不好。
由于每個節點只能包含一定數目的子節點，最后得出來的簇可能和自然簇相差很大。
BIRCH適合于處理需要數十上百小時聚類的數據，但在整個過程中算法一旦中斷，一切必須從頭再來。
局部性也導致了BIRCH的聚類效果欠佳。當一個新點要插入B樹時，它只跟很少一部分簇進行了相似性(通過計算簇間距離)比較，高的efficient導致低的effective。
總結
以上是生活随笔為你收集整理的聚类算法的java实现_聚类算法之BIRCH（Java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 给定两个字符串形式的非负整数 num1
- 下一篇： DOS常见命令