篮球让分胜负投注技巧

30倍性能提升 | DataExa-Insight 利用图算法优化层次聚类

1

层次聚类算法介绍


聚类算法作为机器学习算法体系的一个重要分支,主要适用于对无监督数据进行特征分析与类别划分,聚类问题就是将数据集按照某一预先定义的距离标准划分为多个不同的类或簇,其中类内成员之间的关联关系比较强,而类间成员则表现为弱关联或者无关联关系。目前主流的聚类算法有:K-Means(K均值)聚类、均值漂移聚类、DBSCAN密度聚类、最大期望聚类、凝聚层次聚类、图团体检测聚类。

本次分享主要就凝聚层次聚类算法在海量数据下遇到的性能瓶颈问题提出了一种可行的解决方案。

层次聚类算法一般可分为两类:自上而下的和自下而上的。其中凝聚层级聚类是采用自下而上的方?#20581;?#22312;聚类过程中,凝聚层级聚类方式首?#28982;?#23558;每个数据点视为一个单一的簇,然后计算所有簇之间的距离来合并簇,直到所有的簇聚合成为一个簇为止。

具体步骤可描述为:

第一步,首先将无监督数据集中的每个数据点视为一个单独的簇;

第二步,选择一个测量两个簇之间距离的度量标准,如:使用average linkage作为标准,将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离;

第三步,在每次迭代中,将两个具有最小标准度量距离的簇合并成为一个簇;

第四步,重新计算合并后的簇与其他簇之间的标准度量距离;

第五步,重复步骤三与步骤四,直到所有的数据点合并成一个簇;

第六步,按所需聚类簇的个数,得到聚类结果。

层次聚类算法的优点:

1)无需事先指定聚类簇的个数;(2)对于距离度量标准的选择并不敏感 ;(3)可以发现数据之间的层次关系;

层次聚类算法的缺点:

1)大数据量下计算效率低下;(2)合并终止条件难以控制;(3)奇异值会对聚类产生较大影响;(4)算法很有可能聚类成链状。


  场景应用案例


推荐系统中对文本数据的无主题聚类分析


目前,推荐系统已被广泛应用于各种直?#29992;?#23545;c端用户的商业场景,为平台用户提供丰富的个性化物品推荐服务,其中推荐的内容主要有:文本消息、影音视讯、实体商品等。在文本消息推荐引擎中,对海量的文本信息进行无主题聚类是非常关键的一个?#26041;冢?#20026;了提高文本聚类分析的效果,可选用层次聚类算法进行无主题的文本聚类,其中标准度量距离可通过综合两类信息进行评估?#21644;?#36807;人工或者深度学习(自然语言处理)技术计算两文本之间的语义相似度度量ai j;通过解析海量的用户行为数据,将用户的一系列行为转化为文本之间的相似度度量bi j。使用层次聚类算法的文本数据无主题分析流程可大?#26053;?#36848;如下:

第一步计算两两文本信息之间的两类相似度度量:ai j  bi j

第二步得到两两文本信息之间的标准距离度量:Ci j = w1 × ai j + 1 - w1× bi j

第三步,使用凝聚层次聚类算法得到聚类分析结果;

第四步,对结果进行特征分析,得到最佳聚类无主题分簇结果;

第五步,基于此无主题文本数据聚类结果展开一系列个性化推荐业务。



基于以上案例可知,凝聚层次聚类算法一般适用的场景数据具有以下特点:

1.样本点之间的标准度量距离定义清晰且计算高效;

2.样本点量级不可过大;

3.聚类结果边界相对清晰;

4.有较明确的聚类终止条件。


3
层次聚类算法在进行大规模聚类时会遇到的性能问题


由于层次聚类算法在每一次的合并迭代中,都需要重新计算新簇与其他簇之间的标准度量距离,因此将传统的层次聚类方式应用于真实的业务场景时,往往会由于数据量级相对较大而导致计算效率低下的问题。为了解决以上问题,我们尝试了集群下通过spark分布式计算来优化并提升层次聚类的计算效率,但仍未获得理想中的效果,主要是因为通过简单的数据筛选与过滤等操作仅能缩减很少一部分的数据计算量,大规模数据下的时间复杂度并未得到本质性的解决。


假设待聚类的样本数量为V个,那么层次聚类需要计算的标准度量距离空间复杂度?#27425;?/span>O(V2真实业务场景中V一般都在1000w以上,因此生成了极大的计算时间开销,导致计算效率极其低下。


4
引入?#25216;?#31639;算法进行优化


优化思路:虽然通过引入分布式计算加速了簇之间的标准度量距离的计算效率,但是并未从根本上优化算法计算的时间复杂度,主要的思路仍为通过迭代计算,每次合并最近的一组簇,直到达到终止条件。在多次实践中我们发现,利用图算法中的最小生成树思想可以优化了整个层次聚类算法的计算流程,使得基于最小生成树的层次聚类算法能够更加充分地适配于分布式计算方式,将原本计算复杂度极高的O(V2)问题分解成多个相对简单的子问题,并由各分布式节点进行高效计算,优化后时间复杂度为:O(E log V ),其中E为关系的数量。基于最小生成树的层次聚类算法主要步骤如下:

第一步,将整个数据集分为大致相等的s份;

第二步,对于划分的s份数据生成s个子图;

第三步,对于划分的s份数据,循环操作两两数据集,使生成基于该两份数据集合的1个子图,最终将生成Cs2个子图;

第四步,在第三步与第四步构建的s + Cs2个子图基础上,使用Prim算法生成每一个子图的最小生成子树;

第五步,在生成的s + Cs2棵最小生成子树上,使用Kruskal算法每次合并k棵满足条件的最小生成子树;

第六步,循环步骤五,直到构建完一棵完整的最小生成树;

第七步,按照业务目标对聚类的划分粒度要去,拆解完全最小生成树,得到聚类结果。


5
性能对比


本次性能对比过程中,我们基于已计算完成的标准度量距离数据在spark分布式集群上进行了不同层次聚类算法之间的性能对比,标准度量距离数据格式为:样本点A、样本点B、样本点A与样本点B之间的标准度量距离。性能对比数据中,覆盖的样本点数为:304647,行数为:9531287,数据量大小为:1125.6MB数据样本如下:

其中?#35797;?#20351;用配置如下:

spark.executor.memory=20g

spark.executor.cores=5

spark.executor.instances=12

spark.default.parallelism=120

性能测试时间开销:


(1)原始层次聚类算法:1hrs58mins10sec

(2)基于spark优化后的层次聚类算法:18mins26sec

(3)基于最小生成树的层次聚类算法:4mins58sec


基于最小生成树的层次聚类算法在相同的配置下,对304647个样本、9531287条关系进行聚类会比未做任何优化的层次聚类算法提升近29倍。

注:终止阈值设置为0.95表示:当进行一次聚类合并后,最大关系度量值(范围:[01])低于0.95即终止聚类操作。


6
零编码使用MST层次聚类组件


DataExa - Insight数据洞察平台内置了基于最小生成树方式的层次聚类算法组件,用户可以方便地通过使用集成后组件构建业务模型,无需任何编码就可以直接使用高效的最小生成树层次聚类算法,如上述推荐系统中对文本数据的无主题聚类分析案例,可在DataExa - Insight数据洞察平台通过简单的拖拉组件操作构建如下有向无环流程图:

运行过程图:



篮球让分胜负投注技巧