通过Apache Spark建立共识集群

  • 时间:2018-06-19 22:28 作者:爱码农 来源:爱码农 阅读:96
  • 扫一扫,手机访问
摘要:研究共识聚类以表示屡次聚类算法的共识,并分析聚类关于采样变异性的稳固性。详情在本文中,我们将探讨一种称为共识聚类的技术,以评估聚类算法针对数据集中的小扰动生成的聚类的稳固性。我们将回顾用Apache Spark机器学习库构建的示例应使用程序,以显示如何用K-means,Bisecting K-mea

研究共识聚类以表示屡次聚类算法的共识,并分析聚类关于采样变异性的稳固性。

详情

在本文中,我们将探讨一种称为共识聚类的技术,以评估聚类算法针对数据集中的小扰动生成的聚类的稳固性。我们将回顾用Apache Spark机器学习库构建的示例应使用程序,以显示如何用K-means,Bisecting K-means和Gaussian Mixture(三种不同的聚类算法)能用共识聚类。

机器学习中的聚类分析[1]旨在根据数据点之间的类似性度量将数据划分为单独的,不重叠的集合。同一集群中的数据点必需尽可可以相近(类似),并且不同集群中的数据点必需尽可可以相距(不类似)。聚类分析在生物学,生物信息学,医学,商业,计算机科学和社会科学等各种科学学科中有很多应使用[1]。以下是少量例子。

  • 聚类可使用于医学图像的像素分类,以辅助医学诊断[2]。
  • 为了分析患者的预期寿命取决于他们属于哪一个群,[3],癌症患者的数据能根据某些属性(例如“区域节点阳性”和“阶段组群”)聚类为一组。
  • 癌细胞的基因表达可通过聚类技术进行分析,以分析细胞结构并预测生存[4]。

许多不同的技术和算法可使用于聚类分析,其中[5]和[6]提供了极好的评论。

问题陈述

不同的聚类算法能为相同的数据集创立不同的聚类。在不同的执行过程中,即便是相同的算法也会产生不同的簇,例如因为随机启动。作为一个例子,我们从美国国家癌症研究所GDC数据门户网站下载了关于多形性成胶质细胞瘤(GBM)和低级别胶质瘤(LGG)患者的数据集,并用K均值聚类算法将它们分成三个聚类。

结果如图1.a,1.b所示,使用于两种不同的解决。

通过Apache Spark建立共识集群

图1.a. 通过K-means算法取得的使用于GBM和LGG患者的一组聚类。

图1.b. 通过K-means算法取得的另一组集群使用于GBM和LGG患者。

在每个图表中,有三个由黑色,深蓝色和浅蓝色组成的群集。横轴表示变异分类(与患者中观察到的TP53基因突变有关的变异等位基因的特定特征)和肿瘤分级。纵轴表示施使用于患者的化学治疗次数。

请注意,集群集不一致。假如算法在不同的执行过程中为相同的数据集产生显着不同的集群,我们能相信该算法吗?我们如何选择一种算法来对群集结构感到最自信?

在本文中,我们将探讨称为共识聚类的分析技术,以表示在屡次聚类算法运行中的共识,并分析发现的聚类在采样变异性方面的稳固性[7]。

条款的组织

在下一节中,我们将探讨共识聚类的基础知识。以下部分涉及使用Apache Spark MLLib机器学习库[8]开发的样例应使用程序的代码审查,该样例应使用程序用三种不同的聚类算法,K均值,平分K均值和高斯混合[5] ,[6]。最后一节给出结论。

共识聚类

共识聚类基于这样的假设:每次在略微不同的数据集版本上执行时,可靠的聚类算法应该创立相似的聚类。换句话说,数据集上的微小扰动不应该显着改变所得到的聚类。

为了实现共识聚类,原始数据集被随机二次采样m次,以创立比原始数据集略小的m个不同数据集。而后聚类算法重复m次(迭代),每个子采样数据集一次。

接下来,对于原始数据集中的每对数据点,确定该对在该聚类算法的特定迭代中在相同聚类中出现多少次。这个想法是,假如这对数据点是“类似的”,那么当对应于迭代的二次采样数据集同时包含这两个数据点时,它们理想情况下应当放置在每次迭代中的相同群集中。相似地,假如数据点是“不类似的”,则当与迭代相对应的二次采样数据集同时包含两者时,它们应该在每次迭代中置于不同的聚类中。

为了量化共识,构建了所谓的“共识矩阵”。让原始数据集由N个数据点组成。而后,一致矩阵是一个对称的N×N矩阵,其中元素(i,j)等于数据点a i和被分配到同一个簇中的j的次数除以数据点a i的次数和j一起被选中。一致矩阵的对角线元素始终为1,任何非对角元素都在0和1之间(包括0和1)。

作为一个非常简单的例子,考虑在二维空间中由5个数据点{a 1,a 2,a 3,a 4,a 5 } 组成的数据集。

通过Apache Spark建立共识集群

图2.二维空间中5个数据点的示例

这些数据点的共识矩阵可可以如下所示:

通过Apache Spark建立共识集群

考虑突出显示的元素(1,3),其对应于数据点对a 1,a 3。该要素的价值意味着:

(将1和3分配给同一簇的次数)/ (1和3一起选择的次数)= 0.9

因而,在数据样本中一起选择点a 1和a 3的 90%时间,算法将它们放在同一个群集中。另一方面,共识矩阵意味着只有10%的时间算法放在一起(元素(1,4))选择一个1和4在相同的群集。

令人满意的共识意味着共识矩阵的任何非对角元素都非常接近1,由于特定的数据点对是类似的,因而算法在大多数迭代中将它们分配给相同的群集,或者者非常接近0 ,由于特定的数据点对是不类似的,因而算法在大多数迭代中将它们分配给不同的群集。另一方面,远离0和1的条目意味着较差的共识。例如,值为0.5的条目意味着该算法已将相应的一对数据点放置在50%的迭代中的相同群集中,并且在剩余的50%的迭代中放置在单独的群集中。

共识矩阵的行和列能被置换,以使最近的数据点尽可可以地彼此相邻,从而产生对称的热图,而后通过视觉检查帮助决定共识[9]。参见[10]查看从共识矩阵生成热图的算法。

对于视觉检查,热图的另一种方法是开发与共识矩阵有关的直方图,称为共识指数直方图[7]。直方图的水平轴表示一对两个不同数据点出现在同一个群集中的次数与所有迭代中同一子样本中该对次数的比率。直方图的纵轴显示达到特定比率的次数。在理想情况下,直方图只趋向于接近1和0的两个仓,其中1周围的仓代表同一集群中的一对不同数据点,而0周围的仓代表一对不同的数据点,它们分别是在大部分时间跨越所有迭代的不同群集中。

对于每个K均值,平分K均值和高斯混合算法,我们将一致的聚类技术应使用于我们的数据集,以创立m= 20次迭代的三个聚类。在每次迭代中,随机子样本由原始数据集的?90%组成。每种算法的直方图如下所示(生成这些图表的应使用程序的源代码将在下一节中进行详情)。

通过Apache Spark建立共识集群

图3. K-means算法的直方图。

通过Apache Spark建立共识集群

图4.平分K均值算法的直方图。

通过Apache Spark建立共识集群

图5.高斯混合算法的直方图。

对于平分K均值和高斯混合算法,数据主要累积在0和1周围的箱中,特别是在区间[0,0.2]和[0.8,1.0]中。另一方面,对于K均值算法,0到1之间的分箱包含太多的数据点,特别是在区间[0.4,0.7]中。因而,我们得出这样的结论:对于特定的数据集,K均值算法没有达到像平分K均值或者高斯混合一样令人满意的共识。

代码审查

我们实施了一个示例Java应使用程序来演示共识聚类。应使用程序用Apache Spark机器学习库API使用于K-means,Bisecting K-means和Gaussian Mixture(Spark版本2.3.0)。一个名为笼统类的 ConsensusCluster存储所有使用于计算直方图的逻辑。三个具体的类, BisectingKMeansClustering, KMeansClustering 和, GaussianMixtureClustering每个代表一个特定的聚类算法,创立实际的簇。

通过Apache Spark建立共识集群

图6.演示应使用程序的类图。

示例应使用程序用一个数据集,如前面在美国国家癌症研究所GDC数据门户网站下载的关于多形性成胶质细胞瘤(GBM)和低级别胶质瘤(LGG)患者['11]中的'问题陈述'中所述。它由76个不同的数据点组成。对于一致计算,我们运行了20次迭代。在每次迭代中,数据被随机二次采样,每个子采样包含原始(完整)数据集的约90%。

用每种算法,我们在每次迭代中创立了三个群集。我们在所有迭代完成后生成直方图数据。图3,4,5给出了每种算法的直方图图。

结论

在本文中,我们探讨了共识聚类,这是一种使用于在屡次聚类算法运行中表示共识的技术,并分析了发现聚类在采样变异性方面的稳固性。我们回顾了用Apache Spark机器学习库构建的示例应使用程序,以显示如何用K-means,Bisecting K-means和高斯混合(三种不同的聚类算法)能用共识聚类。对于应使用程序中考虑的示例数据集,我们计算并绘制了共识指数的直方图。直方图表明,平分K均值和高斯混合算法比K均值算法提供更稳固的聚类。少量结论性意见如下。

  • 共识聚类可应使用于任何聚类算法,并可使用于比较同一数据集上的不同算法。然而,一致聚类的目的不是决定哪些聚类算法比其余算法更稳固一般。结果取决于特定的数据集和数据点之间关系的性质。例如,层次聚类算法可可以无法达到令人满意的本质上不分层次的数据集的共识,反之亦然。
  • 另外能用共识聚类来确定数据集和聚类算法的最佳聚类数。共识矩阵也能使用作类似性度量,是其余度量的替代方法,例如欧几里得距离[7]。
  • 图1.a,1.b中的样本簇的三维图由基于Java的jzy3d框架[12]取得,图3-5中的直方图由Microsoft Excel绘制。
  • 示例应使用程序的完整源代码能在[13]中找到。
  • 全部评论(0)
最新发布的资讯信息
【系统环境|】2019年web前端开发技术框架有哪些(2019-07-20 12:06)
【系统环境|】什么是Web?零基础能不能学Web前端开发?(2019-07-19 07:04)
【网页前端|HTML】为什么学Web前端?选择Web前端理由(2019-07-17 20:28)
【网页前端|JS】Java面经-百度新入职老哥整理近半年学习经验,面试刷题路线!(2019-07-16 22:16)
【网页前端|HTML】最全面的前端开发指南(2019-07-15 12:57)
【系统环境|数据库】零基础如何快速学好大数据?(2019-06-29 12:27)
【系统环境|Linux】零基础如何学好大数据?必备需要学习知识(2019-06-18 11:54)
【系统环境|】Hadoop环境中管理大数据存储八大技巧(2019-06-15 11:01)
【系统环境|服务器应用】现在国内IT行业是不是程序员过多了?(2019-06-11 06:34)
【系统环境|服务器应用】新贵 Flutter(2) 自己设置 Widget(2019-06-11 06:34)
手机二维码手机访问领取大礼包
返回顶部