并行k均值聚类算法的完备性证明与实现

对经典k均值算法进行分析,证明如何在减少节点间通信代价的情况下,从局部聚类信息生成完备的全局聚类信息,使聚类质量等价于相应串行算法,并具有较高的执行效率,在此基础上给出可信的基于消息传递接口的并行k均值算法。实验结果表明,该算法是高效的和可行的。     

数据挖掘技术——聚类算法研究

介绍了聚类算法的分类,对每一类聚类方法给出了典型的聚类算法,重点对基于划分算法的PAN算法给出了详细的阐述,总结和归纳了PAM算法四种代价的计算方法,同时给出了其性能分析。     

核函数在划分聚类中的应用与实现

聚类是数据挖掘的一种重要方法,核函数是能够将低维不可分的数据映射到高维空间进行线性可分时能够降低数据处理难度的重要手段。介绍了聚类算法和核函数的特点。通过引入基于核函数的相似性测度,对k-平均聚类算法和围绕中心点的划分(PAM)算法在Matlab上做了改进和实现。     

基于PAM和均匀设计的并行粒子群优化算法

聚类技术是数据挖掘中的一个重要方法,PAM（Partitioning Around Medoids）是基于分区的聚类算法的一种,它试图将[n]个数据对象分成[k]个部分。在并行粒子群PSO（Particle Swarm Optimization）算法中,需要划分整个种群为几个相互不重叠的子种群。因此,引入PAM来划分整个种群。通过聚类,相同子种群的粒子相对集中,从而能够较容易地相互学习。这使得有限的时间能够花费在最有效的搜索上,以便提高算法的搜索效率。为了均匀地探测整个解空间,引入均匀设计来产生初始种群,使种群成员均匀地分散在可行解空间中。进化过程中,均匀设计也被引入来替换种群中的较差个体。提出基于PAM和均匀设计的并行粒子群算法,它结合并充分利用了二者的优点。对几个测试问题的实验结果证明,提出的算法比传统的并行粒子群算法具有更高的性能和更好的收敛准确性。     

一种基于SOM和PAM的聚类算法

提出了一种基于自组织映射（SOM）算法和围绕中心点的划分（PAM）算法相结合的SOM-PAM聚类算法。该算法首先利用SOM算法对数据集进行“粗聚类”并得到簇数k；然后，根据簇数k再利用PAM算法对“粗聚类”结果进行聚类并得到最终聚类结果。通过实验表明，SOM-PAM算法具有比SOM算法更高的聚类效率和更好的聚类质量。     

基于划分的蚁群聚类算法研究

聚类分析是一种重要的人类活动,被广泛应用于数据挖掘、统计学、生物学和机器学习等领域。随着仿生学的发展,一种新的智能优化算法——蚁群算法被提出,并被应用于聚类分析。针对PAM算法和蚁群聚类算法的缺点,提出了一种将PAM算法和蚁群聚类算法相结合的聚类方法。仿真实验表明,算法性能得到了有效提高。     

基于聚类算法的并行化研究

聚类是数据挖掘中重要组成部分,为了提高聚类的处理效率,将并行处理技术运用于k-means和PAM算法中,对k-means与PAM算法进行了改进。实验结果表明:并行k-means算法相对串行k-means算法有更好的执行效率;且k-means算法有比PAM算法更好的并行性和可扩展性。最后,该文提出和介绍了将并行技术引入谱聚类算法。     

k中心点聚类算法在层次数据的应用

探讨了近年来提出的聚类概念与聚类过程、k中心点聚类的算法,在此基础上提出了一种基于层次数据模型的k中心聚类的改进算法.该算法一方面针对层次变量提出了相关的中值点概念;另一方面对传统k中心点算法进行了改进.最后对改进算法的复杂度进行了分析,由分析结果得出改进算法要比传统k中心点算法每次迭代耗费时间略少,但在总耗费时间上远远小于k中心点算法,大幅度提高了算法的整体性能.     

蚁群优化与模糊聚类结合的文本聚类研究

针对模糊文本聚类算法（FCM）对输入顺序以及初始点敏感的问题,提出了一种使用蚁群优化的模糊聚类算法（FACA）。该算法采用蚁群聚类算法（ACA）找到聚类的初始中心点,以解决模糊聚类的输入顺序以及初始点敏感等问题。模糊文本聚类算法的线性复杂度使其更便于在计算机实现。与经典的基本模糊聚类以及蚁群聚类在真实数据集上仿真相比较,结果表明经蚁群优化过的模糊聚类算法（FACA）效果更有效,更适合应用于大型的数据集。     

基于MPI的并行PSO混合K均值聚类算法

传统的串行聚类算法在对海量数据进行聚类时性能往往不尽如人意,为了适应海量数据聚类分析的性能要求,针对传统聚类算法的不足,提出一种基于消息传递接口(MPI)集群的并行PSO混合K均值聚类算法。首先将改进的粒子群与K均值结合,提高该算法的全局搜索能力,然后利用该算法提出一种新的并行聚类策略,并将该算法与K均值聚类算法、粒子群优化(PSO)聚类算法进行比较。实验结果表明,该算法不仅具有较好的全局收敛性,而且具有较高的加速比。     

大规模生物网络马尔可夫聚类的并行化算法

马尔可夫聚类算法（MCL）是在大规模生物网络中寻找模块的一个有效方法，能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算，因此复杂度可达立方阶次。针对复杂度高的问题，提出了基于消息传递接口（MPI）的并行化马尔可夫聚类算法以提高算法的计算性能。首先，生物网络转化成邻接矩阵；然后，根据算法的特性，按照矩阵的规模判断并重新生成新矩阵以处理非平方倍数矩阵的计算；其次，并行计算通过按块分配的方式能够有效地实现任意规模矩阵的运算；最后，循环并行计算直至收敛，得到网络聚类结果。通过模拟网络和真实生物网络数据集的实验结果表明，与全块集体式通信（FCC）并行方法相比，平均并行效率提升了10个百分点以上，因此可以将该优化算法应用在不同类型的大规模生物网络中。     

并行最短路径搜索算法的设计与实现

针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O（N²）减少到O（N²/p+N*（p-1））,提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。     

基于主从式并行遗传算法的S盒优化算法

针对传统遗传算法优化高阶S盒中适应度评价值计算量相对大的问题,利用MPI+C环境结合主从式并行遗传算法框架来改进传统串行遗传算法,在MPP处理机——“深腾-1800”（联想）上进行测试,实验结果表明,运用此并行算法优化6阶、8阶的双射S盒,只在优化8阶的情况下能得到更好的加速比,从而验证了主从模式在解决适应度评价值计算量大的问题时,可达到接近线性的加速比。     

一种改进并行遗传算法解决TSP

针对旅行商问题（Travelling Salesman Problem,TSP）的遗传算法的大规模操作,需要大量运算时间而且容易造成局部最优解,提出一种并行混合遗传算法。该方法基于MPI并行环境,利用种群中选择、交叉、变异操作的并行化,将种群中个体平均的分配到处理器中进行操作,有效地避免局部最优解的出现和减少算法的运行时间。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。     

MPI_ALLGATHER实现算法的改进与性能分析

首先分析了影响MPI组通信性能的各方面因素,提出了一种衡量算法性能的模型。基于这种分析及模型,提出了一种将邻居交换和递归倍增两种算法结合的新的MPI_ALLGATHER实现算法。新的算法比邻居交换算法通信次数少,比递归倍增算法具有较好的通信局部性。通过在高性能机群系统中的测试,发现新算法在多种情况下比邻居交换算法具有更优的性能,在中等长度消息通信时具有最优的性能,在长消息通信时性能比递归倍增算法和Bruck算法的性能更优,且在长消息通信时多数情况下性能最优。     

基于MPI的大规模栅格影像并行瓦片化算法

当前主流GIS软件以及互联网地图应用在WebGIS（网络地理信息系统）解决方案中都广泛采用地图切片（又称瓦片）,切片处理服务是实现影像在WebGIS上快速无缝浏览的关键技术。针对目前传统算法以及商业GIS软件在大数据量栅格影像快速瓦片化方面的不足,提出一种名为ParaTile的高效栅格影像快速瓦片化方法,ParaTile基于MPI共享外存的并行技术,利用多进程对原始栅格影像进行数据划分,每个进程对其所划分的区域进行独立读写和计算,而后再按照TMS或者Google Tile定义的标准将瓦片进行编码输出。实验采用不同级别大小的遥感影像进行测试,结果表明ParaTile在面对不同规模的数据时,无论从速度还是算法稳定性上都较现有算法和工具具有显著优势,特别是当数据量越大时,这种优势愈加明显。     

高效RSA算法的研究与并行实现

RSA算法依赖于大数的运算,实现起来较为困难,并且对计算机速度、容量等要求较高。针对上述问题,提出一种有效的解决方案,即将大整数分解成小整数进行相乘以提高幂乘运算速度,并给出改进的负载均衡并行算法,进一步提高计算速度。实验结果表明,与传统的RSA算法相比,该算法在计算速度上有明显的提高,具有较好的可扩展性。