基于网格筛选的大规模密度峰值聚类算法

密度峰值聚类算法(density peaks clustering algorithm,DPC)是2014年提出的一种新型聚类分析算法,它基于聚类中心局部密度大以及与密度更大点之间的距离较远两大特点绘制决策图寻找聚类中心,从而得到任意形状的簇.但在寻找聚类中心的过程中,求解局部密度以及高密度距离属性都依赖于相似度矩阵的计算,计算复杂度较高,限制了密度峰值聚类算法在大规模数据集中的应用.针对此不足,提出基于网格筛选的密度峰值聚类算法(density peaks clustering algorithm based on grid screening,SDPC),根据数据的不均匀分布,使用网格化方法去除部分密度稀疏的点,然后再使用密度峰值聚类算法中决策图的方法选取聚类中心,可以在保证聚类准确性的基础上有效降低计算复杂度.理论分析和实验测试表明:基于网格筛选的密度峰值聚类算法不仅可以对大规模数据集进行正确的聚类,还极大地降低了计算复杂度.

面向知识库问答的多注意力RNN关系链接方法

针对知识库问答场景中的关系链接任务,尤其是面向复杂问题的多关系链接任务,提出一种基于多注意力RNN模型的关系链接方法,该方法既适用于简单问题也适用于复杂问题.首先,在字符及词级别基础上通过Bi-LSTM模型学习问句的向量表示,利用条件随机场模型标注问句中的命名实体.基于词典生成候选实体,基于预定义规则实现候选实体消歧,将问句中命名实体指称链接到知识库中实体.然后,采用机器学习方法将问句分类为简单问题及复杂问题.从已识别实体出发,对于简单问题,在知识库中收集一跳关系作为候选关系;对于复杂问题,收集二跳关系作为候选.最后,采用多注意力Bi-LSTM模型对问句及候选关系进行编码,比较相似度,返回相似度最高的候选关系作为关系链接的结果.值得注意的是,对于简单问题采用带有一个注意力的Bi-LSTM模型,对于复杂问题则采用带有2个注意力的Bi-LSTM模型.实验结果表明:在有效的实体链接方法基础上,引入注意力机制的Bi-LSTM关系链接方法对于无论简单问题还是复杂问题效果都有所提升,且优于现有基于图算法或基于语言学的关系链接方法.

基于核心向量机的多任务概念漂移数据快速分类

通过协同求解多个概念漂移问题并充分挖掘相关概念漂移问题中蕴含的有效信息,共享矢量链支持向量机(shared vector chain supported vector machines,SVC-SVM)在面向多任务概念漂移分类时表现出良好性能。然而实际应用中的概念漂移问题通常有较大的数据容量,较高的计算代价限制了SVC-SVM方法的推广能力。针对这个弱点,借鉴核心向量机的近线性时间复杂度的优势,提出了适于多任务概念漂移大规模数据的共享矢量链核心向量机(shared vector chain core vector machines,SVC-CVM)。SVC-CVM具有渐近线性时间复杂度的算法特点,同时又继承了SVC-SVM方法协同求解多个概念漂移问题带来的良好性能,实验验证了该方法在多任务概念漂移大规模数据集上的有效性和快速性。

融合网格划分和DBSCAN的改进聚类算法

针对基于密度的噪声应用空间聚类算法(density based spatial clustering of applications with noise,DBSCAN)计算复杂度较高以及无法聚类多密度数据集等问题,提出了一种网格聚类算法和DBSCAN相结合的融合聚类算法(G_FDBSCAN)。利用网格划分技术将数据集划分为稀疏区域和密集区域,分而治之,降低计算的时间复杂度和采用全局参数引起的聚类误差;改进传统的DBSCAN聚算法得到FDBSCAN,将密集区域中网格聚类的结果作为一个整体参与后续的聚类,在网格划分基础上进行邻域检索,减少邻域检索和类扩展过程中对象的无效查询和重复查询,进一步减少时间开销。理论分析和实验测试表明,改进后的算法与DBSCAN算法、DPC算法、KMEANS算法、BIRCH算法和CBSCAN算法相比,在聚类结果接近或达到最优的情况下,聚类效率分别平均提升了24倍、11倍、2倍、3倍和1倍。

面向密度峰值聚类的高效相似度度量

针对密度峰值聚类(density peaks clustering,DPC)计算复杂度高的问题,提出一种面向密度峰值聚类的高效相似度度量(efficient similarity measure,ESM)法,通过仅度量最近邻之间的相似度构建不完全相似度矩阵。最近邻的选择基于一个随机第三方数据对象,无需另外引入参数。基于ESM法构建相似度矩阵,提出一种改进的高效密度峰值聚类(efficient density peaks clustering,EDPC)算法,在保持准确率的同时提高DPC识别聚类中心的效率。理论分析和试验结果表明,ESM法通过减少一定不相似的相似度,可以有效提高DPC及其改进算法基于K最近邻的密度峰值聚类(density peaks clustering based on K-nearest neighbors,DPC-KNN)和模糊加权K最近邻密度峰值聚类(fuzzy weighted K-nearest neighbors density peaks clustering,FKNN-DPC)的计算效率,具有较强的可扩展性。

基于双数据处理的双路冒泡排序策略

冒泡排序算法是一种易实现且稳定的计算机排序算法,但是由于该算法的时间复杂度较高,因此,冒泡排序不适用于大规模数据集。在本文中,我们提出了一种针对经典冒泡排序算法的改进方法-基于双数据处理的双路冒泡排序算法,该方法在每趟排序的过程中可以同时确定两个数据的位置,从而减少排序过程中所需的循环次数,以达到降低了算法的时间复杂度的目的。最终的仿真实验结果表明,双路冒泡排序算法是可行有效的,它显著地降低了冒泡排序过程中所需的数据比较次数和移动次数。