聚類算法通常會得到一種分類，將n個點聚合成k類，同一聚類（即插槽簇）中的對象相似度較高；而不同類中的對象相似度較小。
聚類算法的基本流程如下：
（1）從n個節點中選擇 k 個節點作為初始聚類中心。（2）將剩余節點根據它們與這k個聚類中心的代價大小，分別將它們分配給與其代價最小的（聚類中心所代表的）聚類。（3）更新聚類的聚類中心。不斷重復（2）（3）這一過程將剩下其它節點分配完畢。（4）排序，將各聚類按照聚類間節點代價和高低降序排列。
? ? ? ? ?下面詳細解釋上述步驟。
（1）從n個節點中選擇 k 個節點作為初始聚類中心
由于K-MEANS算法（一種典型的聚類算法，隨機確定k個聚類中心）有缺點：產生類的大小相差不會很大，對于臟數據很敏感。所以采用最大最小距離算法確定這k個聚類中心。最大最小距離算法是識別領域中的一種試探性算法。思想是取盡可能離得遠的對象作為聚類中心，以避免聚類中心過于鄰近。
步驟如下：
1.計算各節點到其他節點的最大代價總和，取滿足最大的點i（可理解為距其他節點最遠）為聚類1的中心點。
2.計算其他節點到點的最大代價，取滿足最大的i點為聚類2的中心點。
3. 計算其他節點到、點的最大代價，取滿足最大的i點為聚類3的中心點。
4. 計算其他節點到、、點的最大代價，取滿足最大的i點為聚類4的中心點。
以此類推直到找到k個聚類中心點。
?
（2）將剩余節點根據它們與這些聚類中心的代價大小，分別將它們分配給與其代價最小的（聚類中心所代表的）聚類
依次將不是聚類中心點的節點分配到k個聚類中去。若某類中已經有兩個節點，則在分配進入該節點之后還要進行更新聚類中心點的操作（見后（3）詳解）。
?
（3）更新聚類的聚類中心
當某個聚類中存在3個或3個以上節點時需要更新此聚類中心點。采用K-medoids算法中的更新聚類中心方式。在 K-medoids算法中，我們將從當前聚類中選取這樣一個點——它到其他所有（當前聚類中）點的代價之和最小——作為中心點。
?
（4）排序，將各聚類按照聚類間代價高低降序排列。
[cpp] view plain copy
#include <stdio.h> ?
#include <stdlib.h> ?
#include <iostream> ?
#include <math.h> ?
#include "CLSlotClustering.h" ?
#include "CLZone.h" ?
#include "CLVMMinKCut.h" ?
??
using namespace std; ?
??
CLSlotClustering::CLSlotClustering() ?
{ ?
} ?
??
CLSlotClustering::~CLSlotClustering() ?
{ ?
} ?
??
int CLSlotClustering::Find(int i) ?
{ ?
? ? int j; ?
? ? if (m_Parent[i]==i) ?
? ? { ?
? ? ? ? return ?i; ?
? ? } ?
? ? j=m_Parent[i]; ?
? ? Find(j); ?
? ? return 0; ?
} ?
??
CLZone CLSlotClustering::SlotClustering(int C[][MAXNUMBER],int n,int k,int flag) ?
{ ?
? ? m_VexOfMaxCost=0; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //初始化 ?
? ? m_Flag=0; ?
? ? m_Number=(-1); ?
? ? for (int i = 0; i < MAXNUMBER; i++) ?
? ? { ?
? ? ? ? m_Parent[i]=i; ?
? ? ? ? m_VexOfCostSum[i]=0; ?
? ? ? ? for (int j = 0; j < MAXNUMBER; j++) ? ? ? ? ? ?
? ? ? ? { ?
? ? ? ? ? ? m_C[i][j]=0; ?
? ? ? ? } ?
? ? } ?
? ? m_k=k; ?
? ? m_n=n; ?
? ? //cout<<"m_C:"<<endl; ?
? ? for (int i = 0; i < n; i++) ?
? ? { ?
? ? ? ? for (int j = 0; j < n; j++) ?
? ? ? ? { ?
? ? ? ? ? ? m_C[i][j]=C[i][j]; ? ? ? ? ? ? ? ? ? ? ?//讀入代價矩陣 ?
? ? ? ? ? ? //cout<<m_C[i][j]<<"\t"; ?
? ? ? ? } ?
? ? ? ? //cout<<"\n"; ?
? ? } ?
? ? //Sleep(3000); ?
??
? ? FindCenter(); ?
? ? if (!flag) ?
? ? { ?
? ? ? ? Clusting(); ?
? ? } ?
? ? Sort(); ?
? ? return **m_MyZone; ?
} ?
int CLSlotClustering::FindCenter() ? ? ? ? ? ? ?//找k個聚合類的中心點 ?
{ ?
? ? for (int i = 0; i < m_n; i++) ?
? ? { ?
? ? ? ? for (int j = 0; j < m_n; j++) ?
? ? ? ? { ?
? ? ? ? ? ? m_VexOfCostSum[i]+=m_C[i][j]; ?
? ? ? ? } ?
? ? ? ? if (m_VexOfCostSum[i]>m_Flag) ?
? ? ? ? { ?
? ? ? ? ? ? m_VexOfMaxCost=i; ?
? ? ? ? ? ? m_Flag=m_VexOfCostSum[i]; ?
? ? ? ? } ?
? ? } ?
? ? m_MyZone[0]= new CLZone; ?
? ? m_MyZone[0]->m_Center=m_VexOfMaxCost; ? ? ? ?//第一個中心點 ?
? ? m_MyZone[0]->m_Size=1; ?
? ? m_MyZone[0]->m_Member[0]=m_MyZone[0]->m_Center; ?
? ? m_Flag=0; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? m_VexOfMaxCost=0; ? ? ? ??
? ? for (int l = 1; l < m_k; l++) ? ? ? ? ? ? ? ?//找其余中心點 ?
? ? { ?
? ? ? ? for (int k = 0; k < m_n; k++) ?
? ? ? ? { ?
? ? ? ? ? ? if (l>1) ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? if (l==2) ?
? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? m_Cost[k]=m_C[m_MyZone[0]->m_Center][k]; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? ? ? m_Cost[k]=min(m_C[m_MyZone[l-1]->m_Center][k],m_Cost[k]); ? ?//min(Dl(l-1),Dl(l-2)) ?
? ? ? ? ? ? ? ? if (m_Flag<m_Cost[k]) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//max(min(Dl(l-1),Dl(l-2))) ?
? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? m_Flag=m_Cost[k]; ?
? ? ? ? ? ? ? ? ? ? m_VexOfMaxCost=k; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? } ?
? ? ? ? ? ? else ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//第二個節點，只需要maxDl1,不需要min(Dl1,Dl2) ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? if (m_Flag<m_C[m_MyZone[0]->m_Center][k]) ?
? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? m_Flag=m_C[m_MyZone[0]->m_Center][k]; ?
? ? ? ? ? ? ? ? ? ? m_VexOfMaxCost=k; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? } ?
? ? ? ? } ? ??
? ? ? ? m_MyZone[l]=new CLZone; ?
? ? ? ? m_MyZone[l]->m_Center=m_VexOfMaxCost; ? ? ? ? ? ? ? ? ? ?//各類中心點 ?
? ? ? ? m_MyZone[l]->m_Size=1; ?
? ? ? ? m_MyZone[l]->m_Member[0]=m_MyZone[l]->m_Center; ?
? ? ? ? m_Flag=0; ?
? ? } ?
? ? return 0; ?
} ?
??
int CLSlotClustering::Clusting() ?
{ ?
? ? ??
? ? m_VexOfCostSum[m_n-1]=10000; ? ? ? ? ? ? ? ? ? ?//臨時變量 ?
? ? for (int i = 0; i < m_n; i++) ?
? ? { ?
? ? ? ? m_Flag=10000; ?
? ? ? ? m_Flag_IsCenter=0; ?
? ? ? ? for (int j = 0; j < m_k; j++) ? ? ?
? ? ? ? { ?
? ? ? ? ? ? if (i==m_MyZone[j]->m_Member[0]) ? ? //驗證是否是首個中心點，如果是則不進行聚合操作 ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? m_Parent[i]=i; ?
? ? ? ? ? ? ? ? m_Flag_IsCenter=1; ?
? ? ? ? ? ? ? ? break; ?
? ? ? ? ? ? } ?
? ? ? ? ? ? if (m_Flag>m_C[i][m_MyZone[j]->m_Center]&&m_C[i][m_MyZone[j]->m_Center]!=0) ? ? ? ?//記錄i點離某個中心最近 ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? m_Flag=m_C[i][m_MyZone[j]->m_Center]; ?
? ? ? ? ? ? ? ? m_Parent[i]=Find(m_MyZone[j]->m_Center); ?
? ? ? ? ? ? ? ? m_Number=j; ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? ? ? if (m_Flag_IsCenter==0&&m_Number!=(-1)) ? ? ? ? ? ? ? ? ? ? ? ? ? ? //將i點聚合 ?
? ? ? ? { ?
? ? ? ? ? ? m_MyZone[m_Number]->m_Member[m_MyZone[m_Number]->m_Size]=i; ?
? ? ? ? ? ? (m_MyZone[m_Number]->m_Size)++; ?
? ? ? ? ? ? if (m_MyZone[m_Number]->m_Size>2) ? ? ? ? ? ? ? ? ? ? ? ? ? ? //當某聚合類中數量大于2時需要檢驗是否要改變聚合類中心 ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? for (int k = 0; k < m_MyZone[m_Number]->m_Size; k++) ?
? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? m_VexOfCostSum[k]=0; ?
? ? ? ? ? ? ? ? ? ? for (int l = 0; l < m_MyZone[m_Number]->m_Size; l++) ?
? ? ? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? ? ? m_VexOfCostSum[k]+=m_C[m_MyZone[m_Number]->m_Member[k]][m_MyZone[m_Number]->m_Member[l]]; ?
? ? ? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? ? ? ? ? if (m_VexOfCostSum[k]<m_VexOfCostSum[m_n-1]) ?
? ? ? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? ? ? m_VexOfCostSum[m_n-1]=m_VexOfCostSum[k]; ?
? ? ? ? ? ? ? ? ? ? ? ? m_MyZone[m_Number]->m_Center=m_MyZone[m_Number]->m_Member[k]; ?
? ? ? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? ? ? //cout<<"changed--m_MyZone["<<m_Number<<"]->m_Center:"<<m_MyZone[m_Number]->m_Center<<endl; ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? ? ? m_Number=(-1); ?
? ? } ?
? ? return 0; ?
} ?
??
int CLSlotClustering::Sort() ?
{ ?
? ? m_Flag=0; ?
? ? for (int i = 0; i < m_n; i++) ? ? ? ? ? ? ? ? ? ? ? ?//得到各點到其他聚合類的代價和 ?
? ? { ?
? ? ? ? m_VexOfCostSum[i]=0; ?
? ? ? ? for (int j = 0; j < m_n; j++) ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? { ?
? ? ? ? ? ? if (m_Parent[i]==m_Parent[j]) ? ? ? ? ? ? ? //若i,j為同一個集合，則查看下一個點 ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? continue; ?
? ? ? ? ? ? } ?
? ? ? ? ? ? else ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? m_VexOfCostSum[i]+=m_C[i][j]; ?
? ? ? ? ? ? } ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? } ?
? ? } ?
? ? m_MyZone[m_k]=new CLZone; ?
? ? for (int k = 0; k < m_k; k++) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//得到各類到其他類的代價和 ?
? ? { ?
? ? ? ? m_MyZone[k]->m_SumOfCost=0; ?
? ? ? ? for (int l = 0; l < m_MyZone[k]->m_Size; l++) ?
? ? ? ? { ?
? ? ? ? ? ? m_MyZone[k]->m_SumOfCost+=m_VexOfCostSum[m_MyZone[k]->m_Member[l]]; ? ? ? ? ? ??
? ? ? ? } ?
? ? } ?
? ? for (int i = 0; i < m_k; i++) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//各聚合類降序排序 ?
? ? { ?
? ? ? ? for (int j = i+1; j < m_k; j++) ?
? ? ? ? { ?
? ? ? ? ? ? if (m_MyZone[i]->m_SumOfCost<m_MyZone[j]->m_SumOfCost) ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? m_MyZone[m_k]=m_MyZone[i]; ?
? ? ? ? ? ? ? ? m_MyZone[i]=m_MyZone[j]; ?
? ? ? ? ? ? ? ? m_MyZone[j]=m_MyZone[m_k]; ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? } ?
? ? /*for (int i = 0; i < m_k; i++)?
? ? {?
? ? ? ? cout<<"m_MyZone["<<i<<"]->m_Center:"<<m_MyZone[i]->m_Center<<"\t"<<"m_MyZone["<<i<<"]->Size:"<<m_MyZone[i]->m_Size<<"\t"<<"m_MyZone["<<i<<"]->Member:\n";?
? ? ? ? for (int j = 0; j < m_MyZone[i]->m_Size; j++)?
? ? ? ? {?
? ? ? ? ? ? cout<<m_MyZone[i]->m_Member[j]<<"\t";?
? ? ? ? }?
? ? ? ? cout<<endl;?
? ? }*/ ?
? ? return 0; ?
}

總結

以上是生活随笔為你收集整理的最大最小距离算法(K-MEANS K-medoids )聚类算法的结合运用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。