苏州网络推广苏州网站建设,伦教网站开发,门户网站优点,专做h5的公司网站聚类算法通常会得到一种分类#xff0c;将n个点聚合成k类#xff0c;同一聚类#xff08;即插槽簇#xff09;中的对象相似度较高#xff1b;而不同类中的对象相似度较小。聚类算法的基本流程如下#xff1a;#xff08;1#xff09;从n个节点中选择 k 个节点作为初始聚… 聚类算法通常会得到一种分类将n个点聚合成k类同一聚类即插槽簇中的对象相似度较高而不同类中的对象相似度较小。聚类算法的基本流程如下1从n个节点中选择 k 个节点作为初始聚类中心。2将剩余节点根据它们与这k个聚类中心的代价大小分别将它们分配给与其代价最小的聚类中心所代表的聚类。3更新聚类的聚类中心。不断重复23这一过程将剩下其它节点分配完毕。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; } jm_Parent[i]; Find(j); return 0; } CLZone CLSlotClustering::SlotClustering(int C[][MAXNUMBER],int n,int k,int flag) { m_VexOfMaxCost0; //初始化 m_Flag0; 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_kk; m_nn; //coutm_C:endl; for (int i 0; i n; i) { for (int j 0; j n; j) { m_C[i][j]C[i][j]; //读入代价矩阵 //coutm_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_VexOfMaxCosti; m_Flagm_VexOfCostSum[i]; } } m_MyZone[0] new CLZone; m_MyZone[0]-m_Centerm_VexOfMaxCost; //第一个中心点 m_MyZone[0]-m_Size1; m_MyZone[0]-m_Member[0]m_MyZone[0]-m_Center; m_Flag0; m_VexOfMaxCost0; for (int l 1; l m_k; l) //找其余中心点 { for (int k 0; k m_n; k) { if (l1) { if (l2) { 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_Flagm_Cost[k]) //max(min(Dl(l-1),Dl(l-2))) { m_Flagm_Cost[k]; m_VexOfMaxCostk; } } else //第二个节点只需要maxDl1,不需要min(Dl1,Dl2) { if (m_Flagm_C[m_MyZone[0]-m_Center][k]) { m_Flagm_C[m_MyZone[0]-m_Center][k]; m_VexOfMaxCostk; } } } m_MyZone[l]new CLZone; m_MyZone[l]-m_Centerm_VexOfMaxCost; //各类中心点 m_MyZone[l]-m_Size1; m_MyZone[l]-m_Member[0]m_MyZone[l]-m_Center; m_Flag0; } return 0; } int CLSlotClustering::Clusting() { m_VexOfCostSum[m_n-1]10000; //临时变量 for (int i 0; i m_n; i) { m_Flag10000; m_Flag_IsCenter0; for (int j 0; j m_k; j) { if (im_MyZone[j]-m_Member[0]) //验证是否是首个中心点如果是则不进行聚合操作 { m_Parent[i]i; m_Flag_IsCenter1; break; } if (m_Flagm_C[i][m_MyZone[j]-m_Center]m_C[i][m_MyZone[j]-m_Center]!0) //记录i点离某个中心最近 { m_Flagm_C[i][m_MyZone[j]-m_Center]; m_Parent[i]Find(m_MyZone[j]-m_Center); m_Numberj; } } if (m_Flag_IsCenter0m_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_Size2) //当某聚合类中数量大于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_Centerm_MyZone[m_Number]-m_Member[k]; } } //coutchanged--m_MyZone[m_Number]-m_Center:m_MyZone[m_Number]-m_Centerendl; } } m_Number(-1); } return 0; } int CLSlotClustering::Sort() { m_Flag0; 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_SumOfCost0; for (int l 0; l m_MyZone[k]-m_Size; l) { m_MyZone[k]-m_SumOfCostm_VexOfCostSum[m_MyZone[k]-m_Member[l]]; } } for (int i 0; i m_k; i) //各聚合类降序排序 { for (int j i1; j m_k; j) { if (m_MyZone[i]-m_SumOfCostm_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) { coutm_MyZone[i]-m_Center:m_MyZone[i]-m_Center\tm_MyZone[i]-Size:m_MyZone[i]-m_Size\tm_MyZone[i]-Member:\n; for (int j 0; j m_MyZone[i]-m_Size; j) { coutm_MyZone[i]-m_Member[j]\t; } coutendl; }*/ return 0; }
