探讨在集群环境下，如何设计并行聚类算法。作为一种低成本、通用并行系统，集群系统的通信能力，相对于节点的计算能力，是一个瓶颈。所以在集群环境下，设计并行聚类算法时，应采用数据并行的思想。从理论上，对采用数据并行思想后，...探讨在集群环境下，如何设计并行聚类算法。作为一种低成本、通用并行系统，集群系统的通信能力，相对于节点的计算能力，是一个瓶颈。所以在集群环境下，设计并行聚类算法时，应采用数据并行的思想。从理论上，对采用数据并行思想后，影响聚类算法的加速比和聚类质量的因素进行了分析，然后通过一个验证算法PCIT(Parallel clustering algorithm based on Index Tree)证实了理论分析的正确性。研究结果可以为以后设计更好的数据并行聚类算法提供理论依据。展开更多
针对传统串行聚类集成算法在处理高维海量数据时效率低下的问题,提出基于Spark的并行聚类集成算法SCEA(Spark based Clustering Ensemble Algorithm).首先,通过主成分分析与成对约束结合的方法对算法输入数据进行预处理,达到数据降维并...针对传统串行聚类集成算法在处理高维海量数据时效率低下的问题,提出基于Spark的并行聚类集成算法SCEA(Spark based Clustering Ensemble Algorithm).首先,通过主成分分析与成对约束结合的方法对算法输入数据进行预处理,达到数据降维并去除特征相关性的目的;其次,通过调用不同聚类算法获得基聚类成员后,采用三元组方法通过基聚类成员的簇标签构造出相似度矩阵,并调用层次聚类算法得到最终的聚类结果;最后,在调用MLlib中已有聚类算法的基础上,基于Scala对SCEA算法进行了实现.将SCEA与同类算法在多组数据集下进行对比测试,实验结果表明:总体上SCEA不仅较已有算法在准确率方面有所提高,并且通过分析运行时间、加速比以及可扩展性3个性能指标,证明了SCEA在算法性能上的优越性.展开更多
针对大数据环境下并行K-means算法存在的面对高维数据聚类效果差、数据分区不均匀、初始质心敏感等问题,提出了一种基于MapReduce和MSSA的并行K-means算法MR-MSKCA。首先,提出基于肯德尔相关系数和深度稀疏自动编码器的降维策略(dimensi...针对大数据环境下并行K-means算法存在的面对高维数据聚类效果差、数据分区不均匀、初始质心敏感等问题,提出了一种基于MapReduce和MSSA的并行K-means算法MR-MSKCA。首先,提出基于肯德尔相关系数和深度稀疏自动编码器的降维策略(dimensionality reduction strategy based on Kendall correlation coefficient and DSAE,DRKCAE)对高维数据进行特征加权和特征提取,解决了高维数据不相关特征和结构稀疏导致的聚类效果差的问题;其次,提出基于两段映射的广义超平面分区策略(uniform partition strategy based on two-stage mapping,UPS)对数据集进行划分,获取均匀的数据分区;最后提出非均匀变异麻雀搜索算法(non-uniform mutation sparrow search algorithm,MSSA)用于获取并行K-means的聚类质心,解决了算法初始质心敏感的问题。在UCI数据集上进行的实验显示,MR-MSKCA较MR-KNMF、MR-PGDLSH、MR-GAPKCA的运行时间分别降低了45.1%、49.1%、59.8%,聚类效果分别提升了19.2%、22.8%、24%,表明MR-MSKCA对大数据进行聚类时有良好性能,适用于不同场景的大数据聚类分析。展开更多
文摘探讨在集群环境下，如何设计并行聚类算法。作为一种低成本、通用并行系统，集群系统的通信能力，相对于节点的计算能力，是一个瓶颈。所以在集群环境下，设计并行聚类算法时，应采用数据并行的思想。从理论上，对采用数据并行思想后，影响聚类算法的加速比和聚类质量的因素进行了分析，然后通过一个验证算法PCIT(Parallel clustering algorithm based on Index Tree)证实了理论分析的正确性。研究结果可以为以后设计更好的数据并行聚类算法提供理论依据。
文摘针对传统串行聚类集成算法在处理高维海量数据时效率低下的问题,提出基于Spark的并行聚类集成算法SCEA(Spark based Clustering Ensemble Algorithm).首先,通过主成分分析与成对约束结合的方法对算法输入数据进行预处理,达到数据降维并去除特征相关性的目的;其次,通过调用不同聚类算法获得基聚类成员后,采用三元组方法通过基聚类成员的簇标签构造出相似度矩阵,并调用层次聚类算法得到最终的聚类结果;最后,在调用MLlib中已有聚类算法的基础上,基于Scala对SCEA算法进行了实现.将SCEA与同类算法在多组数据集下进行对比测试,实验结果表明:总体上SCEA不仅较已有算法在准确率方面有所提高,并且通过分析运行时间、加速比以及可扩展性3个性能指标,证明了SCEA在算法性能上的优越性.
文摘针对大数据环境下并行K-means算法存在的面对高维数据聚类效果差、数据分区不均匀、初始质心敏感等问题,提出了一种基于MapReduce和MSSA的并行K-means算法MR-MSKCA。首先,提出基于肯德尔相关系数和深度稀疏自动编码器的降维策略(dimensionality reduction strategy based on Kendall correlation coefficient and DSAE,DRKCAE)对高维数据进行特征加权和特征提取,解决了高维数据不相关特征和结构稀疏导致的聚类效果差的问题;其次,提出基于两段映射的广义超平面分区策略(uniform partition strategy based on two-stage mapping,UPS)对数据集进行划分,获取均匀的数据分区;最后提出非均匀变异麻雀搜索算法(non-uniform mutation sparrow search algorithm,MSSA)用于获取并行K-means的聚类质心,解决了算法初始质心敏感的问题。在UCI数据集上进行的实验显示,MR-MSKCA较MR-KNMF、MR-PGDLSH、MR-GAPKCA的运行时间分别降低了45.1%、49.1%、59.8%,聚类效果分别提升了19.2%、22.8%、24%,表明MR-MSKCA对大数据进行聚类时有良好性能,适用于不同场景的大数据聚类分析。
文摘目的随着城市交通拥堵问题的日益严重,建立有效的道路拥堵可视化系统,对智慧城市建设起着重要作用。针对目前基于车辆密度分析法、车速判定法、行驶时间判定法等模式单一,可信度低的问题,提出了一种基于DBSCAN+(density-based spatial clustering of applications with noise plus)的道路拥堵识别可视化方法。方法引入分块并行计算,相较于传统密度算法,可以适应大规模轨迹数据,并行降维聚类速度快。对结果中缓行区类簇判别路段起始点和终止点,通过曲线拟合和拓扑网络纠偏算法,将类簇中轨迹样本点所表征的路段通过地图匹配算法匹配在电子地图中,并结合各类簇中浮动车平均行驶速度判别道路拥堵程度,以颜色深浅程度进行区分可视化。结果实验结果表明,DBSCAN+算法相较现有改进的DBSCAN算法时间复杂度具有优势,由指数降为线性,可适应海量轨迹点。相较主流地图产品,利用城市出租车车载OBD(on board diagnostics)数据进行城区道路拥堵识别,提取非畅通路段总检出长度相较最优产品提高28.9%,拥堵识别命中率高达91%,较主流产品城区拥堵识别平均命中率提高15%。结论在城市路网中,基于DBSCAN+密度聚类和缓行区平均移动速度的多表征道路拥堵识别算法与主流地图产品相比,对拥堵识别率、通勤程度划分更具代表性,可信度更高,可以为道路拥堵识别的实时性提供保障。
