论文部分内容阅读
k-means算法是“数据挖掘十大经典算法”之一。随着当前互联网和信息科技的快速发展，各行各业产生的数据呈爆炸式增长，大数据时代的到来进一步推动了k-means算法的应用。在实际应用中，k-means算法存在如下缺点:1）k-means对初始聚类中心十分敏感，导致了不同的收敛速度和聚类结果;2）在处理大规模数据时，k-means算法执行时间过长。 针对k-means聚类中心初始化，现有的基于密度的初始化算法依赖于一些主观参数阈值，不稳定且适用性差。另一方面，针对k-means执行时间过长，现有的硬件加速方案主要集中在GPU和FPGA两个平台，大多的解决方案采用Slave-Master模式的异构平台，主从机之间大量的通信造成了性能瓶颈，带来了额外的功耗;同时片上资源限制了聚类的灵活性，只能满足固定个数的聚类需求。为解决上述问题，本文分别从聚类初始化和硬件加速方面提出了针对k-means算法的改进方案，主要的研究内容及研究成果为: 在聚类初始化方面，本文提出了一种改进的聚类中心初始化方法，该方法定义了结合密度和距离信息的密度距离积。基于该密度距离积，选择出高效稳定且唯一的初始化聚类中心，从而加快k-means算法的收敛速度。最后通过不同数据集上的仿真测试验证了所提算法的良好性能。 在硬件加速方面，结合k-means算法特点，分别设计了面向小规模和大规模聚类个数的硬件加速方案，解决了聚类个数的限制问题。该加速方案采用片上方式，利用在线更新技术解决了异构平台的大量主从机通信问题。最后通过模拟器平台实验分析了加速方案中各模块对加速性能的影响，通过FPGA平台验证了加速方案的可行性和正确性。通过与当前主流CPU平台对比，该加速方案实现了16.3x到26.7倍的加速比。