基于参考集索引的高效序列相似性查找算法

序列数据在文本、Web访问日志文件、生物数据库中普遍存在,对其进行相似性查找是一种重要的获取和分析知识的手段.基于参考集索引技术是一类解决序列相似性查找的有效方法,主要思想是找到序列数据库中的少数序列作为参考集,通过参考集过滤掉数据库中与查询序列不相关的数据,从而高效地回答查询.在现有基于参考集索引技术的基础上,提出一种过滤能力更强的序列相似性查询算法IRI(improved reference indexing).首先,充分利用了先前的查询结果集来加速当前的查询,其次考虑了基于序列特征的上界和下界,使得应用参考集进行过滤的上下界更紧,过滤能力进一步加强.最后,为了避免候选集中费时的编辑距离计算,则只计算前缀序列间的编辑距离,从而进一步加速算法运行.实验采用真实的DNA序列和蛋白质序列数据,结果表明,算法IRI在查询性能上明显优于现有的基于参考集索引方法RI(reference indexing).

基于分割的字符串相似性查找算法

字符串相似性查找问题主要包括两方面,基于阈值的字符串相似性查找以及top-k字符串相似性查找。目前处理基于阈值的字符串相似性查找问题的算法多是基于过滤-验证框架的。基于该框架提出了PBsearch算法,算法在过滤阶段首次加入One-Off条件过滤掉大量的无效匹配,并在验证阶段提出了一种新的验证算法MultiThreshold算法,大大减少了计算编辑距离的次数。在top-k字符串相似性查找问题方面,提出了两种基于分割思想的算法,Pb-topk算法和PbCount-topk算法。其中,Pb-topk算法采用差值递增的策略,减少了需处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模。最后,通过在3个真实数据集上的实验结果,验证了提出算法的高效性。

一种基于分形和相似性查找的非平稳时间序列符号化表示法

传统的时间序列表示方法均在不同程度上采用了对数据的约简手段,从而破坏了时间序列的非线性和分形这些重要的本质特征,也就使得时间序列的相似性匹配误差加大。提出一种高精度的随机非平稳时间序列表示方法FSPA,该方法将分形理论和R/S方法应用到现有的时间序列表示方法中,既保留了时间序列的非线性和分形的重要特征,同时也实现了维度的约简。实验分别在合成数据和实际数据上进行,结果表明,该方法具有更高的精度且需要较少的存储空间。

一种高效的基于相似性查找时间序列的位符号化表示方法

到目前为止能够计算字符化时间序列的距离度量的方法很少,为此,提出了一种新的字符化的时间序列表示方法BSAP。该方法既能进行维度约简又允许在符号化后的时间序列表示法上定义距离度量。实验分别在合成数据和实际数据上进行,实验表明该方法具有更高的运算效率且需要较少的空间。

基于回归系数的时间序列维约简与相似性查找

在时间序列中进行相似性查找往往需要进行维约简.以往的维约简方法或者时间复杂度太大并且不直观(如 DWT、DFT 等),或者无法用于准确的相似性查找(如 PAA 方法).本文提出一种新的基于回归系数的时间序列维约简方法——逐段回归近似(PRA).该方法具有线性时间复杂度,并且对均值平稳的独立噪声干扰不敏感,同时证明了基于 PRA 方法的相似性查找满足下界定理,因而是实用有效的.对实际数据的实验结果验证了本文的结论.

基于IRST的谱图相似性查找方法研究

光谱图相似性匹配是推测化合物结构的重要研究方法之一,而如何在标准谱图数据库中进行相似性查找是关键步骤。传统的谱图匹配方法在数据量较大时,检索效率较低。本文首次将互关联后继树(TRST)算法思想应用于光谱图数据领域,从光谱图特征数据点出发,通过对算法的改进,提出了1种基于斜率序列的互关联后继树算法(SSIRST)实现光谱图相似性匹配查找,旨在通过减少匹配过程中的数据量缩短查找时间。实验结果表明,算法可以有效提高光谱图相似性匹配查找效率1倍以上。

在时间序列相似性问题中滑动窗口的确定

作为一个非平凡命题,大多数时间序列相似性查找方法都涉及到了对原数据的维度简约。在保持原序列中有效信息量的同时,尽量降低计算复杂度是这些算法的关键。讨论滑动窗口在时间序列相似性降维技术中的实际应用,从中发现确定自适应滑动窗口大小的一种新方法。通过对时序特征值分布函数的挖掘,发现时间序列中的若干有效点,从而确定一组合适的滑动窗口大小,并根据序列变化的来决定最佳的滑动窗口。

时间序列相似性分析中滑动窗口宽度的确定

时间序列相似性查找作为一种非平凡问题,大多数有效的求解方法都涉及到对原数据维度的简约。在有效地保持原序列中信息量的前提下,尽可能降低计算复杂度是算法的关键所在。通过讨论滑动窗口在时间序列相似性降维算法中的实际应用情况,从中发现一种自适应确定滑动窗口宽度的新方法。通过对时序特征值分布函数挖掘,发现时间序列中的有效特征点,进而确定一组合适的滑动窗口宽度;最后根据序列的变化情况来决定最优的滑动窗口宽度,对原数据维度进行简约。

一种新的不确定性时间序列概率相似查找方法

针对传统的数据管理中的数据表示、存储与索引、查询与挖掘等所有技术,不能直接应用于不确定性时间序列数据的相似性查找的不足.研究了可用于不确定性时间序列数据的降维表示、索引与剪枝、查找等理论与技术,针对不确定性时间序列数据结构的复杂性,首次给出了不确定性时间序列上的概率最近邻的定义;将不确定性时间序列进行了PLA降维,转换到PLA空间,并提出了三个引理,用以加速查找效率;基于该三个引理,提出了概率K最近邻查找算法PKNNS.通过实验,验证了PKNNS算法的有效性和效率.

一种基于MBR的高效的时间序列表示方法

提出了一种基于最小边界矩形的新颖的时间序列表示方法(GMBR),该方法将网格的概念引入到MBR中,能够在保证低开小的情况下有效地提高查找的准确性,最后通过实验证明了该方法的有效性,实验分别在实际数据和合成数据上进行。结果表明该方法的剪枝率为69%～92%,高出MBR方法4%～9%。

基于列表监督的Hash排序算法

Hash学习技术目前被广泛应用于大规模数据的相似性查找中,其通过将数据转化成二进制编码的形式,同时提高查找速度和降低存储代价。目前,大多数Hash排序算法通过比较数据在欧氏空间和海明空间的排序一致性来构造损失函数,然而,在海明空间的排序过程中,因为海明距离是离散的整数值,可能存在多个数据点共享相同的海明距离,这样就无法准确地排序。针对这一问题,将编码后的数据切分成几个长度相同的子空间,并为每个子空间设置不同的权重,比较时,再根据不同的子空间权重来计算海明距离。实验结果表明,与其他Hash学习算法相比,本文算法能够有效地对海明空间中的数据进行排序,并提高查询的准确性。

基于J2EE平台应用时序挖掘算法对纺织品出口风险预测的研究

贸易数据是按时间记录下的、不断更新中的海量数据。首先引入时间序列模式的概念,分析了时间序列的本质问题;其次改进了AprioriAll算法挖掘贸易序列数据库的有用序列模式;然后使用离散傅里叶变换子序列相似性查找的方法,将现有序列与挖掘到的感兴趣的序列模式进行子序列匹配,得到有用的知识;最后结合实际情况,合理搭建系统平台,将改进的算法应用在该平台之下得到满意的效果。

Near-duplicate document detection with improved similarity measurement

To quickly find documents with high similarity in existing documentation sets, fingerprint group merging retrieval algorithm is proposed to address both sides of the problem:a given similarity threshold could not be too low and fewer fingerprints could lead to low accuracy. It can be proved that the efficiency of similarity retrieval is improved by fingerprint group merging retrieval algorithm with lower similarity threshold. Experiments with the lower similarity threshold r=0.7 and high fingerprint bits k=400 demonstrate that the CPU time-consuming cost decreases from 1 921 s to 273 s. Theoretical analysis and experimental results verify the effectiveness of this method.