2005, 16(12):2029-2035.
摘要:概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用.概念格的构造在其应用过程中是一个主要问题.提出了一种基于搜索空间划分的概念生成算法SSPCG(search space partition based concepts generation),它将属性集合的幂集看作初始闭包搜索空间,迭代地将每个搜索空间划分为一些子搜索空间,并引入了子搜索空间的有效性判断,只搜索那些能生成正规闭包的子搜索空间,有效地提高了搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度.由于所有子搜索空间是独立的,所以该算法可以很容易地扩展为并行算法.在随机生成的数据集和真实数据集上进行的实验测试表明,本算法的时间性能要优于Ganter提出的NextClosure算法.
2005, 16(12):2036-2044.
摘要:分析了变异操作对微粒群算法(particle swarmoptimization,简称PSO)的影响,针对收敛速度慢、容易陷入局部极小等缺点,结合生物界中物种发现生存密度过大时会自动分家迁移的习性,给出了一种自适应逃逸微粒群算法,并证明了它依概率收敛到全局最优解.算法中的逃逸行为是一种简化的确定变异操作.当微粒飞行速度过小时,通过逃逸运动使微粒能够有效地进行全局和局部搜索,减弱了随机变异操作带来的不稳定性.典型复杂函数优化的仿真结果表明,该算法不仅具有更快的收敛速度,而且能更有效地进行全局搜索.
2005, 16(12):2045-2053.
摘要:NKI(国家知识基础设施)是一个大规模知识库,它用框架来表示本体中的概念,用Hom逻辑程序作为自动推理.给出NKI中的本体、框架和逻辑理论的形式表示以及形式表示之间的转换,并证明如果将本体、框架和逻辑理论看作是3个范畴,则这些转换是这3个范畴之间的函子.这个结果保证了在NKI中,基于Horn逻辑程序的推理关于用本体和框架表示的知识库是正确的.
2005, 16(12):2054-2062.
摘要:最近邻分类方法中对距离机制的研究大都集中在根据何种计算方法将不同属性取值的差异集中起来,而未考虑到同一属性间取值的语义差异所带来的影响;而且传统算法的分类准确率对于不同抽象层次描述的数据集带来的数据不完整性相当敏感.针对这两个问题,提出一种基于语义距离的最近邻分类方法SDkNN(semantic distance based k-nearest neighbor).该方法分析了同一属性内取值的语义差异,说明了如何基于领域本体计算语义距离,并将其应用到kNN算法中.经过在UCI数据集以及实际应用数据集中验证,SDkNN的整体性能要优于传统方法,在数据不完整的情况下效果更为明显,实践证明,SDkNN有较好的应用价值.
2005, 16(12):2063-2079.
摘要:对XML数据建立有效的索引,是左右XML数据处理性能的重要因素.深入地讨论了目前XML索引技术的研究现状,将XML索引技术分为两大类:节点记录类索引(本身还可以分为3个小的类型)和结构摘要类索引.根据XML数据查询处理效率以及XML数据修改对XML索引的要求,讨论了相关XML索引方法的优点和不足,并归结出XML索引后续研究的3个方向:XML结构信息的获取,路径信息的多维处理,数据修改合法性的有效支持,以及涉及能够同时有效满足XML查询和信息获取的索引.
2005, 16(12):2080-2088.
摘要:个性化服务技术为数字图书馆的研究带来一些新的挑战.如何描述用户的偏好以及如何使数字图书馆支持偏好查询是有待研究的一个问题.人们已经提出了基于偏序关系的用户偏好模型,并针对关系数据提出了一系列偏好构造方法.数字图书馆中的数据是半结构数据.半结构数据上用户偏好的描述比关系数据复杂得多.偏序模型无法有效地表达数字图书馆中的用户偏好.提出基于ontology的新的用户偏好模型,用ontology来描述数字图书馆中的文本和文本上的偏好.该模型能够充分表达用户偏好的结构和语义,并提供了复杂的偏好操作,能够有效地支持数字图书馆中的个性化检索和推荐操作.
2005, 16(12):2089-2098.
摘要:目前数据流的研究成果主要集中在分析处理存储于内存中的最近一段时间内的数据流数据,忽略了对数据流历史数据的分析处理与存储管理.提出了一种数据流历史数据的存储管理及聚集查询处理方法,通过对历史数据实施多层递阶抽样存储,并在内存中建立存储数据流历史数据聚集值的HDS-Tree索引,实现对无限数据流历史数据的存储管理,有效地支持各种聚集查询同时,还给出了基于HDS-Tree的聚集查询算法的时间复杂性分析和查询误差分析.理论分析与实验结果表明,该方法可以有效地用于数据流历史数据的存储与分析.
2005, 16(12):2099-2105.
摘要:在现有的数据流频繁模式挖掘算法中,批处理方法平均处理时间短,但需要积攒足够的数据,使得其实时性差且查询粒度粗;而启发式方法可以直接处理数据流,但处理速度慢.提出一种改进的字典树结构--IL-TREE(improved lexicographic tree),并在其基础上提出一种新的启发式算法FPIL-Stream(frequent pattem mining based on improved lexicographic tree),在更新模式和生成新模式的过程中,可以快速定位历史模式.算法结合了倾斜窗口策略,可以详细记录历史信息.该算法在及时处理数据流的前提下,也降低了数据的平均处理时间,并且提供了更细的查询粒度.
2005, 16(12):2106-2116.
摘要:提出了一种分布式的高效节能的传感器网络数据收集和聚合协议DEEG.此协议中节点自主地根据其剩余能量以及邻居节点的信号强度来竞争簇头,同时为了减小簇头节点的能量开销,簇头之间以多跳方式将收集到的数据发送到指定的簇头节点,然后通过该节点将整个网络收集的数据发送到基站.此外,该协议还提出了一种简单的簇覆盖方法,使得当节点密度提高时,传感器网络寿命相应于节点数量呈线性增长.实验证明,在没有使用簇覆盖方法的情况下,DEEG协议与其他两种数据收集和聚合协议(LEACH,PEGASIS)相比,在最好情况下,其网络寿命分别提高达1800%和300%,并且由于DEEG协议使得所有节点集中于最后40轮内全部死亡(网络寿命定义为最后一个节点死亡),因此,使用DEEG协议的传感器网络其监测结果具有很高的可靠性.
2005, 16(12):2117-2123.
摘要:针对核心路由器端口的输入、输出流量的变化,用改进的CUSUM(cumulative sum)算法对其统计特性进行实时监控,检测网络流量异常.基于路由器多端口的特点,提出了矩阵式的多统计量CUSUM算法(M-CUSUM),并提出了可调的参数设定体系,以提高准确性.M-CUSUM算法通过对输入、输出端口流量的绝对差与和之比进行统计,实时地监控其均值的偏移情况.通过对该算法在计算机中的模拟实现,验证了该算法对DOS/DDOS攻击具有较高的检测速度和精度,且系统开销小,已成功运行在软件路由器之上.
2005, 16(12):2124-2131.
摘要:TCP友好拥塞控制是保证实时媒体流和组播业务在Internet广泛应用的关键技术.基于收端TCP模拟方案TEAR(TCP emulation at receivers),提出了一个根据丢包类型和当前拥塞周期的持续时间动态调整加权平均参数的拥塞控制机制,称为自适应TCP友好拥塞控制方案ATFCC(adaptive TCP-Friendly congestion control).仿真结果表明,ATFCC方案在速率平滑程度和TCP友好性方面的性能优于TCP友好速率控制协议TFRC(TCP-Friendly rate control).
2005, 16(12):2132-2138.
摘要:复合攻击是网络入侵的主要形式之一.如何检测复合攻击是当前入侵检测研究的一个重要方向.这项研究对入侵检测的作用主要表现在以下几个方面:(1)减少误报和漏报;(2)实现对未知攻击的检测;(3)攻击预测.尤其是第3点,可能使被动的检测发展为主动的有针对性的防御.经过对复合攻击模式的大量研究,提出了一种基于入侵意图的复合攻击检测和预测算法.该算法采用扩展的有向图来表示攻击类别及其逻辑关系,按照后向匹配和缺项匹配的方式对报警进行关联,根据已关联攻击链的累计权值和攻击逻辑图中各分支的权值计算其可能性.该算法可以实现复合攻击的检测,在一定程度上预测即将发生的攻击,并且对未知攻击有一定的检测能力,还可以大幅度地减少误报和一定的漏报.最后介绍了相应的实验过程和结果分析,证明了算法的有效性.
2005, 16(12):2139-2149.
摘要:在具有星际链路的低地球轨道(LEO)卫星网络中,高度动态的网络拓扑和受限的星上资源为其路由协议设计带来很大的挑战.提出了一种简洁的星上分布式路由协议ODRP来应对这种挑战.在ODRP协议中,单层LEO星座被作为双层星座处理.根据星际链路动态特性和流量分布情况,各轨道面内位于一定位置的卫星节点被选作为轨道面发言人,从而实现简洁的分布式分层路由.实验结果表明,ODRP能够适应网络拓扑的动态变化,保证路由最优.尤其是在高负载情况下,能够有效降低分组丢失率.通过复杂性分析得知,与其他星上路由机制相比,ODRP具有较低的通信开销、计算开销和存储开销.
2005, 16(12):2150-2156.
摘要:1998年,Guttman等人提出了串空间理论作为一种新的密码协议形式化分析的工具.并在1999年第1次引入了关于消息代数上的理想以及诚实的概念来分析协议的保密性.由于理想结构的特殊性使得它可以刻画协议运行中消息之间的关系.利用理想的结构来分析协议的一些安全性质,例如保密性、认证性、零知识性以及如何抵抗猜测攻击.
2005, 16(12):2157-2165.
摘要:构件需要在其复用期间进行持续的优化改进和重构,消除设计需求与复用需求之间的差异,在保证有用性的前提下改善可用性.为此,提出一种面向复用成本优化的、基于局部性原理与实例集分解的构件重构方法.首先给出一种基于特征的构件模型,着重探讨基于可变点的复用机制,并在此基础上研究构件复用成本的构成要素、优化策略与优化目标,即通过提高构件固定部分的比例降低复用成本.探讨了构件复用过程中存在的时间/空间局部性,依据构件实例复用频度的差异,将具有高复用频度的实例分离出来形成(半)实例化构件,以降低构件复用过程中的实例化成本与实现成本.进而提出一种基于贪心策略的构件实例分解算法实现近似最优化,并通过实例验证其有效性.该方法通过将构件特征间依赖关系分解为构件实例间依赖关系,将构件的部分实例化工作由复用阶段提前到设计阶段来完成,将若干可变特征转化为固定特征,从而避免了构件频繁复用时的多次实例化,以降低复用成本.
2005, 16(12):2166-2171.
摘要:软件开发实践中存在的隐合成分和无法回避的"不够完美",就是现实软件开发项目中的无法控制或未知部分,这违反现存的大部分软件开发方法的基础,如一致性.完美球却是基于二重性,把微观世界的一些成分和复杂系统相映射.这是探索先进的西方科学技术和古代东方哲学的产物.分析由"陈述","思想"和"客观事实"组成的三角形,以说明完美点相区别的三角形.分布系统的测不准关系阐明:代码(代表可用产品)和目标(代表软件产品的性能)不能同时确定.在解释软件系统与人体间的联系中表明在气功哲学概念和软件开发概念之间可建立的某种映射关系.在完美球范畴下的软件开发强调生动活跃的学习行为,而不仅看重的自动机行为.用完美球替代特定目标点或动态可修改的目标点.系统复杂性日益增加,逐步减少概率论和预定计划影响.列举完美球少许应用.
2005, 16(12):2172-2180.
摘要:提出了一种由体系结构描述驱动的基于约束求解的微处理器体系结构级测试程序自动生成的新方法,并基于此开发了原型系统--MA2TG(microprocessor architectural automatic test program generator).该系统不仅可以随机生成测试程序,最主要的是可以产生针对特定要求的测试程序.其优点在于:首先,通过体系结构语言描述简化了体系结构建模,方便了对目标处理器体系结构的探索;第二,利用比较成熟的约束求解技术来生成满足需求的测试程序;第三,极大地缩减了测试程序的大小以及微处理器的验证时间.MA2TG已应用于DLX处理器和自主开发的EStar嵌入式微处理器的验证.实验结果表明了此方法的有效性.
2005, 16(12):2181-2189.
摘要:高速网络设备一般需要大容量高速数据包存储器来缓存收到的数据包.但以目前的存储器工艺水平很难实现这样的存储器,从而限制了整个网络的发展.提出一种新型的三级存储阵列结构可以成功解决数据包存储器的容量和带宽问题,理论上可以实现任意高速数据包的缓存.使用"最关键队列优先"算法完成对三级存储阵列的管理,证明了使用该算法能够保证数据包的无时延调度输出,并且其所需的系统规模最小,同时推导出系统规模的上、下限.最后给出三级存储阵列的一种可实现方案,从而使该结构易于硬件实现.