最长公共子序列算法在程序代码相似度度量中的应用

阐述了最长公共子序列算法在程序代码结构相似度度量中的应用,列举了两种计算最优值和一种获取最长公共标识符子序列的算法.根据最优值得到结构相似度值,进而可以查找出结构相似程序对.最后探讨了程序代码相似度的实际应用.     

带约束最长公共子序列快速算法

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.     

利用矩阵搜索求所有最长公共子序列的算法

利用动态规划法求出二维数组的情况下,使用矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法．该算法将通常认为的指数量级的时间复杂度降低到了max{O（cmn）,O（ck）}．随后对此算法的正确性以及效率做了证明．     

采用改进最长公共子序列的人名消歧

将名词、形容词、动名词和命名实体作为文本特征,考虑词序与词频,结合特征项的语义,提出一种基于改进最长公共子序列的文本聚类(LCSC)方法.实验结果表明:相对于传统的余弦值聚类方法,LCSC方法在人名消歧的P-IP指标上,F平均值由74.2%提高到了84.9%;相对于最长公共子序列方法,总体性能也提高了3.7%.     

基于滑动窗口的时间序列离群数据挖掘

离群数据挖掘是数据挖掘中的重要内容.本文针对时间序列数据进行离群数据挖掘方法的研究.在引入了基于局部离群点因子的离群数据挖掘方法与时间序列上滑动窗口基础上,将二者相结合,提出了基于滑动窗口的时间序列离群数据挖掘算法,并将算法应用于海表温度数据得到海表温度的异常之处.     

基于滑动窗口的奇异点数据挖掘算法研究

在一条时间序列上与其它序列点存在显著差异的点,被称为奇异点.提出了一种基于滑动窗口的奇异点挖掘算法,该算法利用局部异常因子检测的方法检测出时间序列中的奇异点,再利用移动平均模型对奇异点的趋势进行判断,这样能更直观的看出奇异点对时问序列趋势的影响.通过对证券信息点和上证指数收盘点数构成的时间序列进行分析,结果表明该算法的...     

基于随机部署RP的位置指纹定位算法

随着人们对位置信息需求的不断增加,室内定位技术迎来了前所未有的研究热潮.在分析影响基于位置指纹定位算法性能主要因素的基础上,提出了基于随机部署参考点(RP)的位置指纹定位算法.该方法首先将目标环境划分成多个子区域,在每个子区域中采用随机方式部署RP,从而减少定位成本、提高灵活性;为了在保证定位性能的前提下缩短定位时间,给出了两种数据剔除方法.仿真结果表明,该方法能够获得良好的定位性能,具有实际的应用价值.     

基于公共子序列的OPSM双聚类算法

OPSM作为一种基于模式的双聚类方法,被广泛应用于基因数据矩阵的分析上.在一个OPSM聚类中,形成聚类的若干基因在特定的条件子集下具有一致的表达模式,其中隐含着基因的关联调控信息,对基因数据矩阵进行双聚类分析具有生物学意义.其中,Deep OPSM 是OPSM 聚类中行数少列数多的特殊聚类.根据OPSM模型,该文提出了一种快速有效的精确性算法,用于挖掘分散在基因数据矩阵中的OPSM聚类.首先寻找基因数据矩阵中任意两行的公共子序列,然后利用STL map对找到的公共子序列进行支持度统计,并将符合支持度阈值的OPSM聚类输出,且通过阈值的设置即可输出Deep OPSMs.结果证明该算法能够快速地找到符合条件的Deep OPSMs.通过P-value值分析,验证了找到的Deep OPSM具有明显的生物学意义.     

基于3DCNN的CSI-cluster室内指纹定位算法

针对室内环境中复杂的多径效应影响定位精度问题,提出一种基于3维卷积神经网络(3 dimensional convolutional neural network,3DCNN)多径程度划分的自校准指纹定位算法。该算法利用MeanShift方法分析定位区域内每一个采样点的信道状态信息数据分布特性,得到其可代表多径效应程度的簇类数量,结合阈值原则将指纹库划分为2种不同多径程度的子库,从而减少多径程度差异较大的指纹点对后续定位影响利用3DCNN深度学习2类指纹子库。在定位阶段,根据校准算法判断待测数据所属子库,并采用相应的3DCNN模型估计位置。通过仿真实验验证,该方法在保证指纹库构建合理性和高效性的同时,在定位精度方面实现了明显的提升,优于与之对比的相关算法。     

复合滑动窗口连接算法

滑动窗口是对数据流进行连续查询处理、得出近似查询结果的一种常用的数据采样技术．连续查询处理的执行方式有2类：一类是立即执行方式；一类是周期执行方式、在已有的研究工作中，基于滑动窗口的连接算法都是适用于立即执行的连续查询．提出了适用于周期执行的连续查询的复合滑动窗口连接算法，即CSWSNLJ算法和CSWSNHJ算法．理论分析和试验结果表明CSWSNHJ算法具有较好的性能．     

滑动时间窗算法关键参数研究

滑动时间窗算法主要涉及窗体大小、步长和位置交换范围三个参数,这三个参数对算法的有效性和效率都有非常重要的影响。为了寻求这三个参数对算法的具体影响和最优组合,首先对算法的复杂度进行了分析和评估;而后探索和总结了这三个参数之间的关系;最后,在设计和实现该算法的基础上,通过仿真找到了实时性约束条件下,优化效果最好时三个参数的取值,即窗口大小为7,移动步长为3,交换范围约束为4时,计算结果最好。通过大量的数据验证了在最优参数组合下算法的有效性,为科学地使用滑动时间窗算法提供了依据。     

基于偏度-峰度检验的WLAN位置指纹室内定位算法

目前,无线局域网（Wireless Local Area Networks,简称WLAN）技术因其成本低、配置简单、精度高等特点,被认为是室内定位的最佳选择之一。虽然WLAN接收信号强度指标(Received Signal Strength Indicator,简称RSSI)指纹法是最精确的定位方法,但由于其无线电地图(Radio Map,简称RM)在发生环境变化时已经过时,具有很大的缺陷,且重新校准RM是一个耗时的过程。因此,本文提出基于偏度-峰度检验进行WLAN位置指纹室内定位算法改进。在离线阶段,通过偏度-峰度检验样本总体是否服从高斯分布,对于严重偏离高斯分布的样本直接舍去,而对于与高斯分布接近的样本,利用核函数估计其概率密度。在线阶段,利用K最近邻(K-Nearest Neighbor,简称KNN）,将移动终端设备接收到的RSSI与建立的指纹数据库中的RSSI,通过欧几里得公式计算样本点到观测点的欧氏距离,并从中选择欧氏距离最短的样本点的位置作为研究位置的无偏估计。通过实验结果,本文提出的算法比传统定位算法的精度提高了11%,证明了该算法具有更高的定位精度和更少的离线工作量等优点,而且在RSS(Received Signal Strength)信号容量较小时该算法的定位误差比其他算法更小,具有显著的稳定性。     

基于滑动时间窗的机场流量优化分配

针对机场实际运行过程中飞行流量需求以及机场容量动态变化的特点,将滑动时间窗概念应用到机场飞行流量分配问题中,提出了一种基于滑动时间窗的机场流量动态优化分配方法。对基于滑动时间窗的流量优化分配原理进行了阐述,该方法采用不断进行的动态流量分配代替静态的一次性流量分配,能够实时得到当前时间段最优化的流量分配方案,为机场战术流量管理提供决策支持。实例计算表明：基于滑动时间窗的机场流量优化分配方法在动态环境中能够较好地达到实时优化分配飞行流量目的,而静态流量分配方法不适用于动态环境,文中方法实用有效。     

基于双向窗口特征提取技术的车道线检测算法

为提高车道线检测算法的准确性与稳定性, 提出一种基于双向窗口特征提取技术的车道线检测算法。融合运用Hough 变换与边缘分布函数技术得到车道线的直线特征点; 运用双向窗口特征提取技术获得所有车道线特征点, 包括直线部分与弯曲部分。获得直线与双曲线相结合的车道线模型: 在近视场, 应用直线车道线模型能获得较好的鲁棒性; 在远视场, 使用双曲线模型可有效检测出车道线的弯曲部分。实验结果表明, 相较于已有的车道线检测算法, 该方法可有效提高多种场景下车道线检测的准确性和稳定性。     

应用时间滑动窗口模型的轨迹相似性研究

针对社交网络用户个人信息难以获取、公开信息不完整、不通用甚至内容虚假的问题，选择了普适性强，且能客观、真实反映用户行为习惯的位置数据作为相似性分析依据，对新浪微博、滴滴打车进行位置数据采集，形成两个高价值且具有国内网民特色的数据集作为实验对象.提出了一种基于时间滑动窗口模型的轨迹相似性匹配算法，通过调整时间窗口和位置距离优化算法F值，实现不同网络平台用户的相似性分析.以对新浪微博和滴滴打车的用户位置数据为例进行验证，实验结果证明了地理位置为虚拟身份相似性判断的正相关影响因子，且判断相似性的平均F值超过90%.      

基于双自适应滑动时间窗滚动轴承故障预测模型

针对传统方法和基于神经网络方法在滚动轴承故障预测中存在的问题,提出一种双自适应滑动时间窗故障预测模型。首先,通过设置能够去除相关性的状态估计非线性算子,将滚动轴承振动信号映射为能够表征其退化状态的故障特征—故障程度指标DR。其次,以损失函数为判据,设置模型参数自适应更新机制,以及建立能够自适应选取数据长度的滑动时间窗口。最后,通过西安交通大学发布的滚动轴承全寿命周期数据,模拟实际中突发性故障和渐发性故障综合作用下的故障发生情况,验证了所提出的故障预测模型的有效性。实验结果表明,提出的预测模型能够准确判断滚动轴承退化阶段的开始时刻和故障时刻,真实反映滚动轴承性能退化的趋势,预测误差仅为0.068%,预测时间仅占2次故障间隔时间的1.385%,满足复杂工况下滚动轴承故障预测的需求。     

一种基于滑动窗口的一趟数据流聚类算法

在海量的动态数据流中发现有价值的知识,是数据挖掘技术研究的重要问题.研究数据流聚类,根据数据流的特点,提出了一种基于滑动窗口的一趟数据流挖掘的算法,对原有的一趟数据流聚类算法进行了改进,增强了一趟数据流聚类算法的扩展性,改进了数据流聚类的质量.     

基于字符串匹配和直方图分析的视频镜头检测算法研究

首先介绍了现有典型切变检测算法,然后提出一种改进的镜头切变检测算法,在字符串匹配算法的基础上用直方图法来进行二次检测.实验显示,这种方法解决了单独用字符串匹配算法造成的误检问题,取得了较好的镜头切变检测效果.