Press "Enter" to skip to content

聚类算法-K-means、DBSCAN

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

1、实验目的

 

 

掌握实验对比分析K-means和DBSCAN聚类算法的原理;

 

对整个实验过程进行编码实现。

 

 

2、实验步骤

 

1、按照算法的原理设计两个算法的执行过程。

 

两个算法的都是聚类算法,KMeans是通过计算所有的节点和聚簇中心的距离来不断的更新当前的中心节点位置,直到当前的聚簇中心达到最优(也就是在当前的选择范围之内不会再发生变化)。DBSCAN是一个比较有代表性的基于密度的聚类算法,与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现任意形状的聚类。

 

由于数据集本身具有3类的标签分类,因此KMeans的聚簇中心就选为3个初始化,而且进行随机化,这样可能会造成聚类不充分,但是可以通过多次聚类的降低这样的可能性。

 

DBSCAN是基于密度计算的,他的邻域阈值和分类的支持数这些基础数据不好确定,因此采用随机递增的方式来进行测试比对,选择其中最好的参数作为最终的比对参数,邻域范围为0.5、核心节点支持数为10个。

 

2、加载iris数据集并进行数据的预期展示。

 

iris数据集一共有150条数据,其中4列属性列作为分类的条件,划分类别为3类,先将最初的标签样本进行展示,这样就可以在后面的两个算法完成聚类之后进行分析比对。

 

3、两个算法分别对样本进行分类。

 

将数据集全部送入两个算法进行聚类,会得到具体每个样本的预测标签,这个时候按照对应的属性进行标签打印,并且和原本的正确标签进行比对统计聚类出错的样本数量,这个指标有助于我们后面对比两个算法正确性和情况分析。

 

4、将算法最终的比对数据交由图形进行展示。

 

主要展示iris的三种标签聚类结果,以及聚类错误的样本情况,可视化分析更加贴近人们的思考。通过降维使用第二列和第三列属性作为平面的坐标来进行数据的展示。

 

2.1、算法原理

 

1、KMeans算法原理

 

预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。

 

2、DBSCAN算法原理

 

算法的聚类过程就是根据核心点来推导出最大密度相连的样本集合,首先随机寻找一个核心样本点,按照minPoiints和eps来推导其密度相连的点,赋予一个cluser编号,然后再选择一个没有赋予类别的核心样本点,开始推导其密度相连的样本结合,一直迭代到所有的核心样本点都有对应的类别为止。相比kmeans算法,DBSCAN算法不需要事先指定聚类的类别数目K,而且适用的范围更广泛,可以对任意形状的数据进行聚类,同时还可以发现异常值点。

 

2.2 算法步骤

 

1、KMeans算法步骤

 

第一步设置参数k,k的含义为将数据聚合成几类。

 

第二步从数据当中,随机的选择(k)个点,成为聚类初始中心点。

 

第三步计算所有其他点到(k)个点的距离, 然后找出离每个数据点最近的中心点, 将该点划分到这个中心点所代表的的簇当中去。

 

第四步重新计算三个簇的质心,作为下一次聚类的中心点。

 

重复以上步骤直至聚簇中心不再变化或者是达到了最大的迭代次数。

 

2、DBSCAN算法步骤

 

第一步确定半径和核心节点数两个参数。

 

第二步从样本集中抽出一个未处理的点。

 

第三步如果抽出来的点是核心点则继续寻找密度相连的点形成簇。

 

第四步如果抽出来的点不是核心点则进行下一个点的寻找判定。

 

重复上述步骤直到所有的节点都被划分。

 

2.3 程序流程图

 

 

3、实验结果分析(附实验过程结果截图)

 

单纯的从实验结果来看,KMeans的聚类结果优于DBSCAN的聚类结果,但是不排除是参数选择不正确而导致的差异,因为我们预先就知道需要进行聚类的数量的,KMeans的中心点数量可以直接进行指定,也就是意味着很有可能在一次结果中就能达到很好的聚类结果,在多次的随机中心的初始化过程中都能达到相对较好的一个聚类结果。DBSCAN的两个参数在多次的变化中最终选择了0.5和10这两个定值,但是这样的两个参数的结果也没有比前者更优。

 

通过对下面的实验结果图可能能更好的展现出两个算法的差异,和在此训练集下的聚类结果和正确率。KMeans的聚类错误点大多集中在两个簇的交接点,这样的距离是很难得到一个区分的,而DBSCAN的错误点到处都有分布,这个和他的阈值范围有很大的关系,这个抖动是无法避免的。

 

 

 

 

4、实验结论

 

在当前的iris数据集中,KMeans的聚类效果比DBSCAN的效果要好(因为参数的不确定性不能够整体的评价两个算法之间的差异),从聚类出错的节点数量的多少情况我们就可以得到一个很直观的判断。因为KMeans基于距离的计算方式也直接的导致了它在两个簇之间的节点不好划分的这样一个问题,而DBSCAN是基于密度从全部节点中进行数据量的集中,因此划分错误节点分布较为散开。

 

因此在对于聚类数量较为精确而且类别之间的划分较为明显时使用KMeans有更好的表现能力,但是可能会存在聚簇中心选择不合理的情况,需要使用对此的随机来进行最佳节点的选择,尽量的消除一次随机带来的误差。对于情况不清晰而且存在噪声污染的数据样本使用DBSCAN能达到更好的一个变现能力,因为整个算法本身即与密度来进行计算,但是需要对于核心参数进行多次的输入,以此提高算法的准确度。

 

5、实验心得体会

 

经过这次实验,我收获了很多,一方面加深了两个聚类算法的知识与知识的应用,另一方面还提高了自我动手做项目的本事。在实验中我学到了许多新的知识,通过对两个算法进行算法比较,更加深刻地认识到算法的执行过程,增强对分类算法的核心理解,同时也锻炼了对于编码的实操能力。理解了KMeans和DBSCAN聚类的整体过程,更加明白了相关算法计算公式的含义。

 

参考文献

 

1、数据仓库与数据挖掘

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。