基于Spark的点排序识别聚类结构算法

点排序识别聚类结构(Ordering Points to Identify the Clustering Structure,OPTICS)的密度聚类算法能以可视化的方式导出数据集的内在聚类结构,并且可以通过簇排序提取基本的聚类信息。但是该算法由于时空复杂度较高,不能很好地适应当今社会出现的大型数据集。随着云计算和并行计算的发展,提供了一种解决OPTICS算法复杂度缺陷的方法和一种建立在基于Spark内存计算平台的点排序识别聚类结构并行算法。测试的实验结果表明,它能极大地降低OPTICS算法对时间和空间的需要。     

改进的OPTICS算法及其在文本聚类中的应用

基于密度的OPTICS聚类算法以可视化的结果输出方式直观呈现语料结构,但由于其结果组织策略在处理稀疏点时的局限性,算法实际性能未能得到充分发挥。本文针对此缺陷提出一种有效的结果重组织策略以辅助稀疏点的重新定位,并针对文本领域的特点改变距离度量方法,形成了OPTICS-Plus文本聚类算法。在真实文本分类语料上的实验表明,我们的结果重组织策略能够辅助算法产生更为清晰反映语料结构的可达图,与K-means算法的比较则证实了OPTICS-Plus具有较为良好的聚类性能。     

基于MapReduce的并行聚类算法设计与实现

针对目前聚类算法对大数据处理效率较低的问题,研究云平台上高效并行化的聚类算法十分必要。在HDFS分布式文件系统基础上,设计一种并行聚类算法P-ISODATA,利用MapReduce编程框架的执行机制将传统ISODATA聚类算法并行化,并在Map阶段之后加入Combine阶段以减少网络传输开销,进一步提高执行效率。实验从著名UCI机器学习库上选取若干数据集作为测试数据,分析了新并行算法P-ISODATA性能,结果表明基于P-ISODATA算法具有优良的加速比、数据伸缩率和扩展率,可以有效地应用于大规模数据的处理。     

基于MapReduce的并行k-modes算法

k-modes是一种代表性的分类数据的聚类算法.首先对k-modes聚类算法的实现过程进行了改进:通过在分配数据对象到簇时更新这个簇中各个属性项的次数,使得在遍历一次全部数据对象就能计算出新的簇中心.为了使k-modes能够处理大规模分类数据,在Hadoop平台上用MapReduce并行计算模型实现了k-modes算法.实验表明:在处理大量数据时,并行k-modes比串行k-modes极大地缩短了聚类时间,取得了较好的加速比.     

基于改进的OPTICS聚类和LOPW的离群数据检测算法

针对现有的离群数据检测算法时间复杂度过高,且检测质量不佳的不足,提出一种新的基于改进的OPTICS聚类和LOPW的离群数据检测算法。首先,使用改进的OPTICS聚类算法对原始数据集进行预处理,筛选由聚类形成的可达图得到初步离群数据集;然后,利用新定义的基于P权值的局部离群因子LOPW计算初步离群数据集中对象的离群程度,计算距离时引入去一划分信息熵增量确定属性的权重,提高离群检测准确性。实验结果表明,改进后的算法不仅提高了运算效率,而且提高了对离群数据检测的精确度。     

改进的OPTICS算法在调制识别中的应用

提出了一种基于星座聚类的调制识别新方法。该算法利用改进的OPTICS算法能准确发现数据集分布的特性,不仅克服了模糊C-均值聚类算法对初始聚类中心、样本输入次序敏感等不足,而且能够同时发现不同密度的聚类,结合聚类有效性分析实现了聚类中心目的自适应调整,同基于DBSCAN的聚类算法相比,降低了时间复杂度。将该算法用于对MPSK/MAPSK信号星座重构和识别,实验结果表明该方法是实际有效的。     

一种基于网格与加权信息熵的OPTICS改进算法

针对现有OPTICS算法时间复杂度高且不适用于数据密集型环境的问题,提出一种基于网格与加权信息熵的改进算法。将数据集合划分为一定数量的网格单元,引入加权信息熵,自适应计算每个网格单元的最小密度阈值。对满足最小密度阈值的网格单元定义密集格的概念,利用质心点代替网格数据点集的方法对数据点进行压缩。采用Geolife Trajectories数据集对算法性能进行测试,从理论分析和实验结果两方面证明了改进算法的有效性。     

EDDPC：一种高效的分布式密度中心聚类算法

聚类分析是数据挖掘中经常用到的一种分析数据之间关系的方法.它把数据对象集合划分成多个不同的组或簇,每个簇内的数据对象之间的相似性要高于与其他簇内的对象的相似性.密度中心聚类算法是一个最近发表在《Science》上的新型聚类算法,它通过评估每个数据对象的2个属性值(密度值ρ和斥群值δ)来进行聚类.相对于其他传统聚类算法,它的优越性体现在交互性、无迭代性、无数据分布依赖性等方面.但是密度中心聚类算法在计算每个数据对象的密度值和斥群值时,需要O(N\\+2)复杂度的距离计算,当处理海量高维数据时,该算法的效率会受到很大的影响.为了提高该算法的效率和扩展性,提出一种高效的分布式密度中心聚类算法EDDPC (efficient distributed density peaks clustering),它利用Voronoi分割与合理的数据复制及过滤,避免了大量无用的距离计算开销和数据传输开销.实验结果显示:与简单的MapReduce分布式实现比较,EDDPC可以达到40倍左右的性能提升.     

基于OPTICS可达图的自动识别簇方法

针对主题特征不明显的搜索结果聚类的问题,提出了基于OPTICS(Ordering Points To Identify theClustering Structure)可达图的自动识别簇的Smooth方法。首先利用OPTICS算法得到搜索结果的可达图,然后采用移动平均法平滑掉可达图曲线中的毛刺,最后识别其中的峰值以划分各个凹陷区域,即得到聚类结果。在搜索结果数据集上的实验结果表明,Smooth方法的准确率较已有的方法平均提高了100%左右。Smooth方法能够与OPTICS算法结合应用于搜索引擎中,对搜索结果进行聚类处理,有效地提高其可浏览性。     

FATOC: Bug Isolation Based Multi-Fault Localization by Using OPTICS Clustering

Bug isolation is a popular approach for multi-fault localization (MFL), where all failed test cases are clustered into several groups, and then the failed test cases in each group combined with all passed test cases are used to localize only a single fault. However, existing clustering algorithms cannot always obtain completely correct clustering results, which is a potential threat for bug isolation based MFL approaches. To address this issue, we first analyze the influence of the accuracy of the clustering on the performance of MFL, and the results of a controlled study indicate that using the clustering algorithm with the highest accuracy can achieve the best performance of MFL. Moreover, previous studies on clustering algorithms also show that the elements in a higher density cluster have a higher similarity. Based on the above motivation, we propose a novel approach FATOC (One-Fault-at-a-Time via OPTICS Clustering). In particular, FATOC first leverages the OPTICS (Ordering Points to Identify the Clustering Structure) clustering algorithm to group failed test cases, and then identifies a cluster with the highest density. OPTICS clustering is a density-based clustering algorithm, which can reduce the misgrouping and calculate a density value for each cluster. Such a density value of each cluster is helpful for finding a cluster with the highest clustering effectiveness. FATOC then combines the failed test cases in this cluster with all passed test cases to localize a single-fault through the traditional spectrum-based fault localization (SBFL) formula. After this fault is localized and fixed, FATOC will use the same method to localize the next single-fault, until all the test cases are passed. Our evaluation results show that FATOC can significantly outperform the traditional SBFL technique and a state-of-the-art MFL approach MSeer on 804 multi-faulty versions from nine real-world programs. Specifically, FATOC’s performance is 10.32% higher than that of traditional SBFL when using Ochiai formula in terms of metric A-EXAM. Besides, the results also indicate that, when checking 1%, 3% and 5% statements of all subject programs, FATOC can locate 36.91%, 48.50% and 66.93% of all faults respectively, which is also better than the traditional SBFL and the MFL approach MSeer.

     

基于MapReduce并行化计算的大数据聚类算法

面对大数据规模庞大且计算复杂等问题,基于MapReduce框架采用两阶段渐进式的聚类思想,提出了改进的K-means并行化计算的大数据聚类方法。第一阶段,该算法通过Canopy算法初始化划分聚类中心,从而迅速获取粗精度的聚类中心点;第二阶段,基于MapReduce框架提出了并行化计算方案,使每个数据点围绕其邻近的Canopy中心进行细化的聚类或合并,从而对大数据实现快速、准确地聚类分析。在MapReduce并行框架上进行算法验证,实验结果表明,所提算法能够有效地提升并行计算效率,减少计算时间,并提升大数据的聚类精度。     

Binary-Positive下的并行化CURE算法

当CURE算法在处理不均匀的海量数据时,针对随机抽样不具有代表性的问题,提出了一种健壮的并行化改进算法。该算法使用Binary-Positive算法得到原始数据的有效属性,并利用MapReduce并行框架对有效数据进行层次聚类,从而实现了正确率与效率的一种权衡。实验分析表明,改进后的CURE算法具有更高的执行效率,且聚类效果良好。     

基于传感器聚类数据挖掘的物联网智慧医疗模型设计

现代智慧医疗需要操作简洁、反应迅速,能够提供智慧诊断的信息化平台,提出基于物联网无线传感器技术的智慧医疗模型。系统利用附着在患者身上的各类传感器采集到的生理信息数据,采用基于密度的带有噪声的空间聚类(DBSCAN)算法的数据分析方法,用非线性映射把患者的生理信息数据转换到高纬度的特征空间,对变换后的矢量数据进行聚类分析,从而提升聚类结果并有效辅助医务人员进行诊断。     

基于Storm的流数据KNN分类算法的研究与实现

KNN算法是一种简单、有效且易于实现的分类算法,可用于类域较大的分类。近年来对KNN算法的研究偏向于静态大数据集,不过,在越来越多的情况下要用KNN算法在线实时处理流数据。考虑到流式数据流量大,连续且快速,不易存储和恢复等特性,以及流处理系统Storm对流数据处理具有实时性、可靠性的特点,提出了基于Storm的流数据KNN分类算法,该算法首先对整个样本集进行划分,形成多个片集,然后计算出待分类向量在各片集上的[K]近邻,最后再将所有片集[K]近邻归约得出整体[K]近邻,实现待分类向量的分类。实验结果表明,基于Storm的流数据KNN分类算法能够满足大数据背景下对流数据分类的高吞吐量、可扩展性、实时性和准确性的要求。     

基于分组和IGSA的并行密度聚类算法

针对并行密度聚类算法在处理大数据集时存在伸缩困难、参数寻优能力不佳、并行化效率较低等问题,提出一种基于分组和重力搜索优化算法(improve gravitational search algorithm,IGSA)的并行密度聚类算法(densi-ty-based clustering algorithm based on groups and improve gravitational search,MR-GDBIGS).首先,该算法设计了基于图形的分组策略(grouping strategy based on pattern,GSP)来有效划分数据,加速邻域搜索,解决了处理大数据集时伸缩困难的问题;其次,在局部聚类中提出基于位置更新函数(position update function,PUF)的重力搜索优化算法,动态寻找局部聚类中的最优参数,提升了局部聚类的效果;最后,提出基于覆盖树的并行局部簇合并策略(cluster merging strategy by using MapReduce,MR-CTMC),在实现局部簇并行化合并的同时加快了合并局部簇的收敛速度,提升了算法整体的并行化效率.实验结果表明,MR-GDBIGS算法在处理大数据时的聚类效果更佳,且并行化性能更好.     

基于网格密度和局部敏感哈希函数的并行化聚类算法

针对大数据背景下基于划分的聚类算法中存在初始中心敏感,节点间通信开销大以及集群效率低下等问题,提出了基于网格密度和局部敏感哈希函数的PBGDLSH-MR并行化聚类算法。首先,对初始数据集提出网格密度策略(GDS)获取初始中心点,有效避免了随机选取引起的初始中心敏感的问题;其次,提出基于局部敏感哈希函数的数据分区(DP-LSH)用于投射关联性较大的数据对象到同一子数据集中,得到map上的数据分区,并设计相似性度量公式(SI)对数据分区结果进行评价,从而降低了节点间的通信开销;接着设计自适应分组策略(AGS)处理数据分区中数据倾斜的问题,进而有效地提高了集群效率;最后,结合MapReduce计算模型并行挖掘簇中心,生成最终聚类结果。实验结果表明,PBGDLSH-MR算法的聚类效果更佳,同时在大数据环境下能有效地提高并行计算的效率。     

基于划分DBSCAN算法的小区载频配置优化

为了充分利用无线网络资源,提升无线网络质量,充分利用了DBSCAN（Density Based Spatial Clustering of Applications with Noise）算法的优点,提出基于划分DBSCAN算法的话务量异常小区的检测方法,并通过对现网大量话务数据的统计分析,找出小区载频配置数和最佳话务量之间的关系。对话务量异常、拥塞率高的小区进行载频配置优化,并对城市小区网络优化有一定的指导意义。     

基于MapReduce和改进密度峰值的划分聚类算法

对于基于划分的聚类算法随机选取初始聚类中心导致初始中心敏感,聚类结果不稳定、集群效率低等问题,提出一种基于MapReduce框架和改进的密度峰值的划分聚类算法(based on MapReduce framework and im-proved density peak partition clustering algorithm,MR-IDPACA).首先,通过自然最近邻定义新的局部密度计算方式,将搜索样本密度峰值点作为划分聚类算法的初始聚类中心;其次针对算法在大规模数据下运行时间复杂,提出基于E2LSH(exact Euclidean locality sensitive hashing)的一种分区方法,即KLSH(K of locality sensitive hashing).通过该方法对数据分区后结合MapReduce框架并行搜寻初始聚类中心,有效减少了算法在搜索初始聚类中心时的运行时间;对于MapReduce框架中的数据倾斜问题,提出ME(multistage equilibrium)策略对中间数据进行多段均衡分区,以提升算法运行效率;在MapReduce框架下并行聚类,得到最终聚类结果.实验得出MR-IDPACA算法在单机环境下有着较高的准确率和较强的稳定性,集群性能上也有着较好的加速比和运行时间,聚类效果有所提升.     

基于关联分区和ST-GCN的人体行为识别

基于骨骼的动作识别因不受人体物理特征的影响,简单清晰地传达了人体行为识别的重要信息而受到广泛关注.传统的应用程序骨架建模通常依赖遍历规则的人为设置而导致表达能力有限和推广困难.因此,在近年来热门的时空图卷积网络(ST-GCN)模型基础上提出了一种新的划分骨架关节点的分区策略.该策略相比于原始分区方法加强了身体相对位置之...