基于状态子集编码的快速DFA构造算法

网络深度包检测等网络应用广泛采用正则表达式匹配技术检测网络中的传输内容,正则表达式用非确定性有限自动机(NFA)或者确定性有限自动机(DFA)实现.网络应用对匹配速度要求很高,相比NFA,DFA具有确定性的匹配速度,但所有基于DFA的方法需要预先从NFA构造一个与之等价的DFA,于是DFA的构造成为系统瓶颈之一.为此通过深入探索自动机内在运行特性———NFA状态间活跃关系和NFA中导致DFA空间膨胀的因素,设计了一种NFA状态子集的编码方法和查询方法,显著减少了DFA构造过程中状态子集的查询代价.基于入侵检测与防护系统Snort中的真实规则集的实验表明,与传统的子集构造算法相比,该方法减少了88.33%~93.57%的DFA构造时间.     

确定型有穷状态自动机的同态压缩

对于确定型有穷状态自动机(DFA),通过定义状态集上的等价关系≈Q,借助于等价关系,可以在平方时间内构造出接受相同语言的极小化自动机.本文在DFA之间引入同态关系,证明了同态压缩下DFA接受相同语言.     

快速构建目录树的算法研究

通常使用DFA和ITA算法构造目录树,分别对这两种算法进行了时间复杂性分析,16组实验结果表明DFA算法快于ITA算法.     

确定有穷状态自动机最小化算法的三点说明

确定有穷状态自动机最小化可提高词法分析程序的效率.本文简述了最小化的概念、算法,从基本概念出发分析了该算法初始分划如何构造,及在状态无后继和全部由终止状态构成时这两种特殊情况下的解决对策,并对原算法做了进一步的细化.     

基于规则分组的DFA正则表达式匹配算法

模式匹配因误报率低和漏报率低被入侵检测所采用.在使用正则表达式构造DFA时,因状态爆炸导致匹配算法需要较多的存储空间和运行时间,算法效率低下,采用规则分组后,可以在一定程度上抑制状态爆炸问题.根据缓存中的历史记录对正则表达式进行分组,既能利用规则分组减少状态总数,抑制状态爆炸,又能减少因每次重新构建DFA所带来的开销,...     

基于非线性拟合方程的多变量决策树算法

根据数据属性间存在的线性相关和非线性相关影响决策树性能的特点,提出了一种用拟合回归建立决策树的算法,并利用这种相关性来提高分类能力.该算法选择了一个较优的属性子集,对此子集中的属性进行加权组合,用于构造决策树的节点,采用二次多项式来拟合两个属性间可能存在的相关性,从而构造出分类能力更强的决策树.研究中用UCI标准数据集对各种算法进行测试及比较,实验结果及分析表明此决策树算法具有良好性能.     

基于连通图动态分裂的聚类算法

当前大部分的聚类算法都难以处理任意形状和大小、存在孤立点和噪音以及密度多变的簇,为此,文中提出了一种基于连通图动态分裂的聚类算法.首先构造数据集的l-连通图,然后采用动态分裂策略对l-连通图进行分割,把数据集分成多个互不相连的连通图子集,每个连通图子集为一类.实验结果表明,所提出的算法能够有效地解决任意形状和大小、存在孤立点和噪音以及密度多变的簇的聚类问题,具有广泛的适用性.     

基于Apriori算法的改进关联规则的算法研究

关联规则是数据挖掘的一个重要研究内容,主要用于从大量数据集中挖掘出有价值的数据项之间的关联关系.典型案例是超市的购物篮分析,主要对顾客的购买记录数据库进行关联规则挖掘,可以发现顾客的购买行为.本文依据Apriori算法的两个基本性质,即任何大项集的子集一定是大项集,非大项集的超集一定是非大项集,对经典的Apriori算法要多次扫面事务数据库的问题,作了一些改进,并进行仿真计算,结果表明,改进的算法确实减少了扫描次数.     

快速构建目录树的算法研究

通常使用DFA和ITA算法构造目录树,本文分别对这两种算法进行了时间复杂性分析,16组实验结果表明DFA算法快于ITA算法。     

F-score结合核极限学习机的集成特征选择算法

特征选择是高维小样本癌症基因数据分析的首要和关键步骤,但是现有特征选择算法存在特征子集依赖于训练样本且随训练样本不同而变化的问题。为了解决特征选择过程的特征子集不稳定问题,提出一种基于核极限学习机的集成特征选择方法,利用5-折交叉验证划分原始数据,对各训练集继续采用5-折交叉验证进行划分并进行特征选择,以所得5个特征子集之并集作为该训练集的特征子集,构造核极限学习机评价该特征子集的分类性能,以原始数据集5-折交叉验证所得特征子集的平均Jaccard系数评价特征选择算法所选特征子集的稳定性。5个基因数据集的实验测试以及与经典特征选择算法SVM-RFE、LLE Score、ARCO、DRJMIM、Random Forest和mRMR的实验比较表明,本文算法不仅能选择到稳定的特征子集,且所选特征子集具有很好的泛化能力。     

非确定型有穷自动机的极小化

利用自动机状态集上的等价关系对自动机的状态集进行极小化, 从而得到与原自动机功能等价的极小化自动机. 通过两台确定型有穷自动机（DFA）的连接, 构造一台非确定型有穷自动机（NFA）. 利用这两台确定型有穷自动机状态集上的等价关系, 可以构造这台非确定型有穷自动机状态集上的等价关系, 从而对这台非确定型有穷自动机进行极小化. 结果表明这台非确定型有穷自动机的极小化自动机的状态复杂 度, 不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度; 并且自动机在等价关系基础上进行极小化时不改变识别语言.     

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

对DFA最小化算法等价性问题的探讨与改进

有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义。利用自动机状态集上的等价关系对自动机的状态集极小化,从而得到与原自动机功能等价的极小化自动机,该内容是词法分析的重点。很多编译原理书籍介绍的DFA最小化算法是＂分割法＂,但该算法存在一定的问题,本文从对一些特殊的DFA的处理入手,分析＂分割法＂算法在等价原则方面的漏洞,并提出了对最小化问题的改进算法。     

一个有效的LR(K)分析机的分级构造算法及其文法的分划

本文提出了一个上下文无关文法的LR(k)分析机的分级构造算法及其文法的分划方法。并对K=1的情况进行了详细的讨论。该方法不仅适用于任何实际LR(K)文法并且较之[5]中方法更加有效。文中对算法的正确性进行了证明,同时指出由本文建立的强相容性标准是所有合并同心状态的相容性标准中最宽的一个。根据获得的结果。用本文中算法构造的LR(K)分析机中的状态个数与LALR(K)分析机中的状态个数相同或略多。     

线性子空间的并集完全不覆盖的基

在n维线性空间V中,对于有限个真子空间的并集M,都存在V的一个无穷子集U使得M完全不能覆盖U,并且U中的任何的n个元都是V的基。在不可数数域上的n维线性空间V中,对于可数个真子空间的并集M,都存在V的一个无穷子集U使得M完全不覆盖U,并且U中的任何的n个元都是V的基。在n维欧氏空间V中,对于可数个真子空间的并集M,都存在V的一个可数的无穷子集所作成的序列U,使得M完全不覆盖U,并且U中含有V的标准正交基,U中任何的,n个相连的元都是V的基；对于任何的正整数m,V有m个标准正交基完全不被M覆盖。     

一种新的粗糙集与支持向量分类机算法

用支持向量机的机器学习是依据结构风险最小化原则,序列最小优化(SMO)是较特殊的分解算法。对高维大样本对象,支持向量机训练算法面临耗时增大与维数灾问题,利用粗糙集(RS)对不确定数据处理能力,提出一种新的粗糙集与支持向量分类机算法RS-SMO,可以对数据集做属性约简,生成类边界集作为SMO的训练子集,比原始训练集的维数与规模大小都有一定程度的减少,可构造出具有较好时空性能的算法。用两个实用数据对象做仿真,实验结果表明算法RS-SMO比SMO的性能有大的提高,实现了结构风险最小化。     

一种快速的Wrapper式特征子集选择新方法

Wrapper式特征选择方法需要耗费大量时间,为此提出了一种快速的Wrapper式特征选择新方法(Fast Feature Subset Ranking,简称FFSR).与以单个特征作为评价单位的传统方法不同,FFSR算法以特征子集作为评价单位,以子集收敛能力作为评价标准.FFSR算法从收敛速度和收敛极值两个方面对收敛能力进行分析,并利用Sequential Floating Forward Selection(简称SFFS)算法构造和评价快速收敛的子集.FFSR算法选择的特征子集能力接近SFFS算法,但所需时间较SFFS算法大幅度减少.     

基于粗糙集与支持向量机的分类算法

针对高维大样本环境下支持向量机训练算法面临界的耗时增大与维数灾问题,将序列最小优化算法(SMO)与粗糙集(RS)的数据处理功能相结合,提出一种新的基于粗糙集与支持向量机的分类算法RS.SMO.该算法依据属性的重要性对数据集作属性约简,用粗糙边界集法生成类边界集作为SMO的训练子集,使训练集比原始训练集的维数与规模都有一定程度的减少,可构造出具有较好时空性能的算法.实验结果表明,RS-SMO算法能实现结构风险最小化,且性能优于SMO算法.     

N_+~d上某些族的动力学性质

一个正整数集+的子集S称作是一个强迫回归集,若对于任何一个动力系统(X,f)及X的任何一个紧致子集K,只要X中有一点x满足{fnx|nS}K,则K中必含有f的某个回归点.该文对d+(d+)的子集引入回归时间集的概念,讨论了由回归时间集所构成的族的几个特征,并且给出了它们的一个简单应用.     

基于主动学习的有监督在线多核学习算法

为了提高大规模数据的分类性能,提出一种基于主动学习的有监督在线多核学习算法SOMK_AL(Supervised online multiple kernel learning algorithm based active learning).首先,采用主动学习的方法缩减数据规模.通过训练生成两个分类器,对读入数据xt进行预测,将两个分类器预测类别不一致的数据作为信息含量高的有标记数据,参与在线学习过程中的核更新;接着,在核集成过程中,通过随机抽样的方法构造核函数集的子集,仅仅在子集中实现核更新,缩减核更新的计算规模.最后,在大规模数据的基准数据集上进行实验,对提出的算法的有效性进行评估,结果表明SOMK_AL能较好地提高数据的分类性能.