基于CPU与GPU协作的马尔可夫聚类的并行优化实现

马尔可夫聚类算法(MCL)为网络聚类问题提供了一个有效的方法,尤其是在社区问题和生物信息学方面。然而,矩阵的Expansion是最耗时的操作,因为两个大规模矩阵相乘的时间复杂度是n₃。由于每个元素值的计算是独立的,因此Expansion和Inflation可以并行执行于多核GPU上。一个基本的马尔可夫聚类的并行实现需要使用全邻接矩阵来提高性能,该邻接矩阵通常是稀疏的,有时甚至是极大稀疏的。因此,本文的马尔可夫聚类的并行优化实现采用CSR * CSC格式去存储矩阵,大大减少了空间的浪费,并在一定程度上提升了Expansion的性能。实验结果表明,在处理大规模网络问题上,Sparse-MCL比CPU-MCL和P-MCL更有效。     

一种基于密度的并行聚类算法

针对微阵列基因表达数据聚类的高维复杂性,提出了一种基于密度的并行聚类算法,在APRAM模型的分布式存储系统中,通过欧几里德距离矩阵和密度函数两次时间复杂度为O（■）的计算,可使聚类过程的时间复杂度为O（■）,以增加一次计算的代价来降低聚类过程的时间复杂度。基于8结点的机群计算实验表明：本算法能够达到较同类算法更高的并行加速比,提高高维生物数据的聚类速度。     

基于改进属性约简的细粒度并行AP聚类算法

Affinity Propagation(AP)聚类算法将所有数据点作为潜在的聚类中心,在相似度矩阵的基础上通过消息传递进行聚类.与传统聚类方法相比,对于规模很大的数据集,AP是一种快速、有效的聚类方法.正是这样,属性约简对于AP算法非常重要.另外,在大规模并行系统的设计中,细粒度并行是实现高性能的基本策略.提出了一种基于改进属性约简的细粒度并行AP聚类算法(IRPAP),将粒度思想引入到并行计算中.首先分析了并行计算中的粒度原理.然后用改进的属性约简算法对数据集预处理.此算法并行计算并选择差别矩阵元素,降低了时间空间复杂度,最后用AP算法聚类.整个IRPAP算法将任务划分到多个线程同时处理.实验证明,对于大规模数据集的聚类,IRPAP算法比AP算法效率更高.     

并行谱聚类算法

谱聚类算法是建立在谱图理论上的一种点对聚类算法,具有实现简单、理论基础扎实和适应任意数据空间的优点,因而成为机器学习领域的研究热点.谱聚类算法最大的问题在于计算复杂度过高,而并行计算可以提高解题效率,因此本文采用最为流行的并行计算框架MAP/REDUCE在Hadoop环境中实现了并行谱聚类算法,大大改善了谱聚类算法在大规模数据环境中的聚类效率问题.     

基于节点聚类复杂度的图聚类方法

图聚类可以发现网络中的社区结构，是复杂网络分析中的一项重要任务。针对不同节点的聚类难度各异的问题，提出了一种基于节点聚类复杂度的图聚类算法(Graph Clustering Algorithm Based on Node Clustering Complexity, GCNCC),用于判断节点的聚类复杂度，为聚类复杂度低的节点赋予伪标签，利用伪标签提供的监督信息降低其他节点的聚类复杂度，进而得到网络聚类结果。GCNCC包括节点表示、节点聚类复杂度判别和图聚类3个主要模块。节点表示模块得到保持网络集聚性的表示；节点聚类复杂度判别模块用于判断网络中的低聚类复杂度节点，并利用低聚类复杂度节点的伪标签信息来优化更新网络中其他节点的聚类复杂度；图聚类模块采用标签传播方法，将低聚类复杂度节点标签传播给高聚类复杂度节点，以得到聚类结果。在3个真实的引文网络和3个生物数据集上与9种经典算法进行对比，算法GCNCC在ACC,NMI,ARI和F1等方面均表现良好。     

融合局部结构学习的大规模子空间聚类算法

常规的大规模子空间聚类算法在计算锚点亲和矩阵时忽略了数据之间普遍存在的局部结构，且在计算拉普拉斯（Laplacian）矩阵的近似特征向量时存在较大误差，不利于数据聚类。针对上述问题，提出一种融合局部结构学习的大规模子空间聚类算法（LLSC）。所提算法将局部结构学习嵌入锚点亲和矩阵的学习，从而能够综合利用全局和局部信息挖掘数据的子空间结构；此外，受非负矩阵分解（NMF）的启发，设计一种迭代优化方法以简化锚点亲和矩阵的求解过程；其次，根据Nystr?m近似方法建立锚点亲和矩阵与Laplacian矩阵的数学联系，并改进Laplacian矩阵特征向量的计算方法以提升聚类性能。相较于LMVSC(Large-scale Multi-View Subspace Clustering)、SLSR(Scalable Least Square Regression)、LSC-k(Landmark-based Spectral Clustering using k-means)和k-FSC(k-Factorization Subspace Clustering),LLSC在4个广泛使用的大规模数据集上显示出...     

基于压缩子空间对齐的多核聚类算法

近年来,多核聚类（MKC）在融合多源信息以提高聚类性能方面取得了显著进展。但是,以n表示样本数,O(n2)内存消耗和On3计算消耗限制了这些方法的实用性。重新设计了基于子空间分割的MKC公式,从而将其内存和计算复杂度分别降低到O(n)和O(n2)。在该算法（基于压缩子空间对齐的多核聚类算法CSA-MKC）中,通过对部分数据采样来重建整个数据集。具体而言,在该算法中,在信息融合过程中同时学习了共识采样矩阵,从而使生成的锚点集更适合于跨不同视图的数据重建。因此,改进了重构矩阵的判别性,并增强了聚类性能。此外,该算法易于并行化,通过GPU加速,在6个数据集上进行了测试,在时间上,该算法是数据规模的平方复杂度,在性能上,优于目前的先进算法。     

基于Spark的K-means改进算法的并行化实现

针对传统K-means算法在处理海量数据时,存在计算复杂度高和计算能力不足等问题,提出了SKDk-means （Spark based kd-tree K-means）并行聚类算法.该算法通过引入kd-tree改善初始中心点的选择,克服传统K-means算法因初始点的不确定性,易陷入局部最优解的问题,同时利用kd-tree的最近邻搜索减少K-means在迭代中的距离计算,加快聚类速度,并在Spark平台上实现了该算法的并行化,使其适用于海量数据聚类,最后通过实验验证了算法具有良好的准确率和并行计算性能.     

面向大数据的并行聚类算法

在大数据时代,针对CLUBS算法较高的计算复杂度导致训练效率低下的问题,提出一种面向大规模数据的并行聚类算法CLUBS‖,通过将CLUBS算法的思想融入MapReduce并行计算框架,实现数据的并行处理,提高算法的计算效率,从理论上对几个关键计算的并行化进行较为深入的分析,基于Ad-hoc消息传递对该算法进行实现.实验结果验证了所提方法的有效性.     

基于CombBLAS的同辈压力图聚类并行算法的设计与实现

图聚类是指把图中相对连接紧密的顶点及其相关的边分组形成一个子图的过程,在包括机器学习、数据挖掘、模式识别、图像分析及生物信息等领域有着广泛应用。但是,随着大数据时代的到来,图数据海量增长。面对广泛的大规模图计算需求,由于图结构本身的不规则性,单机算法运行效率低下,用传统的并行计算方法进行图计算难以获得高性能。使用线性代数的方法在Combinatorial BLAS上实现了同辈压力(Peer Pressure)图聚类的分布式算法,首先将该图聚类的算法转换为对稀疏矩阵的运算,从而结构化表示图的不规则数据结构及接入模式,然后基于MPI编程模型将其并行实现。实验结果表明,在并行处理规模达到43亿的由稀疏矩阵表示的超大规模图时,基于线性代数表示的同辈压力图聚类算法在曙光超级计算机上取得了较高的并行性能及良好的可扩展性,在64个核上获得了40.1的并行加速。     

快速复杂网络聚类图形处理器并行算法

研究复杂网络拓扑属性的聚类算法需要处理大量节点和连接边,因此对计算性能要求高,否则无法处理现实中的表示为复杂网络的系统。利用图形处理器(GPU)的并行聚类算法是解决该问题的重要方法。利用原语技术设计并行快速聚类算法,原语法不仅降低并行算法的复杂性而且提高聚类的普适性;再从线程调度策略和缓存管理两个方面提出优化的方法来解决负载均衡和数据重用性问题。通过实验对比并行快速聚类算法与优化算法的性能,结果显示并行快速聚类优化后的算法取得较好加速比。     

Spark平台上利用网络加权Voronoi图的分散迭代社区聚类并行化研究

针对当下数据大规模增长对计算能力需求的急剧增长,传统独立运行的机器在大规模网络社区中执行社区检测操作时无法提供所需的数据处理能力的问题,提出一种网络加权Voronoi图的并行分散迭代社区聚类法(NWVD-PDICCM)。利用基于网络加权Voronoi图的分散迭代社区聚类方法(NWVD-DICCM)提取大型网络的有效社区结构。结合并行聚类方法,将DICCM方法的操作从串行过程转换为并行计算。利用执行并行社区聚类时的图分区,通过最小化从属工作者之间的通信来加速该过程。仿真实验结果表明,NWVD-PDICCM可以与一系列计算机架构平台共同运行,并且实现基于Spark平台的并行操作,相比其他几种较新的方法,在大规模网络数据处理能力方面得到显著提升。     

MapReduce 环境下的并行复杂网络链路预测

为使链路预测应用于大型复杂网络,设计并实现了一种基于MapReduce计算模型的并行链路预测算法,包含了9种基于局部信息的相似性指标,在稀疏网络上的时间复杂度为O(N).首先,在公共数据集上验证了并行算法的有效性,随着抽取因子的增加,召回率升高而准确率下降.在不同类型的10个大规模复杂网络数据集上的实验结果表明,基于MapReduce计算模型的并行链路预测算法比传统算法具有更高的效率,算法的运行时间随着并行程度的增加而下降.提出并证明了AUC(area under a receiver operating characteristic curve)评价指标的上下界,实验表明,上下界的中值和实际AUC值很接近,并且AUC评价指标侧重于预测分数值是否为0而不是分数值的大小.在网络拓扑性质中,平均聚集系数对AUC值的影响最大,并且AUC值随着网络平均聚集系数的增加而提高.     

基于并行图计算的社区划分方法

以图计算形式研究社交网络由来已久,但对于如何提升图计算应用于大规模社交网络的计算速度和扩展性,一直是研究的难点。谱图论的应用为社交网络在图计算方面的研究带来新的研究热点,谱图分割为社交网络社区划分带来基于结构的支撑。为了解决谱图论在处理大规模社交网络时存在计算缓慢、内存溢出等问题,本文提出了谱聚类改进算法结合矩阵方式在并行环境下的处理方法。首先,利用Spark对网络数据进行并行化预处理,将社交网络以图结构表示,再将图转化为Spark分布式稀疏矩阵。然后,将谱聚类改进算法在Spark环境下,实现并行化社交网络社区快速划分,并以分布式方式持久化存储源数据、中间计算数据和计算结果,提高图计算在社交网络中的可靠性。最后,通过实验证明并行化图计算方法能有效提高计算速度和扩展性,支持大规模社交网络的挖掘分析,实现并行算法下高并发、高吞吐的特点。     

基于粒子群优化的WSN非均匀分簇路由算法

分簇算法对大规模无线传感器网络(WSN)远程监控系统具有较好的节能性,簇首间通过多跳通信的方式将数据传送至基站,靠近基站的簇首由于需要转发大量其他簇首的数据而负载过重,可能因过早耗尽能量而失效,这将导致整个网络分割。针对现有无线传感器网络分簇算法存在的能耗不均衡问题,提出一种基于粒子群优化的非均匀分簇算法(PSO-UCA)。它采用PSO算法将所有节点划分为多个规模大小非均匀的簇,靠近基站的簇的规模小于远离基站的簇,因此靠近基站的簇首可为簇间的数据转发预留能量。仿真结果表明,与LEACH算法相比较,该分簇算法可使网络的生存时间延长30%。     

基于异构并行计算的单细胞测序数据聚类算法

随着单细胞RNA测序技术的发展,目前单细胞测序通量由上千细胞发展到主流上万细胞的规模。基于单细胞RNA测序数据的细胞分型是研究细胞的重要问题之一,该问题主要运用无监督聚类方法。现有针对大规模单细胞测序数据的聚类方法通过简化细胞关系网络来降低时间复杂度,从而导致细胞分型准确度降低。而常见较高准确度的细胞分型方法无法处理大规模数据。为此,采用将[k]最近邻与细胞相似度阈值结合构建全新的细胞关系网络,并采用CPU+GPU异构并行计算提高运算速度,通过改进的马尔科夫聚类算法进行细胞聚类。通过在七个较大规模单细胞数据集上实验,发现该算法比现有主要算法具有更好的聚类准确度,从而适合基于主流单细胞测序技术数据的细胞分型。     

基于自组织神经网络和模糊聚类的校园无线网用户日常行为分析

针对如何分析校园无线网络数据,挖掘数据中蕴藏的学生行为,更好地辅助教学管理,本文提出了在Hadoop平台构建基于自组织神经网络(SOFM)的模糊C-均值(FCM)聚类算法。该算法采用自组织神经网络与模糊C-均值聚类算法相结合,避免了模糊C-均值聚类算法初始化不当带来的误差,目标函数中采用马氏距离,自适应的调整了数据的几何分布。考虑到无线用户数据规模庞大,采用了Hadoop平台并行运行聚类算法。实验结果表明,本文提出的算法提高了聚类结果的准确性,有效地降低了时间复杂度,分析平台为学校管理层快速有效的做出决策提供了依据,研究分析方法对其它高校有较大地参考价值。     

一种基于分簇的3D-RSSI的定位算法

节点定位是无线传感器网络的重要支撑技术之一,本文提出了一种适用于大规模无线传感器网络的分布式分簇定位算法。相比于集中式算法而言,本文提出的分簇式算法更适用于大规模无线传感器网络,不仅算法的复杂度低,而且通信量小,鲁棒性较好。在三维空间中随机分布节点,仿真结果表明,本文所提出的算法能取得较好的定位效果。     

基于深度自动编码器的脑网络状态观测矩阵降维方法

针对人脑网络状态观测矩阵高维无特征的特点,给出了一种基于深度自动编码器(DAE)的降维算法.利用深度学习网络,将高维的人脑网络空间表达映射到低维的本质特征空间中,为进一步提炼脑网络的动态性能提供了基础.实验结果证明:应用该方法可以达到有效的降维效果,且降维后脑网络状态通过自组织特征映射聚类具有一定的规律性,从而为脑网络的动态特性研究提供了基础.     

Clustering the wireless Ad Hoc networks: A distributed learning automata approach

In Ad Hoc networks, the performance is significantly degraded as the size of the network grows. The network clustering by which the nodes are hierarchically organized on the basis of the proximity relieves this performance degradation. Finding the weakly connected dominating set (WCDS) is a promising approach for clustering the wireless Ad Hoc networks. Finding the minimum WCDS in the unit disk graph is an NP-Hard problem, and a host of approximation algorithms has been proposed. In this article, we first proposed a centralized approximation algorithm called DLA-CC based on distributed learning automata (DLA) for finding a near optimal solution to the minimum WCDS problem. Then, we propose a DLA-based clustering algorithm called DLA-DC for clustering the wireless Ad Hoc networks. The proposed cluster formation algorithm is a distributed implementation of DLA-CC, in which the dominator nodes and their closed neighbors assume the role of the cluster-heads and cluster members, respectively. In this article, we compute the worst case running time and message complexity of the clustering algorithm for finding a near optimal cluster-head set. We argue that by a proper choice of the learning rate of the clustering algorithm, a trade-off between the running time and message complexity of algorithm with the cluster-head set size (clustering optimality) can be made. The simulation results show the superiority of the proposed algorithms over the existing methods.