精华内容
下载资源
问答
  • K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的)1、概述K-means算法是集简单和经典于一身的基于距离的聚类算法采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法...

    K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的)

    1、概述

    K-means算法是集简单和经典于一身的基于距离的聚类算法

    采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。

    该算法认为类簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

    2、核心思想

    通过迭代寻找k个类簇的一种划分方案,使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。

    k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

    k-means算法的基础是最小误差平方和准则,

    其代价函数是:

    8b22c9131be113c6bc0fc8d0c130655a.png

    式中,μc(i)表示第i个聚类的均值。

    各类簇内的样本越相似,其与该类均值间的误差平方越小,对所有类所得到的误差平方求和,即可验证分为k类时,各聚类是否是最优的。

    上式的代价函数无法用解析的方法最小化,只能有迭代的方法。

    3、算法步骤图解

    下图展示了对n个样本点进行K-means聚类的效果,这里k取2。

    8907956c02233de47c47ec2615b5d4d4.png

    4、算法实现步骤

    k-means算法是将样本聚类成k个簇(cluster),其中k是用户给定的,其求解过程非常直观简单,具体算法描述如下:

    1) 随机选取 k个聚类质心点

    2) 重复下面过程直到收敛  {

    对于每一个样例i,计算其应该属于的类:

    866cb618c4202d54d3133a842ddf05e7.png

    对于每一个类j,重新计算该类的质心:

    4dde222e579d1572e51c9241b328d06e.png

    }

    其伪代码如下:

    ******************************************************************************

    创建k个点作为初始的质心点(随机选择)

    当任意一个点的簇分配结果发生改变时

    对数据集中的每一个数据点

    对每一个质心

    计算质心与数据点的距离

    将数据点分配到距离最近的簇

    对每一个簇,计算簇中所有点的均值,并将均值作为质心

    ********************************************************

    5、K-means聚类算法python实战

    需求:

    对给定的数据集进行聚类

    本案例采用二维数据集,共80个样本,有4个类。

    2bb9eeb879ef76991ef3aec226450e32.png

    1 #!/usr/bin/python

    2 #coding=utf-8

    3 from numpy import *

    4 #加载数据

    5 def loadDataSet(fileName): #解析文件,按tab分割字段,得到一个浮点数字类型的矩阵

    6 dataMat = [] #文件的最后一个字段是类别标签

    7 fr =open(fileName)8 for line infr.readlines():9 curLine = line.strip().split('\t')10 fltLine = map(float, curLine) #将每个元素转成float类型

    11 dataMat.append(fltLine)12 returndataMat13

    14 #计算欧几里得距离

    15 defdistEclud(vecA, vecB):16 return sqrt(sum(power(vecA - vecB, 2))) #求两个向量之间的距离

    17

    18 #构建聚簇中心,取k个(此例中为4)随机质心

    19 defrandCent(dataSet, k):20 n = shape(dataSet)[1]21 centroids = mat(zeros((k,n))) #每个质心有n个坐标值,总共要k个质心

    22 for j inrange(n):23 minJ =min(dataSet[:,j])24 maxJ =max(dataSet[:,j])25 rangeJ = float(maxJ -minJ)26 centroids[:,j] = minJ + rangeJ * random.rand(k, 1)27 returncentroids28

    29 #k-means 聚类算法

    30 def kMeans(dataSet, k, distMeans =distEclud, createCent =randCent):31 m =shape(dataSet)[0]32 clusterAssment = mat(zeros((m,2))) #用于存放该样本属于哪类及质心距离

    33 #clusterAssment第一列存放该数据所属的中心点,第二列是该数据到中心点的距离

    34 centroids =createCent(dataSet, k)35 clusterChanged = True #用来判断聚类是否已经收敛

    36 whileclusterChanged:37 clusterChanged =False;38 for i in range(m): #把每一个数据点划分到离它最近的中心点

    39 minDist = inf; minIndex = -1;40 for j inrange(k):41 distJI =distMeans(centroids[j,:], dataSet[i,:])42 if distJI <43 mindist="distJI;" minindex="j">

    44 if clusterAssment[i,0] != minIndex: clusterChanged = True; #如果分配发生变化,则需要继续迭代

    45 clusterAssment[i,:] = minIndex,minDist**2 #并将第i个数据点的分配情况存入字典

    46 printcentroids47 for cent in range(k): #重新计算中心点

    48 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]] #去第一列等于cent的所有列

    49 centroids[cent,:] = mean(ptsInClust, axis = 0) #算出这些数据的中心点

    50 returncentroids, clusterAssment51 #--------------------测试----------------------------------------------------

    52 #用测试数据及测试kmeans算法

    53 datMat = mat(loadDataSet('testSet.txt'))54 myCentroids,clustAssing = kMeans(datMat,4)55 printmyCentroids56 print clustAssing

    运行结果:

    9b590078fc18c5ce0dcdcb93b1f6ac9f.png

    6、K-means算法补充

    K-means算法的缺点及改进方法

    (1)k值的选择是用户指定的,不同的k得到的结果会有挺大的不同,如下图所示,左边是k=3的结果,这个就太稀疏了,蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果,可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的:

    改进:

    对k的选择可以先用一些算法分析数据的分布,如重心和密度等,然后选择合适的k

    7b7a8d29b0f56f3bc8fb646c2571007f.png

    (2)对k个初始质心的选择比较敏感,容易陷入局部最小值。例如,我们上面的算法运行的时候,有可能会得到不同的结果,如下面这两种情况。K-means也是收敛了,只是收敛到了局部最小值:

    改进:

    有人提出了另一个成为二分k均值(bisecting k-means)算法,它对初始的k个质心的选择就不太敏感

    6c65deefda973b2e3ec9cf38841f7de9.png

    (3)存在局限性,如下面这种非球状的数据分布就搞不定了:

    10fdbc0090eaec96884fdc473a6c066b.png

    (4)数据集比较大的时候,收敛会比较慢。

    43>
    展开全文
  • K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的)1、概述K-means算法是集简单和经典于一身的基于距离的聚类算法采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法...

    K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的)

    1、概述

    K-means算法是集简单和经典于一身的基于距离的聚类算法

    采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。

    该算法认为类簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

    2、核心思想

    通过迭代寻找k个类簇的一种划分方案,使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。

    k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

    k-means算法的基础是最小误差平方和准则,

    其代价函数是:

    式中,μc(i)表示第i个聚类的均值。

    各类簇内的样本越相似,其与该类均值间的误差平方越小,对所有类所得到的误差平方求和,即可验证分为k类时,各聚类是否是最优的。

    上式的代价函数无法用解析的方法最小化,只能有迭代的方法。

    3、算法步骤图解

    下图展示了对n个样本点进行K-means聚类的效果,这里k取2。

    4、算法实现步骤

    k-means算法是将样本聚类成k个簇(cluster),其中k是用户给定的,其求解过程非常直观简单,具体算法描述如下:

    1) 随机选取 k个聚类质心点

    2) 重复下面过程直到收敛  {

    对于每一个样例i,计算其应该属于的类:

    对于每一个类j,重新计算该类的质心:

    }

    其伪代码如下:

    ******************************************************************************

    创建k个点作为初始的质心点(随机选择)

    当任意一个点的簇分配结果发生改变时

    对数据集中的每一个数据点

    对每一个质心

    计算质心与数据点的距离

    将数据点分配到距离最近的簇

    对每一个簇,计算簇中所有点的均值,并将均值作为质心

    ********************************************************

    5、K-means聚类算法python实战

    需求:

    对给定的数据集进行聚类

    本案例采用二维数据集,共80个样本,有4个类。

    1 #!/usr/bin/python

    2 #coding=utf-8

    3 from numpy import *

    4 #加载数据

    5 def loadDataSet(fileName): #解析文件,按tab分割字段,得到一个浮点数字类型的矩阵

    6 dataMat = [] #文件的最后一个字段是类别标签

    7 fr =open(fileName)8 for line infr.readlines():9 curLine = line.strip().split('\t')10 fltLine = map(float, curLine) #将每个元素转成float类型

    11 dataMat.append(fltLine)12 returndataMat13

    14 #计算欧几里得距离

    15 defdistEclud(vecA, vecB):16 return sqrt(sum(power(vecA - vecB, 2))) #求两个向量之间的距离

    17

    18 #构建聚簇中心,取k个(此例中为4)随机质心

    19 defrandCent(dataSet, k):20 n = shape(dataSet)[1]21 centroids = mat(zeros((k,n))) #每个质心有n个坐标值,总共要k个质心

    22 for j inrange(n):23 minJ =min(dataSet[:,j])24 maxJ =max(dataSet[:,j])25 rangeJ = float(maxJ -minJ)26 centroids[:,j] = minJ + rangeJ * random.rand(k, 1)27 returncentroids28

    29 #k-means 聚类算法

    30 def kMeans(dataSet, k, distMeans =distEclud, createCent =randCent):31 m =shape(dataSet)[0]32 clusterAssment = mat(zeros((m,2))) #用于存放该样本属于哪类及质心距离

    33 #clusterAssment第一列存放该数据所属的中心点,第二列是该数据到中心点的距离

    34 centroids =createCent(dataSet, k)35 clusterChanged = True #用来判断聚类是否已经收敛

    36 whileclusterChanged:37 clusterChanged =False;38 for i in range(m): #把每一个数据点划分到离它最近的中心点

    39 minDist = inf; minIndex = -1;40 for j inrange(k):41 distJI =distMeans(centroids[j,:], dataSet[i,:])42 if distJI <43 mindist="distJI;" minindex="j">

    44 if clusterAssment[i,0] != minIndex: clusterChanged = True; #如果分配发生变化,则需要继续迭代

    45 clusterAssment[i,:] = minIndex,minDist**2 #并将第i个数据点的分配情况存入字典

    46 printcentroids47 for cent in range(k): #重新计算中心点

    48 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]] #去第一列等于cent的所有列

    49 centroids[cent,:] = mean(ptsInClust, axis = 0) #算出这些数据的中心点

    50 returncentroids, clusterAssment51 #--------------------测试----------------------------------------------------

    52 #用测试数据及测试kmeans算法

    53 datMat = mat(loadDataSet('testSet.txt'))54 myCentroids,clustAssing = kMeans(datMat,4)55 printmyCentroids56 print clustAssing

    运行结果:

    6、K-means算法补充

    K-means算法的缺点及改进方法

    (1)k值的选择是用户指定的,不同的k得到的结果会有挺大的不同,如下图所示,左边是k=3的结果,这个就太稀疏了,蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果,可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的:

    改进:

    对k的选择可以先用一些算法分析数据的分布,如重心和密度等,然后选择合适的k

    (2)对k个初始质心的选择比较敏感,容易陷入局部最小值。例如,我们上面的算法运行的时候,有可能会得到不同的结果,如下面这两种情况。K-means也是收敛了,只是收敛到了局部最小值:

    改进:

    有人提出了另一个成为二分k均值(bisecting k-means)算法,它对初始的k个质心的选择就不太敏感

    (3)存在局限性,如下面这种非球状的数据分布就搞不定了:

    (4)数据集比较大的时候,收敛会比较慢。

    43>
    展开全文
  • 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。

    层次聚类

    层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。随着个人手机和网络的普及,手机已经基本成为所有人必须持有的工具。根据手机信号再地理空间的覆盖情况结合时间序列的手机定位数据可以完整的还原人群的现实活动轨迹从而得到人口空间分布于活动联系的特征信息商圈是现代市场中的重要企业活动空间,商圈划分的目的之一是为了研究潜在的顾客分布,以制定适宜的商业对策。现有数据集business_circle.xls。样本具有以下几个特征:基站编号、工作日上班时间人均停留时间、凌晨人均停留时间、周末人均停留时间、日均人流量,要求根据以上维度指标,对数据集进行层次聚类,并找出潜在的顾客分布规律,同时要求打印输出样本的类别标签,并画出谱系聚类图。

    代码实现

    # 现有数据集circle.xls。样本具有以下几个特征:基站编号、工作日上班时间人均停留时间、凌晨人均停留时间、周末人均停留时间、日均人流量,
    # 要求根据以上维度指标,对数据集进行层次聚类,同时要求打印输出样本的类别标签,并画出谱系聚类图。
    import pandas as pd
    import scipy.cluster.hierarchy as sch
    from sklearn.cluster import AgglomerativeClustering
    from sklearn.preprocessing import MinMaxScaler
    from matplotlib import pyplot as plt
    # 读取数据
    data = pd.read_excel(r'circle.xls',index_col='基站编号')
    # print(data.head())
    df = MinMaxScaler().fit_transform(data)
    
    # 建立模型
    model = AgglomerativeClustering(n_clusters=3)
    model.fit(df)
    data['类别标签'] = model.labels_
    print(data.head())
    
    # 画图
    ss = sch.linkage(df,method='ward')
    sch.dendrogram(ss)
    plt.show()
    

    图形如下

    在这里插入图片描述

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

    万次阅读 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;输出如下,采用的是输入数据的索引

                                                                    


     

     

    展开全文
  • 聚类算法概述 聚类分析是根据样本数据之间的某种相似关系将数据集中的样本划分为多个通常不相交的子集的过程,每一个子集称为一个簇(cluster),每个簇对应一个潜在的类别。 按照数据之间的相似性,对数据集进行分组...
  • 1、kmeanskmeans, k-均值聚类算法,能够实现发现数据集的 k 个簇的算法,每个簇通过其质心来描述。kmeans步骤:(1)随机找 k 个点作为质心(种子);(2)计算其他点到这 k 个种子的距离,选择最近的那个作为该点的类别;...
  • AP近邻传播聚类算法原理Matlab实现 Affinity Propagation (AP)聚类是2007年在Science杂志上提出的一种新的聚类算法。它根据N个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度...
  • TraClus轨迹聚类算法原理java版实现

    千次阅读 热门讨论 2019-09-19 16:35:13
    traClus算法相比于其它的轨迹聚类算法的一大不同点是,该算法先把一个用户的轨迹分成了若干线段,然后把基于所有用户的轨迹生成的线段放到一个集合中进行聚类。 算法本身可以划分为三个部分,分别为: 1、用户轨迹...
  • k-means算法是聚类算法中最简单的算法之一。 k-means 算法将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值...
  • K-Means聚类算法原理及实现

    千次阅读 2016-10-26 11:54:49
    k-means 聚类算法原理:  1、从包含多个数据点的数据集 D 中随机取 k 个点,作为 k 个簇的各自的中心。  2、分别计算剩下的点到 k 个簇中心的相异度,将这些元素分别划归到相异度最低的簇。两个点之间的相异度大小...
  • kmeans聚类算法及matlab实现

    万次阅读 2015-11-12 19:25:10
    作为一个非常好用的聚类算法,kmeans的思想和实现都比较简单。kmeans的主要思想:把数据划分到各个区域(簇),使得数据与区域中心的距离之和最小。换个角度来说,kmeans算法把数据量化为聚类中心,其目标函数就是使...
  • Kmeans聚类算法详解

    万次阅读 多人点赞 2018-05-16 18:41:40
    摘要:本文通过图文详细介绍Kmeans聚类算法的原理和程序实现,以及如何选取类簇中心点。本文首先介绍利用该算法的原理理解,详细介绍基于MATLAB设计一个自定义的Kmeans函数过程,然后利用该函数对UCI的数据集进行...
  • 层次聚类算法的原理python实现

    万次阅读 2018-01-05 11:27:52
    层次聚类(Hierarchical Clustering)是一种聚类算法,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。
  • 本文完成程序测试数据集详细见:数据集链接 本文主要内容: 1.k-means解决的问题; 2.k-means原理介绍;...k-means算法属于无监督学习的一种聚类算法,其目的为:在不知数据所属类别类别数量的前提下,依据...
  • k-meansIsodata 聚类算法实现,用c++代码实现,输入数据为Iris,输出分类类结果
  •   k-means算法也称k均值算法,是一种常用的聚类算法聚类算法是研究最多、应用最广的一种无监督学习算法。   聚类试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个“簇”。通过这样的...
  • 层次聚类算法的原理及实现Hierarchical Clustering

    万次阅读 多人点赞 2016-12-07 21:41:48
    层次聚类算法的原理及实现Hierarchical Clustering 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的...
  • K-means 聚类算法及代码实现

    千次阅读 2018-12-02 18:33:06
    K-means 聚类算法及代码实现 十大数学科学经典算法(一) K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。 首先记录一下当python输出需要展示全部列或者行而不是省略号的时候用以下命令 ...
  • k-means聚类算法原理python3实现

    万次阅读 多人点赞 2018-08-09 11:01:17
    本文完成程序测试数据集详细见:https://github.com/HanXia001/k-means-python3- 本文主要内容:  1.k-means解决的问题;  2.k-means原理介绍;  3.k-means的简单实现。 1.k-means解决的问题  k-...
  • K-means聚类算法及python代码实现

    千次阅读 2019-05-29 11:50:51
    K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的) 1、概述 K-means算法是集简单和经典于一身的基于距离的聚类算法 采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。 ...
  • 模糊C均值聚类(FCM)算法是基于模糊理论的一种软聚类算法。相对于K-Means算法的硬聚类,FCM提供了更加灵活的聚类结果。在很多情况下,数据集中的对象不能划分成为明显分离的簇,这时使用K-Means为每一个对象指定一...
  • k-means 聚类算法原理: 1、从包含多个数据点的数据集 D 中随机取 k 个点,作为 k 个簇的各自的中心。 2、分别计算剩下的点到 k 个簇中心的相异度,将这些元素分别划归到相异度最低的簇。两个点之间的相异度大小...
  • 聚类算法是机器学习中的一大重要算法,也是我们掌握机器学习的必须算法,下面对聚类算法中的K-means算法做一个简单的描述: 一、概述 K-means算法属于聚类算法中的直接聚类算法。给定一个对象(或记录)的集合,将...
  • K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的)1、概述K-means算法是集简单和经典于一身的基于距离的聚类算法采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法...
  • 常用的聚类算法二.K-均值聚类算法1.k-均值算法的python实现1.1 导入数据集 一.聚类分析概述 聚类分析是无监督类机器学习算法中常用的一类,其目的是将数据划分成有意义或有用的组(也被称为簇)。组 内的对象相互...
  • K-Means聚类算法的原理及实现

    千次阅读 2017-09-28 20:59:34
    K-Means聚类算法的原理及实现【转】 【转】http://www.aboutyun.com/thread-18178-1-1.html 问题导读: 1、如何理解K-Means算法? 2、如何寻找K值初始质心? 3、如何应用K-Means算法处理数据? K-...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 602
精华内容 240
关键字:

聚类算法实现及数据