精华内容
下载资源
问答
  • 层次聚类算法原理

    千次阅读 2018-09-21 10:15:11
    层次聚类算法原理及实现Hierarchical Clustering 2016年4月19日 BY 蓝鲸 5 COMMENTS 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。...

    层次聚类算法的原理及实现Hierarchical Clustering

    2016年4月19日 BY 蓝鲸 5 COMMENTS

    层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法,本篇文章介绍合并方法。

    hierarchicalcluster

    层次聚类的合并算法

    层次聚类的合并算法通过计算两类数据点间的相似性,对所有数据点中最为相似的两个数据点进行组合,并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性,距离越小,相似度越高。并将距离最近的两个数据点或类别进行组合,生成聚类树。

    欧几里德距离矩阵

    层次聚类使用欧式距离来计算不同类别数据点间的距离(相似度)。我们在前面的几篇文章中都曾经介绍过欧氏距离的计算方法,本篇文章将通过创建一个欧式距离矩阵来计算和对比不同类别数据点间的距离,并对距离值最小的数据点进行组合。以下是欧式距离的计算公式。

    Euclidean distance

    以下为示例数据,我们通过欧氏距离计算下面A到G的欧式距离矩阵,并通过合并的方法将相似度最高的数据点进行组合,并创建聚类树。

    数据

    创建欧式距离矩阵的方法很简单,将每个类别的数据点分别与A-G中的每个数据点计算距离值,其中A—>B表示数据点A到数据点B的距离,B—>A则代表数据点B到数据点A的距离。这两个距离值是相同的,因此欧式距离矩阵呈对角线对称(绿色部分和蓝色部分)。其中对角线的0值是数据点与自己的距离值。我们将所有数据点间的距离结果进行对比,选择其中距离最近的两个数据点进行组合,并迭代这一过程。下图显示了欧式矩阵的逻辑和计算方法。

    欧式距离矩阵1

    数据点之间的距离    

    对于示例中的数据点,我们通过计算获得了下面的欧式距离矩阵。其中数据点B到数据点C的距离在所有的距离值中最小,为1.00。以下为数据点间距离值的计算公式。

    BtoA

    经过计算数据点B和数据点C与其他数据点相比有最高的相似度。因此,我们将数据点B和数据点C进行组合。并再次计算其他数据点间的距离。

    距离矩阵1

    数据点与组合数据点间的距离

    将数据点B与数据点C进行组合后,重新计算各类别数据点间的距离矩阵。数据点间的距离计算方式与之前的方法一样。这里需要说明的是组合数据点(B,C)与其他数据点间的计算方法。当我们计算(B,C)到A的距离时,需要分别计算B到A和C到A的距离均值。

    BCtoA

    经过计算数据点D到数据点E的距离在所有的距离值中最小,为1.20。这表示在当前的所有数据点中(包含组合数据点),D和E的相似度最高。因此我们将数据点D和数据点E进行组合。并再次计算其他数据点间的距离。

    距离矩阵2

    后面的工作就是不断的重复计算数据点与数据点,数据点与组合数据点间的距离。这个步骤应该由程序来完成。这里由于数据量较小,我们手工计算并列出每一步的距离计算和数据点组合的结果。

    这一步中,数据点A和数据点F的距离值在所有距离值中最小,因此我们将A和F进行组合,生成组合数据点(A,F)。

    距离矩阵3

    到此为止除了数据点G以外,其他的数据点都已经根据距离值(相似度)进行了组合。聚类树的最底层已经完成。下面我们将继续计算组合数据点间的距离,并对相似度最高的组合数据点进行合并。

    两个组合数据点间的距离

    计算两个组合数据点间距离的方法有三种,分别为Single Linkage,Complete Linkage和Average Linkage。在开始计算之前,我们先来介绍下这三种计算方法以及各自的优缺点。

    Single Linkage

    Single Linkage的计算方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

    Complete Linkage

    Complete Linkage的计算方法与Single Linkage相反,将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反,两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

    Average Linkage

    Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大,但结果比前两种方法更合理。

    我们使用Average Linkage计算组合数据点间的距离。下面是计算组合数据点(A,F)到(B,C)的距离,这里分别计算了(A,F)和(B,C)两两间距离的均值。

     

    AFtoBC

    通过计算及对比不同组合数据点间间的距离。(A,F)到(B,C)的距离在所有组合数据点间最小,为13.25。说明(A,F)到(B,C)相似度最高。因此,将(A,F)到(B,C)组合为(A,F,B,C)。

    距离矩阵4

    使用与之前相同的方法计算出组合数据点(D,E)和G的距离在目前所有组合数据点中最小。为34.70。将(D,E)和G组合为(D,E,G)。

    距离矩阵5

    最终,通过计算和合并,我们获得了两个组合数据点(A,F,B,C)和(D,E,G)。这也是聚类树的最顶层的两个数据点。下面,我们按之前的计算步骤来构建聚类树。

    距离矩阵6

     

    层次聚类树状图

    将前面的每一步的计算结果以树状图的形式展现出来就是层次聚类树。最底层是原始A到G的7个数据点。依照7个数据点间的相似度组合为聚类树的第二层(A,F),(B,C),(D,E)和G。以此类推生成完整的层次聚类树状图。以下为简单的示意图。

    Hierarchical Clustering



    Read more: http://bluewhale.cc/2016-04-19/hierarchical-clustering.html#ixzz5RhN1UuTH

    展开全文
  • 层次聚类算法原理及实现

    万次阅读 2017-12-21 17:29:32
    一、聚类算法介绍  层次法聚类和点分配法聚类。 1.1 点、空间和距离 点集是一种适合于聚类的数据集,每个点都是某空间下的对象。一般意义上,空间只是点的全集,也就是说数据集中的点从该集合中抽样而成。特别...

    聚类

             聚类是对点集进行考察并按照某种距离测度将他们聚成多个“簇”的过程。聚类的目标是使得同一簇内的点之间的距离较短,而不同簇中点之间的距离较大。

    一、聚类算法介绍

         层次法聚类和点分配法聚类。

    1.1     点、空间和距离

    点集是一种适合于聚类的数据集,每个点都是某空间下的对象。一般意义上,空间只是点的全集,也就是说数据集中的点从该集合中抽样而成。特别地,欧式空间下的点就是实数向量。向量的长度就是空间的维度数,而向量的分量通常称为所表示点的坐标(coordinate)

    能够进行聚类的所有空间下都有一个距离测度,即给出空间下任意两点的距离。一般的欧氏距离(点的坐标在各个维度上差值的平方和的算术平方根)可以作为所有欧式空间下的距离测度。

    现代聚类问题可能并不这么简单。他们可能牵涉非常高维的欧式空间或者根本不在欧式空间下聚类。比如,基于文档间高频区分词的共现情况来依据主题对文档聚类。而按照电影爱好者所喜欢的电影类别对他们进行聚类。

    1.2     聚类策略

    按照聚类算法使用的两种不同的基本策略,可以将聚类算法分成两类。

    1)   层次(hierarchical)或凝聚式(agglomerative)算法。

    这类算法一开始将每个点都看成簇。簇与簇之间按照接近度(closeness)来组合,接近度可以按照“接近”的不同含义采用不同的定义。当进一步的组合导致多个原因之下的非期望结果时,上述组合过程结束。比如停止条件为:达到预先给定的簇数目,或者使用簇的紧密度测度方法,一旦两个小簇组合之后得到簇内的点分散的区域较大就停止簇的构建。

    2)   点分配过程算法。按照某个顺序依次考虑每个点,并将它分配到最适合的簇中。该过程通常有一个短暂的初始簇估计阶段。一些变形算法允许临时的簇合并或分裂的过程,或者当点为离群点时允许不将该点分配到任何簇中。

    聚类算法也可以使用如下方式分类:

    1)   欧式空间下,我们可以将点集合概括为其质心,即点的平均。而在非欧式空间下根本没有质心的概念,因此需要其他的簇概括方法

    2)   算法是否假设数据足够小的能够放入内存?或者说数据是否必须主要存放在二次存储器?由于不能将所有簇的所有点都同时放入内存,所以我们将簇的概括表示存放在内存中也是必要的。

    1.3     维数灾难

    “灾难”的一个体现是,在高维空间下,几乎所有点对之间的距离都差不多相等。另一个表现是,几乎任意的两个向量之间都近似正交。

    1.        高维空间下的距离分布

    一个d维欧式空间,假设在一个单位立方体内随机选择n个点,每个点可以表示成[x1,x2,…,xd],其每个xi都是01之间。假定d非常大,两个随机点[x1,x2,…,xd][y1,y2,…,yd]之间的欧式距离为

                                                                                                                        

      上述基于随机数据的论证结果表明,在这么多所有距离近似相等的点对之中发现聚类是很难的一件事。

    2.        向量之间的夹角

    d维空间的随机点ABC,其中d很大。AC可以在任意位置,而B处于坐标原点。那么夹角ABC的余弦为:

     

                                                                                                     

    d不断增长时,分母会随d线性增长,但是分子却是随机值之和,可能为正也可能为负。分子期望为0,分子最大值为 。所以对于很大的d而言,任意两个向量的夹角余弦值几乎肯定接近为0,即夹角近似度等于90度。

    推论为:如果dAB = d1, dBC=d2,dAC≈ 。

    二、层次聚类

    首先考虑欧式空间下的层次聚类。该算法仅可用于规模相对较小的数据集。层次聚类用于非欧式空间时,还有一些与层次聚类相关的额外问题需要考虑。因此,当不存在簇质心或者说簇平均点时,可以考虑采用簇中心点(clustroid)来表示一个簇。

    2.1     欧式空间下的层次聚类

    首先,每个点看作一个簇,通过不断的合并小簇而形成大簇。我们需要提前确定

    (1)         簇如何表示?

    (2)         如何选择哪两个簇进行合并?

    (3)         簇合并何时结束?

    对于欧式空间,(1)通过簇质心或者簇内平均点来表示簇。对于单点的簇,该点就是簇质心。可以初始化簇数目为欧式空间点的数目Cnumber=n。簇之间的距离为质心之间的欧式距离,

    2)选择具有最短距离(或者其他方式)的两个簇进行合并。

    例如,有如下12个点,首先我们将每一个点看做一个簇。

                                                               

    point.txt文件

    4 10
    4 8
    7 10
    6 8
    3 4
    2 2
    5 2
    9 3
    10 5
    11 4
    12 3
    12 6

    1. #include <iostream>  
    2. #include <vector>  
    3. #include <algorithm>  
    4. #include <fstream>  
    5. using namespace std;  
    6. const int iniClusNum = 12;  
    7. const int stopNum = 3;  
    8.   
    9. class Point  
    10. {  
    11. public:  
    12.     double x;  
    13.     double y;  
    14.     int NumPBelong;  
    15.     Point()  
    16.     {  
    17.         x=0;  
    18.         y=0;  
    19.         NumPBelong = -1;  
    20.     }  
    21.     Point(double x1, double y1, int f=-1):x(x1),y(y1),NumPBelong(f){}  
    22.     const Point& operator=(const Point& p)  
    23.     {  
    24.         x = p.x;  
    25.         y=p.y;  
    26.         NumPBelong = p.NumPBelong;  
    27.         return *this;  
    28.     }  
    29. };  
    30.   
    31. class ManagerP  
    32. {  
    33. public:  
    34.     double getDistance(const Point& p1, const Point& p2)  
    35.     {  
    36.         return sqrt(pow((p1.x-p2.x),2)+pow((p1.y-p2.y),2));  
    37.     }  
    38.     Point getMean(const Point& p1, const Point& p2)  
    39.     {  
    40.         Point p;  
    41.         p.x = (p1.x+p2.x)/2;  
    42.         p.y=(p1.y+p2.y)/2;  
    43.         return p;  
    44.     }  
    45. };  
    46. class ManagerC  
    47. {  
    48. public:  
    49.     Point Cluster[iniClusNum];  
    50.     vector<int> ClusterLast[iniClusNum];  
    51.     bool isIndexClose[iniClusNum];  
    52.     bool isIndexClose2[iniClusNum];  
    53.     void initCluster()//use txt to init, import txt  
    54.     {  
    55.         ifstream  myfile ( "point.txt" ) ;  
    56.         if  ( !myfile )   
    57.         {   
    58.             cout << "cannot open file." ;   return  ;   
    59.         }  
    60.   
    61.         Point p;  
    62.         int x,y;    
    63.         int i=0;  
    64.         while(!myfile.eof())  
    65.         {  
    66.             myfile>>x>>y;  
    67.             p.x=x;  
    68.             p.y=y;  
    69.             Cluster[i]=p;  
    70.             i++;  
    71.         }  
    72.         myfile.close();  
    73.     }  
    74.     void initIndexClose()  
    75.     {  
    76.             for(int i=0;i<iniClusNum;i++)  
    77.             {  
    78.                 isIndexClose[i]=false;  
    79.                 isIndexClose2[i]=false;  
    80.             }  
    81.     }  
    82.     void print()  
    83.     {  
    84.         for(int i =0;i<iniClusNum;i++)  
    85.         {  
    86.             if(ClusterLast[i].empty())  
    87.             {  
    88.                 continue;  
    89.             }  
    90.             cout<<"cluster "<<i+1<<endl;  
    91.             vector<int>::iterator ite=ClusterLast[i].begin();  
    92.             for(;ite!= ClusterLast[i].end();ite++)  
    93.             {  
    94.                 cout<<*ite<<"\t";  
    95.             }  
    96.             cout<<endl;  
    97.   
    98.         }  
    99.         cout<<endl;  
    100.     }  
    101.         void ClusterAlgo()//use minheap to realize, to optimize  
    102.     {  
    103.   
    104.         int ClustNum = iniClusNum;  
    105.         int clus_index =0;  
    106.         while(ClustNum>stopNum)  
    107.         {  
    108.   
    109.             double min=INT_MAX;  
    110.             int x=-1,y=-1;  
    111.             ManagerP mp;  
    112.             for(int i=0;i<iniClusNum;i++)  
    113.             {  
    114.                 if(isIndexClose[i])  
    115.                 {  
    116.                     continue;  
    117.                 }  
    118.                 for(int j=i+1;j<iniClusNum;j++)  
    119.                 {  
    120.                     if(isIndexClose[j])  
    121.                     {  
    122.                         continue;  
    123.                     }  
    124.   
    125.                     double new_d = mp.getDistance(Cluster[i],Cluster[j]);  
    126.                     if(new_d < min)  
    127.                     {  
    128.                         min = new_d;  
    129.                         x=i;y=j;  
    130.   
    131.                     }  
    132.                 }  
    133.             }  
    134.             if(x==-1 || y==-1)  
    135.             {  
    136.                 break;  
    137.             }  
    138.   
    139.             Point p = mp.getMean(Cluster[x],Cluster[y]);  
    140.             //x<y    store the result  
    141.             if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong==-1)  
    142.             {  
    143.                 cout<<"a0"<<endl;  
    144.                 ClusterLast[clus_index].push_back(x);//xchange to p, y close  
    145.                 ClusterLast[clus_index].push_back(y);  
    146.                 p.NumPBelong = clus_index;  
    147.                 isIndexClose[y]=true;//y is closed  
    148.                 Cluster[x]=p;//new p is open  
    149.                 isIndexClose[x]=false;  
    150.                 isIndexClose2[x]=true;  
    151.                 isIndexClose2[y]=true;  
    152.                 clus_index++;  
    153.   
    154.             }  
    155.             else if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong!=-1)//already exists one cluster  
    156.             {  
    157.                 cout<<"a1"<<endl;  
    158.                 ClusterLast[Cluster[y].NumPBelong].push_back(x);  
    159.                 isIndexClose[x]=true;//x is closed  
    160.                 p.NumPBelong = Cluster[y].NumPBelong;  
    161.                 Cluster[y]=p;//new p is open  
    162.                 isIndexClose2[x]=true;  
    163.             }  
    164.             else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong==-1)  
    165.             {  
    166.                 cout<<"a2"<<endl;  
    167.                 ClusterLast[Cluster[x].NumPBelong].push_back(y);  
    168.                 isIndexClose[y]=true;//y is closed  
    169.                 p.NumPBelong = Cluster[x].NumPBelong;  
    170.                 Cluster[x]=p;//new p is open  
    171.                 isIndexClose2[y]=true;  
    172.             }  
    173.             else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong!=-1)//both are clusteroid  
    174.             {  
    175.                 cout<<"a3"<<endl;  
    176.                 vector<int>::iterator ite = ClusterLast[Cluster[y].NumPBelong].begin();//put y's node in x  
    177.                 for(;ite!=ClusterLast[Cluster[y].NumPBelong].end();ite++)  
    178.                 {  
    179.                     ClusterLast[Cluster[x].NumPBelong].push_back(*ite);  
    180.                 }  
    181.                 ClusterLast[Cluster[y].NumPBelong].clear();  
    182.                 isIndexClose[y]=true;//y is closed  
    183.                 p.NumPBelong = Cluster[x].NumPBelong;  
    184.                 Cluster[x]=p;//new p is open  
    185.                               
    186.             }  
    187.             ClustNum--;  
    188.         }  
    189.         int total_size =0;  
    190.         for(int i=0;i<stopNum;i++)  
    191.         {  
    192.             total_size+=ClusterLast[i].size();  
    193.         }  
    194.         if(total_size<iniClusNum)  
    195.         {  
    196.             int j=0;  
    197.             for(int i=0;i<iniClusNum;i++)  
    198.             {  
    199.                 if(isIndexClose2[i]==false)  
    200.                 {  
    201.                     ClusterLast[stopNum-1-j].push_back(i);  
    202.                     j++;  
    203.                 }  
    204.             }  
    205.   
    206.         }  
    207.     }  
    208.   
    209. };  
    210. int main()  
    211. {  
    212.     ManagerC M;  
    213.     M.initCluster();  
    214.     M.initIndexClose();  
    215.     M.ClusterAlgo();  
    216.     M.print();  
    217.   
    218.     system("pause");  
    219. }  
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <fstream>
    using namespace std;
    const int iniClusNum = 12;
    const int stopNum = 3;
    
    class Point
    {
    public:
    	double x;
    	double y;
    	int NumPBelong;
    	Point()
    	{
    		x=0;
    		y=0;
    		NumPBelong = -1;
    	}
    	Point(double x1, double y1, int f=-1):x(x1),y(y1),NumPBelong(f){}
    	const Point& operator=(const Point& p)
    	{
    		x = p.x;
    		y=p.y;
    		NumPBelong = p.NumPBelong;
    		return *this;
    	}
    };
    
    class ManagerP
    {
    public:
    	double getDistance(const Point& p1, const Point& p2)
    	{
    		return sqrt(pow((p1.x-p2.x),2)+pow((p1.y-p2.y),2));
    	}
    	Point getMean(const Point& p1, const Point& p2)
    	{
    		Point p;
    		p.x = (p1.x+p2.x)/2;
    		p.y=(p1.y+p2.y)/2;
    		return p;
    	}
    };
    class ManagerC
    {
    public:
    	Point Cluster[iniClusNum];
    	vector<int> ClusterLast[iniClusNum];
    	bool isIndexClose[iniClusNum];
    	bool isIndexClose2[iniClusNum];
    	void initCluster()//use txt to init, import txt
    	{
    		ifstream  myfile ( "point.txt" ) ;
    		if  ( !myfile ) 
    		{ 
    			cout << "cannot open file." ;   return  ; 
    		}
    
    		Point p;
    		int x,y;  
    		int i=0;
    		while(!myfile.eof())
    		{
    			myfile>>x>>y;
    			p.x=x;
    			p.y=y;
    			Cluster[i]=p;
    			i++;
    		}
    		myfile.close();
    	}
    	void initIndexClose()
    	{
    			for(int i=0;i<iniClusNum;i++)
    			{
    				isIndexClose[i]=false;
    				isIndexClose2[i]=false;
    			}
    	}
    	void print()
    	{
    		for(int i =0;i<iniClusNum;i++)
    		{
    			if(ClusterLast[i].empty())
    			{
    				continue;
    			}
    			cout<<"cluster "<<i+1<<endl;
    			vector<int>::iterator ite=ClusterLast[i].begin();
    			for(;ite!= ClusterLast[i].end();ite++)
    			{
    				cout<<*ite<<"\t";
    			}
    			cout<<endl;
    
    		}
    		cout<<endl;
    	}
    		void ClusterAlgo()//use minheap to realize, to optimize
    	{
    
    		int ClustNum = iniClusNum;
    		int clus_index =0;
    		while(ClustNum>stopNum)
    		{
    
    			double min=INT_MAX;
    			int x=-1,y=-1;
    			ManagerP mp;
    			for(int i=0;i<iniClusNum;i++)
    			{
    				if(isIndexClose[i])
    				{
    					continue;
    				}
    				for(int j=i+1;j<iniClusNum;j++)
    				{
    					if(isIndexClose[j])
    					{
    						continue;
    					}
    
    					double new_d = mp.getDistance(Cluster[i],Cluster[j]);
    					if(new_d < min)
    					{
    						min = new_d;
    						x=i;y=j;
    
    					}
    				}
    			}
    			if(x==-1 || y==-1)
    			{
    				break;
    			}
    
    			Point p = mp.getMean(Cluster[x],Cluster[y]);
    			//x<y	store the result
    			if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong==-1)
    			{
    				cout<<"a0"<<endl;
    				ClusterLast[clus_index].push_back(x);//xchange to p, y close
    				ClusterLast[clus_index].push_back(y);
    				p.NumPBelong = clus_index;
    				isIndexClose[y]=true;//y is closed
    				Cluster[x]=p;//new p is open
    				isIndexClose[x]=false;
    				isIndexClose2[x]=true;
    				isIndexClose2[y]=true;
    				clus_index++;
    
    			}
    			else if(Cluster[x].NumPBelong==-1 && Cluster[y].NumPBelong!=-1)//already exists one cluster
    			{
    				cout<<"a1"<<endl;
    				ClusterLast[Cluster[y].NumPBelong].push_back(x);
    				isIndexClose[x]=true;//x is closed
    				p.NumPBelong = Cluster[y].NumPBelong;
    				Cluster[y]=p;//new p is open
    				isIndexClose2[x]=true;
    			}
    			else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong==-1)
    			{
    				cout<<"a2"<<endl;
    				ClusterLast[Cluster[x].NumPBelong].push_back(y);
    				isIndexClose[y]=true;//y is closed
    				p.NumPBelong = Cluster[x].NumPBelong;
    				Cluster[x]=p;//new p is open
    				isIndexClose2[y]=true;
    			}
    			else if(Cluster[x].NumPBelong!=-1 && Cluster[y].NumPBelong!=-1)//both are clusteroid
    			{
    				cout<<"a3"<<endl;
    				vector<int>::iterator ite = ClusterLast[Cluster[y].NumPBelong].begin();//put y's node in x
    				for(;ite!=ClusterLast[Cluster[y].NumPBelong].end();ite++)
    				{
    					ClusterLast[Cluster[x].NumPBelong].push_back(*ite);
    				}
    				ClusterLast[Cluster[y].NumPBelong].clear();
    				isIndexClose[y]=true;//y is closed
    				p.NumPBelong = Cluster[x].NumPBelong;
    				Cluster[x]=p;//new p is open
    							
    			}
    			ClustNum--;
    		}
    		int total_size =0;
    		for(int i=0;i<stopNum;i++)
    		{
    			total_size+=ClusterLast[i].size();
    		}
    		if(total_size<iniClusNum)
    		{
    			int j=0;
    			for(int i=0;i<iniClusNum;i++)
    			{
    				if(isIndexClose2[i]==false)
    				{
    					ClusterLast[stopNum-1-j].push_back(i);
    				    j++;
    				}
    			}
    
    		}
    	}
    
    };
    int main()
    {
    	ManagerC M;
    	M.initCluster();
    	M.initIndexClose();
    	M.ClusterAlgo();
    	M.print();
    
    	system("pause");
    }
      如果仔细观察数据的数据在坐标系的分布,可以分成3簇。于是我们使StopNum =3;输出如下,采用的是输入数据的索引

                                                                    


     

     

    展开全文
  • 主要介绍了Python聚类算法之凝聚层次聚类原理与具体使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类 K均值聚类算法的python实现,以及聚类算法与EM最大算法的关系 参考引用 先上一张gif的k均值聚类算法动态图片,让大家对算法有个感性认识: ...
  • 层次聚类算法原理及python实现

    万次阅读 多人点赞 2018-01-05 11:27:52
    层次聚类(Hierarchical Clustering)是一种聚类算法,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。

    一、算法简介

    主流的聚类算法可以大致分成层次化聚类算法、划分式聚类算法(图论、KMean)、基于密度(DBSCAN)和网格的聚类算法和其他聚类算法。

    1.1 基本概念

    1. 层次聚类(Hierarchical Clustering)是一种聚类算法,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。

    2. 聚类树的创建方法:自下而上的合并,自上而下的分裂。(这里介绍第一种)

    1.2 层次聚类的合并算法

    层次聚类的合并算法通过计算两类数据点间的相似性,对所有数据点中最为相似的两个数据点进行组合,并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性,距离越小,相似度越高。并将距离最近的两个数据点或类别进行组合,生成聚类树。合并过程如下:

    1. 我们可以获得一个的距离矩阵 X,其中表示的距离,称为数据点与数据点之间的距离。记每一个数据点为 将距离最小的数据点进行合并,得到一个组合数据点,记为 G
    2. 数据点与组合数据点之间的距离: 当计算G的距离时,需要计算G中每一个点的距离。
    3. 组合数据点组合数据点之间的距离:主要有Single Linkage,Complete Linkage和Average Linkage 三种。这三种算法介绍如下,摘自

        Single Linkage
        Single Linkage的计算方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

        Complete Linkage
        Complete Linkage的计算方法与Single Linkage相反,将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反,两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

        Average Linkage
        Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大,但结果比前两种方法更合理。
       

    二、Python实现

    可以直接使用 scipy.cluster.hierarchy.linkage !!!

    如下代码实现的是将一组数进行层次聚类。

    # -*- coding: utf-8 -*-
    import numpy as np
    from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
    from matplotlib import pyplot as plt
    
    def hierarchy_cluster(data, method='average', threshold=5.0):
        '''层次聚类
        
        Arguments:
            data [[0, float, ...], [float, 0, ...]] -- 文档 i 和文档 j 的距离
        
        Keyword Arguments:
            method {str} -- [linkage的方式: single、complete、average、centroid、median、ward] (default: {'average'})
            threshold {float} -- 聚类簇之间的距离
    
        Return:
            cluster_number int -- 聚类个数
            cluster [[idx1, idx2,..], [idx3]] -- 每一类下的索引
        '''
        data = np.array(data)
    
        Z = linkage(data, method=method)
        cluster_assignments = fcluster(Z, threshold, criterion='distance')
        print type(cluster_assignments)
        num_clusters = cluster_assignments.max()
        indices = get_cluster_indices(cluster_assignments)
    
        return num_clusters, indices
    
    
    
    def get_cluster_indices(cluster_assignments):
        '''映射每一类至原数据索引
        
        Arguments:
            cluster_assignments 层次聚类后的结果
        
        Returns:
            [[idx1, idx2,..], [idx3]] -- 每一类下的索引
        '''
        n = cluster_assignments.max()
        indices = []
        for cluster_number in range(1, n + 1):
            indices.append(np.where(cluster_assignments == cluster_number)[0])
        
        return indices
    
    
    if __name__ == '__main__':
        
    
        arr = [[0., 21.6, 22.6, 63.9, 65.1, 17.7, 99.2],
        [21.6, 0., 1., 42.3, 43.5, 3.9, 77.6],
        [22.6, 1., 0, 41.3, 42.5, 4.9, 76.6],
        [63.9, 42.3, 41.3, 0., 1.2, 46.2, 35.3],
        [65.1, 43.5, 42.5, 1.2, 0., 47.4, 34.1],
        [17.7, 3.9, 4.9, 46.2, 47.4, 0, 81.5],
        [99.2, 77.6, 76.6, 35.3, 34.1, 81.5, 0.]]
    
        arr = np.array(arr)
        r, c = arr.shape
        for i in xrange(r):
            for j in xrange(i, c):
                if arr[i][j] != arr[j][i]:
                    arr[i][j] = arr[j][i]
        for i in xrange(r):
            for j in xrange(i, c):
                if arr[i][j] != arr[j][i]:
                    print(arr[i][j], arr[j][i])
    
        num_clusters, indices = hierarchy_cluster(arr)
    
    
        print "%d clusters" % num_clusters
        for k, ind in enumerate(indices):
            print "cluster", k + 1, "is", ind
    ## 运行结果
    5 clusters
    cluster 1 is [1 2]
    cluster 2 is [5]
    cluster 3 is [0]
    cluster 4 is [3 4]
    cluster 5 is [6]
    

    上述结果可视化:






    展开全文
  • 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有...


    层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法,本篇文章介绍合并方法。

    hierarchicalcluster

    层次聚类的合并算法

    层次聚类的合并算法通过计算两类数据点间的相似性,对所有数据点中最为相似的两个数据点进行组合,并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性,距离越小,相似度越高。并将距离最近的两个数据点或类别进行组合,生成聚类树。

    欧几里德距离矩阵

    层次聚类使用欧式距离来计算不同类别数据点间的距离(相似度)。我们在前面的几篇文章中都曾经介绍过欧氏距离的计算方法,本篇文章将通过创建一个欧式距离矩阵来计算和对比不同类别数据点间的距离,并对距离值最小的数据点进行组合。以下是欧式距离的计算公式。

    Euclidean distance

    以下为示例数据,我们通过欧氏距离计算下面A到G的欧式距离矩阵,并通过合并的方法将相似度最高的数据点进行组合,并创建聚类树。

    数据

    创建欧式距离矩阵的方法很简单,将每个类别的数据点分别与A-G中的每个数据点计算距离值,其中A—>B表示数据点A到数据点B的距离,B—>A则代表数据点B到数据点A的距离。这两个距离值是相同的,因此欧式距离矩阵呈对角线对称(绿色部分和蓝色部分)。其中对角线的0值是数据点与自己的距离值。我们将所有数据点间的距离结果进行对比,选择其中距离最近的两个数据点进行组合,并迭代这一过程。下图显示了欧式矩阵的逻辑和计算方法。

    欧式距离矩阵1

    数据点之间的距离    

    对于示例中的数据点,我们通过计算获得了下面的欧式距离矩阵。其中数据点B到数据点C的距离在所有的距离值中最小,为1.00。以下为数据点间距离值的计算公式。

    BtoA

    经过计算数据点B和数据点C与其他数据点相比有最高的相似度。因此,我们将数据点B和数据点C进行组合。并再次计算其他数据点间的距离。

    距离矩阵1

    数据点与组合数据点间的距离

    将数据点B与数据点C进行组合后,重新计算各类别数据点间的距离矩阵。数据点间的距离计算方式与之前的方法一样。这里需要说明的是组合数据点(B,C)与其他数据点间的计算方法。当我们计算(B,C)到A的距离时,需要分别计算B到A和C到A的距离均值。

    BCtoA

    经过计算数据点D到数据点E的距离在所有的距离值中最小,为1.20。这表示在当前的所有数据点中(包含组合数据点),D和E的相似度最高。因此我们将数据点D和数据点E进行组合。并再次计算其他数据点间的距离。

    距离矩阵2

    后面的工作就是不断的重复计算数据点与数据点,数据点与组合数据点间的距离。这个步骤应该由程序来完成。这里由于数据量较小,我们手工计算并列出每一步的距离计算和数据点组合的结果。

    这一步中,数据点A和数据点F的距离值在所有距离值中最小,因此我们将A和F进行组合,生成组合数据点(A,F)。

    距离矩阵3

    到此为止除了数据点G以外,其他的数据点都已经根据距离值(相似度)进行了组合。聚类树的最底层已经完成。下面我们将继续计算组合数据点间的距离,并对相似度最高的组合数据点进行合并。

    两个组合数据点间的距离

    计算两个组合数据点间距离的方法有三种,分别为Single Linkage,Complete Linkage和Average Linkage。在开始计算之前,我们先来介绍下这三种计算方法以及各自的优缺点。

    Single Linkage

    Single Linkage的计算方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

    Complete Linkage

    Complete Linkage的计算方法与Single Linkage相反,将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反,两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

    Average Linkage

    Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大,但结果比前两种方法更合理。

    我们使用Average Linkage计算组合数据点间的距离。下面是计算组合数据点(A,F)到(B,C)的距离,这里分别计算了(A,F)和(B,C)两两间距离的均值。

     

    AFtoBC

    通过计算及对比不同组合数据点间间的距离。(A,F)到(B,C)的距离在所有组合数据点间最小,为13.25。说明(A,F)到(B,C)相似度最高。因此,将(A,F)到(B,C)组合为(A,F,B,C)。

    距离矩阵4

    使用与之前相同的方法计算出组合数据点(D,E)和G的距离在目前所有组合数据点中最小。为34.70。将(D,E)和G组合为(D,E,G)。

    距离矩阵5

    最终,通过计算和合并,我们获得了两个组合数据点(A,F,B,C)和(D,E,G)。这也是聚类树的最顶层的两个数据点。下面,我们按之前的计算步骤来构建聚类树。

    距离矩阵6

     

    层次聚类树状图

    将前面的每一步的计算结果以树状图的形式展现出来就是层次聚类树。最底层是原始A到G的7个数据点。依照7个数据点间的相似度组合为聚类树的第二层(A,F),(B,C),(D,E)和G。以此类推生成完整的层次聚类树状图。以下为简单的示意图。

    Hierarchical Clustering

    —【所有文章及图片版权归 蓝鲸(王彦平)所有。欢迎转载,但请注明转自“蓝鲸网站分析博客”。】—



    展开全文
  • 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有...
  • 点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据,从而形成树形的聚类结构...
  • 【聚类算法】层次聚类算法

    千次阅读 2019-11-19 21:37:25
    层次聚类有两种聚类的方式: Agglomerative - 从下至上的聚类 将每一个数据样本作为一个独立的簇。在每一次迭代中将相似的簇合并起来,知道整份数据集结成成一个簇或多个簇 Divsive - 从上...
  • R聚类算法-层次聚类算法

    千次阅读 2017-07-24 16:00:48
    层次聚类算法又称为树聚类算法,它根据数据之间的距离,透过一种层次架构方式,反复将数据进行聚合,创建一个层次以分解给定的数据集。 常用于一维数据的自动分组层次聚类方法 hclust(dist) dist 样本的距离矩阵 ...
  • 聚类分析常用算法原理:KMeans,DBSCAN, 层次聚类

    万次阅读 多人点赞 2018-01-01 10:52:32
    聚类分析是非监督学习的很重要的领域。所谓非监督学习,就是数据是...下面是sklearn中对各种聚类算法的比较。 KMeansKMeans算法在给定一个数k之后,能够将数据集分成k个“簇”C={C1,C2,⋯,Ck}\mathcal C = \{C_1, C_2
  • 机器学习实战——层次聚类算法1 层次聚类概述2 sklearn中的实现 1 层次聚类概述 层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构。 数据集的划分可采用"自底向上"的聚合策略,也可采用&...
  • 层次聚类算法

    万次阅读 2016-06-05 09:23:29
    层次聚类算法是一个应用广泛的算法,小编最近要做对比实验,实现了其中一个版本,为了验证实验效果,结合我国各...所有本文从3部分来介绍,首先简介层次聚类算法,然后讲解其实现原理,最后结合一个实例进行分析对比。
  • 层次聚类算法(HCA)是一种聚类分析方法,它通过层次结构搜索聚类的最佳分布。层次聚类的策略通常有两种类型:使用自下而上的过程进行聚集,而使用自上而下的过程进行分裂。但是,大多数聚类方法都有两个缺点:使用...
  • 利用层次结构的平衡迭代归约和聚类(Balanced Iterative Reducing and Clustering usingHierarchies, BIRCH)是为大量数值数据聚类设计的,它将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样的其他聚类算法(在其后...
  • 1.1 层次聚类原理及分类 1)层次法(Hierarchicalmethods):先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算类与类之间的距离,将距离最近的类合并为一个大类。不停的合并,直到合成了一...
  • 层次聚类matlab程序

    2016-01-05 20:25:12
    层次聚类的matlab程序,数据来源为80个平面点坐标。
  • 常见几个聚类算法原理

    千次阅读 2020-02-06 20:38:54
    聚类算法的思想: 给定N个训练样本(未标记的)x1,x2,...,xN,目标是把比较“接近” 的样本放到一个cluster里, 总共得到K个cluster。 聚类算法的目标: 类内紧致,类间分离 一、K-means算法 1、算法步骤: ...
  • 别看层次聚类算法简单,但是实现起来在数据结构方面还需要思考一番,不是那么轻而易举的确定数据结构,实现过的人应该知道的。1.Code# -*- coding: utf-8 -*- """ @author: 蔚蓝的天空Tom Talk is ...
  • 基于连通模型(connectivited-based):如层次聚类,按照对象之间的距离聚类。(距离的定义可以有很多种)。 基于中心点(centroid-based):如K-means,每个cluster都维持有一个中心点。 基于分布模型(distribution-...
  • GMM是一种聚类算法,每个component就是一个聚类中心 。即在只有样本点,不知道样本分类(含有隐含变量)的情况下,计算出模型参数(π,u和Σ)----这显然可以用EM算法来求解。再用训练好的模型去差别样本所属的分类...
  • 层次聚类1.1 凝聚聚类1.2 层次图1.3 不同凝聚算法比较2. Sklearn 实现2.1 层次图可视化参考文献 1. 层次聚类 层次聚类(hierarchical clustering)试图在不同层次对数据集进行划分,从而形成树形的聚类结构。数据...
  • 这篇文章主要介绍了Python聚类算法之凝聚层次聚类原理与具体使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下 本文实例讲述了Python聚类算法之凝聚层次聚类。分享给大家供大家参考,具体如下: 凝聚层次聚类:...
  • K-Means聚类算法是非监督学习方法。对于样本数据,按样本之间的距离大小,将样本划分为K个簇。让簇内的点之间距离尽可能的小,同时让簇之间的距离尽可能的大。 簇划分为(C1,C2,C3,…,Ck)(C_1, C_2, C_3, …, C_...
  • 掌握 C-means与分级聚类算法算法思想及原理,并能够熟练运用这些算法进行聚类分析; 能够分析二者的优缺点 二、实验内容 采用C均值聚类算法对男女生样本数据中的身高、体重2个特征进行聚类分析,考察不同的类别...
  • 聚类算法(2):系统聚类/层次聚类算法

    万次阅读 多人点赞 2019-06-20 15:23:30
    聚类算法(4)--Hierarchical clustering层次聚类 系统聚类:相当于自下而上法,也就是层次聚类 目录 一、系统聚类 1. 系统聚类实现的一般步骤 2. 常用的距离 3. 类间距离 二、手动实现过程 三、代码实现 1....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,436
精华内容 4,174
关键字:

层次聚类算法原理

友情链接: SFTPi.rar