搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 独孤酱烘workspace > 机器学习(一)聚类算法

机器学习(一)聚类算法

独孤酱烘workspace 2019-04-05
举报

当前浏览器不支持播放音乐或语音,请在微信或其他浏览器中播放 机器学习(一)聚类算法

(A)python程序

(一)K-近邻(KNN)算法(是一种有监督学习)

1.K-近邻(KNN)算法概述

KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。

2.  例子

如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

机器学习(一)聚类算法

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

机器学习(一)聚类算法

3.算法流程

(1)准备数据,对数据进行预处理。

(2). 选用合适的数据结构存储训练数据和测试元组

(3). 设定参数,如k

(4).维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列

(5). 遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L 与优先级队列中的最大距离Lmax

(6). 进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L < Lmax,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列。

(7). 遍历完毕,计算优先级队列中k 个元组的多数类,并将其作为测试元组的类别。

(8). 测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k 值。

4.优点

(1).简单,易于理解,易于实现,无需估计参数,无需训练;

(2). 适合对稀有事件进行分类;

(3)特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。

5.缺点

      该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。可理解性差,无法给出像决策树那样的规则。

6.Python程序

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

运行结果:

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

(B)R语言算法

算法演示的数据预处理

机器学习(一)聚类算法

机器学习(一)聚类算法

数据预处理图像

机器学习(一)聚类算法



(二)K-均值(k-means)聚类(是一种无监督学习)

1.K-均值(k-means)聚类算法概述   

     k-means算法是一种简单的迭代型聚类算法,采用距离作为相似性指标,从而发现给定数据集中的K个类,且每个类的中心是根据类中所有值的均值得到,每个类用聚类中心来描述。对于给定的一个包含n个d维数据点的数据集X以及要分得的类别K,选取欧式距离作为相似度指标,聚类目标是使得各类的聚类平方和最小,即最小化:

                机器学习(一)聚类算法

结合最小二乘法和拉格朗日原理,聚类中心为对应类别中各数据点的平均值,同时为了使得算法收敛,在迭代过程中,应使最终的聚类中心尽可能的不变。

2.算法流程

K-means是一个反复迭代的过程,算法分为四个步骤:

(1) 选取数据空间中的K个对象作为初始中心,每个对象代表一个聚类中心;

(2) 对于样本中的数据对象,根据它们与这些聚类中心的欧氏距离,按距离最近的准则将它们分到距离它们最近的聚类中心(最相似)所对应的类;

(3) 更新聚类中心:将每个类别中所有对象所对应的均值作为该类别的聚类中心,计算目标函数的值;

(4) 判断聚类中心和目标函数的值是否发生改变,若不变,则输出结果,若改变,则返回2)。

3.K-均值算法在R语言中的核心函数——kmeans函数

(1)来源:stats包

(2)基本格式:

kmeans(x,centers,iter.max=10,nstart=1,algorithm=c("Hartigan-Wong","Lloyd","For-gy","MacQueen"))

其中x为进行聚类分析的数据集;centers为预设的类别数k;iter.max为迭代的最大值,且默认值为10;nstart为选择随机起始中心点的次数,默认为1;而参数algorithm则提供了四种算法选择,默认值为Hartigan-Wong算法

(3)K-means的迭代算法

(A)Lloyd算法

    Lloyd算法也可以称作Forgy或者Lloyd-Forgy,是最为经典简单的

K-means迭代算法,

(a)K-means迭代算法步骤:

1. 随机选取K个点作为初始的中心点

2. 计算每个点与K个中心点的K个距离(假如有N个点,就有N*K个距离值)

3. 分配剩下的点到距离其最近的中心点的类中

4更新聚类中心:将每个类别中所有对象所对应的均值作为该类别的聚类中心,计算目标函数的值;

5.重复步骤2和步骤3,步骤4

6 直到达到收敛或者达到某个停止阈值(如最大计算时间)

(b)用公式解释如下:

  1. 把所有的点分配到K个类的系数r,属于第k个类的记为1,否则为0

机器学习(一)聚类算法

2. 由上可知第k个类中的样本数量

机器学习(一)聚类算法

3. 目标是最小化损失函数J

机器学习(一)聚类算法

4. 计算每个点到中心点的距离,分配r的系数

机器学习(一)聚类算法

5. 重新计算每个类的中心点

机器学习(一)聚类算法

重复4和5指导收敛或者达到某个阈值

(c)Lloyd算法的缺点:聚类产生的类别经常是不平衡的,就是说不同类中样本的数量差异很大。这点会经常被忽略到,然而很多时候需要我们聚类出来是平衡的,例如对手写数字图像进行聚类的时候,我们有理由相信10个数字出现的频率是一样的,所以希望聚类后每个类中含有样本数量是相同的。像上述的手写数字图像聚类这个例子中 ,为获得更高的分类准确率,则需要平衡的聚类结果。另外,Lloyd算法是一个批量更新算法,因此会学习速度会相对较快。

(B)MacQueen算法

MacQueen是一种在线更新的算法,只需要一次迭代,具体步骤如下:

1. 选取头K个点作为K个类的中心点

2. 选取下一个点计算与K个中心点的距离,选取距离最小的分配到该类中

3. 更新该类的中心点

4. 重复2,3直到所有的点分配完毕,达到收敛

MacQueen相对于Lloyd而言,总体的训练时间需要更久。

(C)Hartigan-Wong算法

     为了改进上述算法的不平衡问题,我们可以考虑用Hartigan-Wong算法,它也是一种在线更新的算法,具体如下:

1. 随机分配所有的点到K个类上,计算K个类的中心

2. 随机选择一个点,把它移出所属类

3. 重新计算有变化的类的中心

4. 把移出的点重新分配到其距离最近的中心点的类上

5. 循环所有的点,重复2,3,4

6. 进行第二次循环,重复2,3,4,5

7. 直到达到收敛或者某个停止阈值

其主要的不同点是在分配到K个类别的过程中,公式如下:

机器学习(一)聚类算法

值得注意的是因为Hartigan-Wong算法多加了一个乘法项

机器学习(一)聚类算法

    因此算法更倾向于把样本分配给样本数量较少的类。但是这个乘法项并不是为了平衡而设计的,而是在把移除的点加入合适的类中而发生的类大小变化。

   Hartigan-Wong算法相对于Lloyd来说是一种在线更新的算法,一般来讲可以获得更低的代价函数值,但是同样地会更慢。Lloyd的批量更新算法速度更快,效率更高。

4.R语言程序处理

> fit_km1=kmeans(countries[,-1],center=3)

#用kmeans算法对countries数据集进行聚类

> print(fit_km1)#输出聚类结果

K-means clustering with 3 clusters of sizes 2, 41, 27

Cluster means:

     birth     death

1 55.95000 29.350000

2 20.26098  9.112195

3 40.50741 10.811111


Clustering vector:

       ALGERIA          CONGO          EGYPT          GHANA     IVORYCOAST 

             3              3              3              1              1 

      MALAGASY        MOROCCO        TUNISIA       CAMBODIA         CEYLON 

             3              3              3              3              3 

         CHINA         TAIWAN       HONGKONG          INDIA      INDONESIA 

             3              3              3              2              2 

          IRAQ         FRANCE          JAPAN         JORDAN          KOREA 

             2              2              2              3              2 

      MALAYSIA       MONGOLIA   PHILLLIPINES          SYRIA       THAILAND 

             3              3              2              2              3 

       VIETNAM         CANADA      COSTARICA     DOMINICANR      GUATEMALA 

             2              2              3              3              3 

      HONDURAS         MEXICO      NICARAGUA         PANAMA   UNITEDSTATES 

             3              3              3              3              2 

     ARGENTINA        BOLIVIA         BRAZIL          CHILE       COLOMBIA 

             2              2              3              3              3 

       ECUADOR           PERU        URUGUAY      VENEZUELA        AUSTRIA 

             3              2              2              3              2 

       BElGIUM        BRITAIN       BULGARIA CZECHOSLOVAKIA        DENMARK 

             2              2              2              2              2 

       FINLAND        FRANCES      E.GERMANY      W.GERMANY         GREECE 

             2              2              2              2              2 

       HUNGARY        IRELAND          ITALY    NETHERLANDS         NORWAY 

             2              2              2              2              2 

        POLAND       PORTUGAL        ROMANIA          SPAIN         SWEDEN 

             2              2              2              2              2 

   SWITZERLAND       U.S.S.R.     YUGOSLAVIA      AUSTRALIA     NEWZEALAND 

             2              2              2              2              2 


Within cluster sum of squares by cluster:

[1]   28.1700  883.5215 1115.8652

 (between_SS / total_SS =  81.5 %)


Available components:


[1] "cluster"      "centers"      "totss"        "withinss"    

[5] "tot.withinss" "betweenss"    "size"         "iter"        

[9] "ifault"      

> fit_km1$centers#各类别中心点坐标

     birth     death

1 55.95000 29.350000

2 20.26098  9.112195

3 40.50741 10.811111

> fit_km1$totss#聚类的总平方和

[1] 10976.7

> fit_km1$tot.withinss#聚类的组间平方和

[1] 2027.557

> fit_km1$betweenss#聚类的组间平方和

[1] 8949.14

> plot(countries[,-1],pch=(fit_km1$cluster-1))

#画出聚类结果,不同类别用不同形状表示

> points(fit_km1$centers,pch=8)

#各类别的中心点并用星号表示

#对各个中心点添加标注

> legend(fit_km1$centers[1,1],fit_km1$centers[1,2],"Center_1",bty="n",xjust=1,yjust=0,cex=0.8)

> legend(fit_km1$centers[2,1],fit_km1$centers[2,2],"Center_2",bty="n",xjust=0,yjust=0,cex=0.8)

> legend(fit_km1$centers[3,1],fit_km1$centers[3,2],"Center_3",bty="n",xjust=0.5,yjust=0,cex=0.8)

机器学习(一)聚类算法

> #显示不同类别数时的聚类优度

> result=rep(0:69)

> for(k in 1:69)

+ {

+ fit_km=kmeans(countries[,-1],center=k)

+ result[k]=fit_km$betweenss/fit_km$totss

+ }

> round(result,2)

 [1]  0.00  0.72  0.81  0.85  0.86  0.87  0.93  0.95  0.94  0.96  0.96  0.96

[13]  0.97  0.97  0.97  0.98  0.97  0.98  0.98  0.98  0.98  0.99  0.98  0.98

[25]  0.99  0.99  0.99  0.99  0.99  0.99  0.99  0.99  0.99  0.99  1.00  0.99

[37]  0.99  1.00  0.99  0.99  1.00  0.99  1.00  0.99  1.00  1.00  1.00  1.00

[49]  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00

[61]  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00  1.00 69.00

> plot(1:69,result[1:69],type="b",main="Choosing the Optimal Number of Cluster",xlab="number of cluster:1 to 69",ylab="betweenss/totss")

> points(10,result[10],pch=16)

> legend(10,result[10],paste("(10,",sprintf("%.1f",result[10]*100),")",sep=""),bty="n",xjust=0.3,cex=0.8)

> #聚类类别为10时的聚类结果

> fit_km2=kmeans(countries[,-1],center=10)

> #与China同组的聚类结果

> cluster_CHINA=fit_km2$cluster[which(countries$country=="CHINA")]

> which(fit_km2$cluster==cluster_CHINA)

   ALGERIA      CONGO     CEYLON      CHINA     TAIWAN   HONGKONG   MALAYSIA 

         1          2         10         11         12         13         21 

  MONGOLIA   THAILAND DOMINICANR      CHILE 

        22         25         29         39 

机器学习(一)聚类算法

(三)K-中心点聚类

1.K-中心点聚类的算法概述

       K-中心点算法也是一种常用的聚类算法,K-中心点聚类的基本思想和K-Means的思想相同,实质上是对K-means算法的优化和改进。在K-means中,异常数据对其的算法过程会有较大的影响。在K-means算法执行过程中,可以通过随机的方式选择初始质心,也只有初始时通过随机方式产生的质心才是实际需要聚簇集合的中心点,而后面通过不断迭代产生的新的质心很可能并不是在聚簇中的点。如果某些异常点距离质心相对较大时,很可能导致重新计算得到的质心偏离了聚簇的真实中心。

2.算法流程

(1)确定聚类的个数K;

(2)在所有数据集合中选择K个点作为各个聚簇的中心点。

(3)计算其余所有点到K个中心点的距离,并把每个点到K个中心点最短的聚簇作为自己所属的聚簇。

(4)在每个聚簇中按照顺序依次选取点,计算该点到当前聚簇中所有点距离之和,最终距离之后最小的点,则视为新的中心点。

(5)重复(2)(3)步骤,直到各个聚簇的中心点不再改变。

3.K-中心点算法在R语言中的核心函数——pam函数

(1)来源:cluster包

(2)基本格式:

pam(x,k,diss=inherits(x,"dist"),metric="euclidean",medoids=NULL,

stand=FALSE,cluster.only=FALSE,do.swap=TRUE,keep.diss=!diss&&

!cluster.only&&n<100,keep.data=!diss&&!cluster.only,pamonce=

FALSE,trace.lev=0)

其中x和k分别表示待处理数据及类别数;metric参数用于选择样本点间距离测算的方式,可供选择的有“euclidean”与“manhattan”;medoids默认取NULL,即由软件选择初始中心点样本,也可认为设定一个k维向量来指定初始点;stand用于选择对数据进行聚类前是否需要进行标准化;cluster.only用于选择是否仅获取各样本所归属的类别(cluster vector)这一项聚类的结果,若选择TRUE,则聚类过程效率更高;keep.data选择是否在聚类结果中保留数据集

4.R语言程序处理

> library(cluster)#加载cluster软件包

> fit_pam=pam(countries[,-1],3)#用k-Medoids算法进行聚类

> print(fit_pam)#输出聚类结果

Medoids:

            ID birth death

DOMINICANR  29  33.0   8.4

COLOMBIA    40  44.0  11.7

SWITZERLAND 66  18.9   9.6

Clustering vector:

       ALGERIA          CONGO          EGYPT          GHANA     IVORYCOAST 

             1              1              2              2              2 

      MALAGASY        MOROCCO        TUNISIA       CAMBODIA         CEYLON 

             2              2              2              2              1 

         CHINA         TAIWAN       HONGKONG          INDIA      INDONESIA 

             1              1              1              3              1 

          IRAQ         FRANCE          JAPAN         JORDAN          KOREA 

             3              3              3              2              3 

      MALAYSIA       MONGOLIA   PHILLLIPINES          SYRIA       THAILAND 

             1              2              1              1              1 

       VIETNAM         CANADA      COSTARICA     DOMINICANR      GUATEMALA 

             3              3              2              1              2 

      HONDURAS         MEXICO      NICARAGUA         PANAMA   UNITEDSTATES 

             2              2              2              2              3 

     ARGENTINA        BOLIVIA         BRAZIL          CHILE       COLOMBIA 

             3              3              2              1              2 

       ECUADOR           PERU        URUGUAY      VENEZUELA        AUSTRIA 

             2              1              3              2              3 

       BElGIUM        BRITAIN       BULGARIA CZECHOSLOVAKIA        DENMARK 

             3              3              3              3              3 

       FINLAND        FRANCES      E.GERMANY      W.GERMANY         GREECE 

             3              3              3              3              3 

       HUNGARY        IRELAND          ITALY    NETHERLANDS         NORWAY 

             3              3              3              3              3 

        POLAND       PORTUGAL        ROMANIA          SPAIN         SWEDEN 

             3              3              3              3              3 

   SWITZERLAND       U.S.S.R.     YUGOSLAVIA      AUSTRALIA     NEWZEALAND 

             3              3              3              3              3 

Objective function:

   build     swap 

4.685420 4.384723 


Available components:

 [1] "medoids"    "id.med"     "clustering" "objective"  "isolation" 

 [6] "clusinfo"   "silinfo"    "diss"       "call"       "data"      

> head(fit_pam$data)#回看原来的数据集

           birth death

ALGERIA     36.4  14.6

CONGO       37.3   8.0

EGYPT       42.1  15.3

GHANA       55.8  25.6

IVORYCOAST  56.1  33.1

MALAGASY    41.8  15.8

> fit_pam$call#回看产生该聚类结果的函数设置

pam(x = countries[, -1], k = 3)

> fit_pam1=pam(countries[,-1],3,keep.data=FALSE)#更改keep.data参数的值

> fit_pam1$data

NULL

> fit_pam2=pam(countries[,-1],3,cluster.only=TRUE)#更改cluster.only参数的值

> print(fit_pam2)#输出聚类结果

       ALGERIA          CONGO          EGYPT          GHANA     IVORYCOAST 

             1              1              2              2              2 

      MALAGASY        MOROCCO        TUNISIA       CAMBODIA         CEYLON 

             2              2              2              2              1 

         CHINA         TAIWAN       HONGKONG          INDIA      INDONESIA 

             1              1              1              3              1 

          IRAQ         FRANCE          JAPAN         JORDAN          KOREA 

             3              3              3              2              3 

      MALAYSIA       MONGOLIA   PHILLLIPINES          SYRIA       THAILAND 

             1              2              1              1              1 

       VIETNAM         CANADA      COSTARICA     DOMINICANR      GUATEMALA 

             3              3              2              1              2 

      HONDURAS         MEXICO      NICARAGUA         PANAMA   UNITEDSTATES 

             2              2              2              2              3 

     ARGENTINA        BOLIVIA         BRAZIL          CHILE       COLOMBIA 

             3              3              2              1              2 

       ECUADOR           PERU        URUGUAY      VENEZUELA        AUSTRIA 

             2              1              3              2              3 

       BElGIUM        BRITAIN       BULGARIA CZECHOSLOVAKIA        DENMARK 

             3              3              3              3              3 

       FINLAND        FRANCES      E.GERMANY      W.GERMANY         GREECE 

             3              3              3              3              3 

       HUNGARY        IRELAND          ITALY    NETHERLANDS         NORWAY 

             3              3              3              3              3 

        POLAND       PORTUGAL        ROMANIA          SPAIN         SWEDEN 

             3              3              3              3              3 

   SWITZERLAND       U.S.S.R.     YUGOSLAVIA      AUSTRALIA     NEWZEALAND 

             3              3              3              3              3 

> which(fit_km1$cluster!=fit_pam$cluster)#不一致聚类结果的显示

     ALGERIA        CONGO        EGYPT        GHANA   IVORYCOAST 

           1            2            3            4            5 

    MALAGASY      MOROCCO      TUNISIA     CAMBODIA       CEYLON 

           6            7            8            9           10 

       CHINA       TAIWAN     HONGKONG    INDONESIA       JORDAN 

          11           12           13           15           19 

    MALAYSIA PHILLLIPINES        SYRIA     THAILAND    COSTARICA 

          21           23           24           25           28 

  DOMINICANR    GUATEMALA     HONDURAS       MEXICO    NICARAGUA 

          29           30           31           32           33 

      BRAZIL        CHILE     COLOMBIA      ECUADOR         PERU 

          38           39           40           41           42 

   VENEZUELA 

          44 

机器学习(一)聚类算法

(四)系谱聚类(R语言的聚类算法)

1.系谱聚类的算法概述

系谱聚类的主要特点是不需要事先设定类别数K,它在每次迭代过程中仅将距离最近的两个样本或簇聚为一类,其过程自然得到k=1至k=n(n为待分类样本总数)个类别的聚类结果。

2.系谱聚类算法在R语言中的用到函数——hclust、cutree及rect.hclust函数

(1)来源:stats包

(2)基本格式:

hclust(d,method="complete",members=NULL)

其中,d为待处理数据集样本间的距离矩阵,可用dist()函数计算得到;method参数用于选择聚类的具体算法,可供选择的有ward,single及complete等7种,默认选择complete方法;参数members用于指出每个待聚类样本点/簇是由几个单样本构成的,如共有5个待聚类样本点/簇,当我们设置members=rep(2,5)则表明每个样本点/簇中分别是有2个单样本聚类的结果,该参数默认值为NULL,表示每个样本点本身即为单样本。

而cutree()函数则可以对hclust()函数的聚类结果进行剪枝,即选择输出指定类别数的系谱聚类结果。其格式为:

cutree(tree,k=NULL,h=NULL)

其中,tree为hclust()的聚类结果,参数k与h用于控制选择输出的结果,k为指定类别数,h为树高度

函数rect.hclust()可以在plot()形成的系谱图中将指定类别中的样本分支用方框表示出来,十分有助于直观分析聚类结果。其基本格式为:

rect.hclust(tree,k=NULL,which=NULL,x=NULL,h=NULL,border=2,

cluster=NULL)

3.R语言程序处理

> fit_hc=hclust(dist(countries[,-1]))#利用dist计算距离矩阵后进行系谱聚类

> print(fit_hc)#显示聚类的相关信息


Call:

hclust(d = dist(countries[, -1]))


Cluster method   : complete 

Distance         : euclidean 

Number of objects: 70 


> plot(fit_hc)#对聚类结果做系谱图

 

机器学习(一)聚类算法

> group_k3=cutree(fit_hc,k=3)#利用剪枝函数cutree()中的参数k控制输出3类别的系谱聚类结果

> group_k3#显示结果

       ALGERIA          CONGO          EGYPT          GHANA     IVORYCOAST 

             1              1              1              2              2 

      MALAGASY        MOROCCO        TUNISIA       CAMBODIA         CEYLON 

             1              1              1              1              1 

         CHINA         TAIWAN       HONGKONG          INDIA      INDONESIA 

             1              1              1              3              3 

          IRAQ         FRANCE          JAPAN         JORDAN          KOREA 

             3              3              3              1              3 

      MALAYSIA       MONGOLIA   PHILLLIPINES          SYRIA       THAILAND 

             1              1              3              3              1 

       VIETNAM         CANADA      COSTARICA     DOMINICANR      GUATEMALA 

             3              3              1              1              1 

      HONDURAS         MEXICO      NICARAGUA         PANAMA   UNITEDSTATES 

             1              1              1              1              3 

     ARGENTINA        BOLIVIA         BRAZIL          CHILE       COLOMBIA 

             3              3              1              1              1 

       ECUADOR           PERU        URUGUAY      VENEZUELA        AUSTRIA 

             1              3              3              1              3 

       BElGIUM        BRITAIN       BULGARIA CZECHOSLOVAKIA        DENMARK 

             3              3              3              3              3 

       FINLAND        FRANCES      E.GERMANY      W.GERMANY         GREECE 

             3              3              3              3              3 

       HUNGARY        IRELAND          ITALY    NETHERLANDS         NORWAY 

             3              3              3              3              3 

        POLAND       PORTUGAL        ROMANIA          SPAIN         SWEDEN 

             3              3              3              3              3 

   SWITZERLAND       U.S.S.R.     YUGOSLAVIA      AUSTRALIA     NEWZEALAND 

             3              3              3              3              3 

> table(group_k3)#以表格形式总结聚类结果

group_k3

 1  2  3 

27  2 41 

> group_h18=cutree(fit_hc,h=18)

> group_h18#显示结果

       ALGERIA          CONGO          EGYPT          GHANA     IVORYCOAST 

             1              1              2              3              3 

      MALAGASY        MOROCCO        TUNISIA       CAMBODIA         CEYLON 

             2              2              2              2              1 

         CHINA         TAIWAN       HONGKONG          INDIA      INDONESIA 

             1              1              1              4              4 

          IRAQ         FRANCE          JAPAN         JORDAN          KOREA 

             4              4              4              2              4 

      MALAYSIA       MONGOLIA   PHILLLIPINES          SYRIA       THAILAND 

             1              2              4              4              1 

       VIETNAM         CANADA      COSTARICA     DOMINICANR      GUATEMALA 

             4              4              2              1              2 

      HONDURAS         MEXICO      NICARAGUA         PANAMA   UNITEDSTATES 

             2              2              2              2              4 

     ARGENTINA        BOLIVIA         BRAZIL          CHILE       COLOMBIA 

             4              4              2              1              2 

       ECUADOR           PERU        URUGUAY      VENEZUELA        AUSTRIA 

             2              4              4              2              4 

       BElGIUM        BRITAIN       BULGARIA CZECHOSLOVAKIA        DENMARK 

             4              4              4              4              4 

       FINLAND        FRANCES      E.GERMANY      W.GERMANY         GREECE 

             4              4              4              4              4 

       HUNGARY        IRELAND          ITALY    NETHERLANDS         NORWAY 

             4              4              4              4              4 

        POLAND       PORTUGAL        ROMANIA          SPAIN         SWEDEN 

             4              4              4              4              4 

   SWITZERLAND       U.S.S.R.     YUGOSLAVIA      AUSTRALIA     NEWZEALAND 

             4              4              4              4              4 

> table(group_h18)#以表格形式总结聚类结果

group_h18

 1  2  3  4 

10 17  2 41 

>sapply(unique(group_k3),function(g) countries$country[group_k3==g])

[[1]]

 [1] ALGERIA    CONGO      EGYPT      MALAGASY   MOROCCO    TUNISIA   

 [7] CAMBODIA   CEYLON     CHINA      TAIWAN     HONGKONG   JORDAN    

[13] MALAYSIA   MONGOLIA   THAILAND   COSTARICA  DOMINICANR GUATEMALA 

[19] HONDURAS   MEXICO     NICARAGUA  PANAMA     BRAZIL     CHILE     

[25] COLOMBIA   ECUADOR    VENEZUELA 

70 Levels: ALGERIA ARGENTINA AUSTRALIA AUSTRIA BElGIUM BOLIVIA ... YUGOSLAVIA


[[2]]

[1] GHANA      IVORYCOAST

70 Levels: ALGERIA ARGENTINA AUSTRALIA AUSTRIA BElGIUM BOLIVIA ... YUGOSLAVIA


[[3]]

 [1] INDIA          INDONESIA      IRAQ           FRANCE        

 [5] JAPAN          KOREA          PHILLLIPINES   SYRIA         

 [9] VIETNAM        CANADA         UNITEDSTATES   ARGENTINA     

[13] BOLIVIA        PERU           URUGUAY        AUSTRIA       

[17] BElGIUM        BRITAIN        BULGARIA       CZECHOSLOVAKIA

[21] DENMARK        FINLAND        FRANCES        E.GERMANY     

[25] W.GERMANY      GREECE         HUNGARY        IRELAND       

[29] ITALY          NETHERLANDS    NORWAY         POLAND        

[33] PORTUGAL       ROMANIA        SPAIN          SWEDEN        

[37] SWITZERLAND    U.S.S.R.       YUGOSLAVIA     AUSTRALIA     

[41] NEWZEALAND    

70 Levels: ALGERIA ARGENTINA AUSTRALIA AUSTRIA BElGIUM BOLIVIA ... YUGOSLAVIA

> plot(fit_hc)#分类结果画图

> rect.hclust(fit_hc,k=4,border="light grey")#用浅灰色矩形框出4分类的聚类结果

机器学习(一)聚类算法

     

>rect.hclust(fit_hc,k=3,border="dark grey")#用深灰色矩形框出3分类的聚类结果


机器学习(一)聚类算法

 

> rect.hclust(fit_hc,k=7,which=c(2,6),border="dark grey")#用深灰色矩形框出7分类第2类和第6类的聚类结果


机器学习(一)聚类算法


(五)密度聚类

1.密度聚类的算法概述(R语言的聚类算法)

      基于密度的聚类算法主要的目标是寻找被低密度区域分离的高密度区域。与基于距离的聚类算法不同的是,基于距离的聚类算法的聚类结果是球状的簇,而基于密度的聚类算法可以发现任意形状的聚类,这对于带有噪音点的数据起着重要的作用。

2.DBSCAN算法的原理

(1)基本概念

      DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一种典型的基于密度的聚类算法,在DBSCAN算法中将数据点分为一下三类:

核心点:在半径Eps内含有超过MinPts数目的点

边界点:在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内

噪音点:既不是核心点也不是边界点的点

在这里有两个量,一个是半径Eps,另一个是指定的数目MinPts。

 (2)一些其他的概念

 (a)Eps邻域:简单来讲就是与点的距离小于等于Eps的所有的点的集合。

 (b)直接密度可达:如果在核心对象的Eps邻域内,则称对象从对象出发是直接密度可达的。

 (c)密度可达:对于对象链机器学习(一)聚类算法机器学习(一)聚类算法是从机器学习(一)聚类算法关于Eps和MinPts直接密度可达的,则对象机器学习(一)聚类算法是从对象机器学习(一)聚类算法关于Eps和MinPts密度可达的。

(3)算法流程

机器学习(一)聚类算法

3.密度聚类的DBSCAN算法在R语言中的用到函数——dbscan函数

(1)来源:fpc包

(2)基本格式:

dbscan(data,eps,MinPts=5,scale=FALSE,method=c("hybrid","raw",

"dist"),seeds=TRUE,showplot=FALSE,countmode=NULL)

其中,data为待聚类数据集或距离矩阵;eps为考察每一样本点是否满足密度要求时,所选定考察邻域的半径;MinPts为密度阈值,当考察点eps邻域内的样本点数大于等于MinPts时,该点才被认为是核心对象,否则为边缘点;scale用于选择是否在聚类前先对数据集进行标准化;method参数用于选择如何看待data,具体的,“hybrid”表示data为距离矩阵,“raw”表示data为原始数据集,且不计算其距离矩阵,“dist”也将data视为原始数据集,但计算局部聚类矩阵;showplot用于选择是否输出聚类结果的示意图,取值为0,1,2,分别表示不绘图,每次迭代都有绘图,仅对子迭代过程绘图。

4.R语言程序处理

> library(fpc)#加载fpc软件包

> ds1=dbscan(countries[,-1],eps=1,MinPts=5)#取半径参数eps为1,密度阈值MinPts为5

> ds2=dbscan(countries[,-1],eps=4,MinPts=5)#取半径参数eps为4,密度阈值MinPts为5

> ds3=dbscan(countries[,-1],eps=4,MinPts=2)#取半径参数eps为4,密度阈值MinPts为2

> ds4=dbscan(countries[,-1],eps=8,MinPts=2)#取半径参数eps为8,密度阈值MinPts为2

> ds1;ds2;ds3;ds4#显示聚类结果

dbscan Pts=70 MinPts=5 eps=1

        0 1

border 61 3

seed    0 6

total  61 9

dbscan Pts=70 MinPts=5 eps=4

       0  1  2

border 5  7  0

seed   0 18 40

total  5 25 40

dbscan Pts=70 MinPts=2 eps=4

       0  1 2  3

border 3  0 0  0

seed   0 25 2 40

total  3 25 2 40

dbscan Pts=70 MinPts=2 eps=8

       1 2

seed  68 2

total 68 2

> par(mfcol=c(2,2))#设置4张图按照2行2列摆放的空白位置

> plot(ds1,countries[,-1],main="1: MinPts=5,eps=1")#绘制MinPts=5,eps=1时的聚类结果

> plot(ds3,countries[,-1],main="3: MinPts=2,eps=4")#绘制MinPts=2,eps=4时的聚类结果

> plot(ds2,countries[,-1],main="2: MinPts=5,eps=4")#绘制MinPts=5,eps=4时的聚类结果

> plot(ds4,countries[,-1],main="4: MinPts=2,eps=8")#绘制MinPts=2,eps=8时的聚类结果

机器学习(一)聚类算法

> d=dist(countries[,-1])#计算样本点距离矩阵

> max(d);min(d)#计算样本间距离的最大值,最小值

[1] 49.56259

[1] 0.2236068

> library(ggplot2)

> interval=cut_interval(d,30)#对样本间的距离进行分段处理,取中位数30

> table(interval)#展示数据分段结果

interval

[0.224,1.87]  (1.87,3.51]  (3.51,5.16]   (5.16,6.8]   (6.8,8.45] 

          85          165          248          208          167 

 (8.45,10.1]  (10.1,11.7]  (11.7,13.4]    (13.4,15]    (15,16.7] 

         130          152          102           94          112 

 (16.7,18.3]    (18.3,20]    (20,21.6]  (21.6,23.2]  (23.2,24.9] 

         109           95          107           99          106 

 (24.9,26.5]  (26.5,28.2]  (28.2,29.8]  (29.8,31.5]  (31.5,33.1] 

         106           85           78           39           31 

 (33.1,34.8]  (34.8,36.4]  (36.4,38.1]  (38.1,39.7]  (39.7,41.3] 

          12            9            8           12           13 

   (41.3,43]    (43,44.6]  (44.6,46.3]  (46.3,47.9]  (47.9,49.6] 

          14           14            8            5            2 


> which.max(table(interval))#找出所含样本点最多的区间

(3.51,5.16] 

          3 

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

(六)期望最大化聚类

1. 期望最大化聚类的算法概述(R语言的聚类算法)

     它将数据集看作一个含有隐性变量的概率模型,并以实现模型最优化,即获取与数据本身性质最契合的聚类方式为目的,通过”反复估计”模型参数找到最优解,同时给出相应的最优类别k.而”反复估计”的过程即是EM算法的精华所在,这一过程由E-step(Expectation)和M-step(Maximization)两个步骤交替进行来实现。 

2.EM算法简介

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法


3.期望最大化聚类算法在R语言中用到的函数——Mclust,mclustBIC,mclust2Dplot及densityMclust函数

(1)来源:mclust包

(2)基本格式:

Mclust(data,G=NULL,modelNames=NULL,prior=NULL,

control=emControl(),initialization=NULL,warn=FALSE,...)

其中data用于放置待处理数据集;G为预设类别数,默认值为1至9,即由软件根据BIC的值在1至9中选择最优值;modelNames用于设定模型类别,该参数和G一样也可由函数自动选取最优值

mclustBIC()函数的参数设置与Mclust基本一致,用于获取数据集所对应的参数化高斯混合模型的BIC值,而BIC值的作用即是评价模型的优劣,BIC值越高模型越优。mclust2Dplot()可根据EM算法所所生成的参数对二维数据制图。而densityMclust()函数利用Mclust()的聚类结果对数据集中的每个样本点进行密度估计。

4.R语言程序处理

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法

机器学习(一)聚类算法机器学习(一)聚类算法

机器学习(一)聚类算法


机器学习(一)聚类算法

机器学习(一)聚类算法


机器学习(一)聚类算法


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《机器学习(一)聚类算法》的版权归原作者「独孤酱烘workspace」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注独孤酱烘workspace微信公众号

独孤酱烘workspace微信公众号:LJF1998KOBE24CR7

独孤酱烘workspace

手机扫描上方二维码即可关注独孤酱烘workspace微信公众号

独孤酱烘workspace最新文章

精品公众号随机推荐

举报