基于密度峰值和网络嵌入的重叠社区发现

密度峰值是一种基于密度的聚类算法,该算法假设类簇中心点具有较高的密度且被密度较小的节点包围.由于图结构的性质,密度峰值无法直接适用于网络结构,现有的基于密度峰值的社区发现算法大部分是基于图的拓扑结构或者邻接矩阵度量节点近似度,这种方法往往引入较大的计算复杂度.文中结合网络嵌入方法通过低维向量表示网络中的节点信息,提出了...     

一种大规模稀疏中国邮递员问题快速求解方法

针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进：首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割;其次根据邻近节点覆盖率对分割后的节点群进行合并;最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明：在奇偶点图上作业法所能支持的节点规模下,该方法可求得与确定性算法相同的最优解,并在运算时间上达到约10倍的效率优化;且该方法在大规模稀疏路网图下可有效提高计算效率,并在可控时间范围内得到优化的可行解,针对5 000个节点规模的路网图最快可在60 s内完成求解.     

一种面向高维数据的密度峰值聚类模型

聚类是大数据时代对海量数据进行数据挖掘与分析的重要工具.本文基于密度峰值聚类算法提出了针对高维数据的聚类模型,以直接简单的形式实现六维度以上数据的任意形状聚类.该模型实现了自动预处理过程,以局部密度较大且距离其他局部密度较大点较远的点作为聚类中心,最后引入参数调整.实验结果表明,该模型不仅对低维数据聚类实用,在高维数据的聚类效果也非常显著.     

基于密度万有引力改进的引力峰值聚类算法

针对密度峰值聚类算法（DPC）中存在的截断距离难以确定、局部密度定义单一的问题，本文提出了一种基于密度万有引力改进的引力峰值聚类算法（DG-DPC算法）。该算法使用相互K近邻的方法对相似性度量和局部密度进行了重新定义，然后将引力参数引入到DPC算法中，并通过新的相对局部密度与引力参数的倒数作出决策图选取簇中心，对数据集中的点进行分配。仿真实验表明，DG-DPC算法对于人工合成数据集和UCI数据集都有效，且准确率相对于基于相对密度优化的密度峰值聚类算法（RE-DPC算法）、DPC算法、基于间隙自动中心检测的密度峰值聚类算法（GAP-DPC算法）分别平均提高了31.07%、21.60%、17.20%。     

最短路径算法在高速公路联网收费中的研究及应用

Floyd算法求任意2点间距离时间复杂度等同于Dijkstra算法,现行高速公路路网由环路和射线路段组成,当路网节点多时,两种算法单独操作计算速度慢。基于Floyd计算环路效率高,Dijkstra计算稀疏图的射线路段效率高的特性,本文结合Floyd和Dijkstra算法来计算高速公路路网任意2节点间最短路径。用VC＋＋设计模拟出路网中2点间（一对点）的最短路径,并对算法复杂度进行分析。     

基于量子计算加速的DDC算法

考虑到量子计算具有超强的并行计算能力,拟引入量子计算以降低局部密度和delta距离度量的聚类算法(DDC)计算复杂度。DDC算法的局部密度求解过程是计数算法,提出利用量子计数算法加速局部密度的求解;delta距离是最小值查找的过程,提出利用最小值查找量子算法加速delta距离的求解。研究结果表明:利用量子计算对DDC聚类算法进行加速,能够使算法的执行效率获得显著提升。     

一种基于密度峰值发现的文本聚类算法

提出一种基于密度峰值发现的文本聚类算法,将文本的距离与密度计算转化为文本向量的相似度计算,实现基于密度峰值发现的文本聚类算法。该算法采用空间向量模型表示文本,用余弦公式进行相似度计算,然后求得每个文本的密度和距离。剔除噪音点后,选取聚类中心,将剩下的非中心点划分到距离其最近的聚类中心所在的类簇中去。通过多组对比试验,验证了本方法的可靠性和鲁棒性。     

基于K-短路径的路网关键路段集合的辨识与分析

为了提高高速公路网络化运营监管与公众服务的水平,需要准确可靠地辨识出综合多种因素的关键路段,采用交通分配理论及K-短路径算法研究了路网运行关键路段集的辨识问题。综合考虑路网结构、交通需求影响、出行行为特征等多方面因素,以系统内所有用户的旅行时间为交通网络性能度量指标,建立了路网运行关键路段评价模型;考虑多路段失效的联合效应,提出了路段集的重要度评估模型及其求解算法。该模型相对于传统的结构可靠性模型,考虑了出行者路径选择行为影响和多路段失效的联合效应,更符合路网运行管理的实际需求。研究结果表明:在相同交通需求的OD对之间,结构密度较低的区域,被选中为关键路段集的概率大;合理的K取值得到的关键路段集与全路网分配所得结果相近,可有效提升计算效率;多路段失效情况下,路段的联合效应明显。     

基于反向K近邻和密度峰值初始化的加权Kmeans聚类入侵检测算法

传统Kmeans聚类算法的性能易受初始类簇中心随机性和类簇中心计算的迭代过程中边缘点和离群点反复计入的影响，为了避免这些影响，该文提出一种基于反向K近邻和密度峰值初始化的加权Kmeans聚类算法。通过样本的近邻信息计算每个样本的反向K近邻，针对不同规模、不同密度分布数据集，可以自适应地搜索密度峰值点作为初始类簇中心；自适应设定相对簇半径，并通过样本加权进行类簇中心迭代，在不同数据分布下可以有效降低边缘点和离群点对聚类结果的影响。试验结果证明，该算法在聚类性能提升的同时迭代次数大幅降低，随着入侵行为类型和数据规模的增加，该文聚类算法仍体现出较好的性能，且在发现未知攻击类型上效果显著。     

基于K近邻和多类合并的密度峰值聚类算法

针对密度峰值聚类（DPC）算法在处理结构复杂、 维数较高以及同类中存在多个密度峰值的数据集时聚类性能不佳的问题, 提出一种基于K近邻和多类合并的密度峰值聚类（KM-DPC）算法. 首先利用定义的密度计算方法描述样本分布, 采用新的评价指标获取聚类中心; 然后结合K近邻思想设计迭代分配策略, 将剩余点准确归类; 最后给出一种局部类合并方法, 以防将包含多个密度峰值点的类分裂. 仿真实验结果表明, 该算法在22个不同数据集上的性能明显优于DPC算法.     

基于连通性的三支密度峰值聚类算法

为了解决密度峰值聚类算法选择密度峰值点困难以及误分配的问题，基于流形的连通性，提出了一种改进的密度峰值聚类算法。通过使用三支密度峰值聚类算法，得到初始聚类结果与簇的边界点，根据这些边界点之间的连通性判断初始聚类之间的连接情况，并利用这些信息进行聚类结果融合。重复上述过程，每次迭代中在剩余数据里寻找密度峰值候选点，并将其纳入聚类过程，得到一种对流形数据友好的聚类算法。结果表明，所提算法在人工数据集和真实数据集上均有较好的表现，聚类准确度相较现有算法更高。基于连通性的三支密度峰值聚类算法可以在不计算路径距离的前提下，有效识别流形数据，大大降低了计算成本。     

基于交通指数聚类的路网区域动态划分

针对宏观路网区域交通状态预报需要首先产生路网区域的需求,提出了一种新的基于交通指数聚类的路网区域动态划分方法。首先对整个城市路网进行网格化划分,将路段划分为从属于某个网格的子路段;然后,计算每个网格的交通指数,提取网格特征,从而得到样本特征矩阵;接着,利用k-means~(++)聚类算法对样本特征矩阵进行聚类,得到初始聚类标签,并对其中奇异网格的聚类标签加以修正;最后,得到划分后的路网区域。为了验证该方法的性能,利用上海市的GPS数据对上海市进行了路网区域的划分,并与不同聚类方法的结果进行了对比。结果表明,新方法对路网区域划分的精度及稳定性均有所提高。     

局部标准差优化的密度峰值聚类算法

密度峰值聚类(clustering by fast search and find of density peaks, DPC)算法是一种基于密度的聚类算法,它可以发现任意形状和维度的类簇,是具有里程碑意义的聚类算法。然而,DPC算法的样本局部密度定义不适用于同时发现数据集的稠密簇和稀疏簇;此外,DPC算法的一步分配策略使得一旦有一个样本分配错误,将导致更多样本的错误分配,产生“多米诺骨牌效应”。针对这些问题,提出一种新的样本局部密度定义,采用局部标准差指数定义样本局部密度,克服DPC的密度定义缺陷;采用两步分配策略代替DPC的一步分配策略,克服DPC的“多米诺骨牌效应”,得到ESDTS-DPC算法。与DPC及其改进算法KNN-DPC、FKNN-DPC、DPC-CE和经典密度聚类算法DBSCAN的实验比较显示,提出的ESDTS-DPC算法具有更好的聚类准确性。     

城市交通路网数据模型的构建及其拓扑结构的研究

基于图论的思想,根据节点、路段和转向这三个主要的网络要素构建了一个城市交通路网模型,并将其抽象成带转向的赋权有向图.同时,通过一个含4节点、8路段的示例路网着重研究了交通路网拓扑结构的五种表达方式.研究表明,路网拓扑结构的表达方式不能单靠各方法的时间空间复杂度来决定,还需权衡问题求解算法的特点.     

基于加权直觉模糊兰氏距离的密度峰值聚类算法

利用传统的聚类算法对直觉模糊集进行聚类分析时,存在对异常值敏感、复杂度较高的问题,不适用于大规模直觉模糊数据的聚类。针对上述问题,提出了一种基于密度峰值思想和加权兰氏距离的直觉模糊聚类算法（WIFDPL）,用来提高算法对直觉模糊数据的检测精度,降低算法的复杂度。由于现有直觉模糊距离算子不满足距离度量的定义,提出了一种新的直觉模糊兰氏距离算子,减少了数据的偏移程度,降低了对异常值的敏感程度;由于凝聚型层次聚类算法复杂度较高,采用密度峰值聚类算法对直觉模糊集进行聚类,显著提高了算法的运行效率。实验结果表明,利用改进的直觉模糊兰氏距离提高了聚类精度,且新算法复杂度较低,更适用于大规模直觉模糊集的聚类。     

基于灰色模糊聚类法的路网路面使用性能评价

以路网内各组成路段的路面性能评价指标灰色关联分析结果为基础,借鉴灰色关联分析在模糊聚类理论中的应用方法,建立了路网路面使用性能评价模型.确定了灰色相似关系矩阵,并利用最大树法,得到了基于不同水平的聚类结果形成的谱系图,较为合理地反映了路网路面基本性能和状况分布.     

密度峰值聚类算法研究现状与分析

密度峰值聚类(Clustering by Fast Search and Find of Density Peaks, DPC)算法是一种新型的基于密度的聚类算法,通过选取自身密度高且距离其他更高密度点较远的样本点作为聚类中心,再根据样本间的局部密度和距离进行聚类。一方面,虽然DPC算法参数唯一、简单、高效,但是其截断距离的取值是按经验策略设定,而截断距离值选取不当会导致局部密度和距离计算错误;另一方面,聚类中心的选取采用人机交互模式,对聚类结果的主观影响较大。针对DPC算法的这些缺陷,目前的改进方向主要有3个：改进截断距离的取值方式、改进局部密度和距离的计算方式以及改进聚类中心的选取方式。通过这3个方向的改进,使得DPC过程自适应。本文对DPC算法的自适应密度峰值聚类算法的研究现状进行比较分析,对进一步的工作进行展望并给出今后的研究方向：将DPC算法与智能算法有机结合实现算法自适应,对于算法处理高维数据集的性能也需要进一步探索。     

物流配送中心选址数学模型的研究和优化

为解决县域农村物流配送中心的选址问题,综合现实路网信息和农村网点吞吐量等要素,建立基于实际公路网的农村物流配送中心选址优化模型,通过基于图论的理论方法建立了物流网点的交通网络赋权图,确定各网点间的最短路径,进而使用基于弗洛伊德算法的迭代重心法建立配送中心的初始模型。在初始模型的基础上,打破行政区域的划分,建立基于密度峰值聚类算法的物流配送中心的双目标优化模型。     

基于方差优化谱聚类的热点区域挖掘算法

为改善交通拥堵的情况,本文利用聚类分析方法对移动轨迹数据进行挖掘,识别居民出行的热点区域。传统的Ng-Jordan-Weiss （NJW）谱聚类算法常使用K-means聚类算法来实现最后的聚类操作,然而K-means聚类算法存在对初始值敏感、容易陷入局部最优的缺陷,影响对热点区域的挖掘结果。因此,本研究将方差优化初始中心的K-medoids聚类算法运用到谱聚类算法最后聚类阶段,提出基于方差优化谱聚类的热点区域挖掘算法（Hot Region Mining algorithm based on improved K-medoids Spectral Clustering,HRM-KSC）,然后在真实的轨迹数据集上进行试验。试验结果发现,HRM-KSC算法聚类结果的轮廓系数更高,表明HRM-KSC算法改善了NJW谱聚类算法,提高了聚类质量。     

基于KL散度的密度峰值聚类算法

快速搜索与发现密度峰值聚类(clustering by fast search and find of density peaks, DPC)算法对聚类中心点进行了全新的定义,能够得到更优的聚类结果。但该算法需要手动选取聚类中心,容易出现多选、漏选聚类中心的问题。提出一种自动选取聚类中心的密度峰值聚类算法。将参数积γ引入新算法以扩大聚类中心的选取范围,利用KL散度的差异性度量准则对聚类中心点和非聚类中心点进行清晰划分,以Dkl排序图中的拐点作为分界点实现了对聚类中心的自动选取。在人工以及UCI数据集上的实验表明,新算法能够在自动选取聚类中心的同时,获得更好的聚类效果。