2009年 第46卷 第7期
摘要:
容迟网络泛指那些由于节点移动、能量管理、调度等原因而出现频繁中断、甚至长时间处于中断状态的一类网络.它涵盖了由于节点调度而处于间歇式连通的无线传感网络、移动Ad hoc网络、周期性连通的卫星网络、乡村网络、野生动物追踪网络以及个人设备交换网络等等,具有十分广阔的应用前景,引起了广泛的关注.与传统网络相比,容迟网络没有稳定的端到端传输路径,因而其路由问题更为复杂.已有的研究工作也主要集中于这一问题,并提出了许多的容迟网络路由算法.对这些算法的最新进展进行了综述.首先,介绍了容迟网络路由算法的性能评价标准.其次,给出了容迟网络路由算法的分类方法.按照路由策略来分,容迟网络路由算法可以分为基于复制策略的算法和基于转发策略的算法.按照网络模型来分,容迟网络路由算法又可以分为面向主动移动模型的算法和面向被动移动模型的算法.然后,针对每一分类,重点综述了其中具有代表性的一些容迟网络路由算法,并总结了各算法的优缺点.最后,讨论了未来的研究方向.
容迟网络泛指那些由于节点移动、能量管理、调度等原因而出现频繁中断、甚至长时间处于中断状态的一类网络.它涵盖了由于节点调度而处于间歇式连通的无线传感网络、移动Ad hoc网络、周期性连通的卫星网络、乡村网络、野生动物追踪网络以及个人设备交换网络等等,具有十分广阔的应用前景,引起了广泛的关注.与传统网络相比,容迟网络没有稳定的端到端传输路径,因而其路由问题更为复杂.已有的研究工作也主要集中于这一问题,并提出了许多的容迟网络路由算法.对这些算法的最新进展进行了综述.首先,介绍了容迟网络路由算法的性能评价标准.其次,给出了容迟网络路由算法的分类方法.按照路由策略来分,容迟网络路由算法可以分为基于复制策略的算法和基于转发策略的算法.按照网络模型来分,容迟网络路由算法又可以分为面向主动移动模型的算法和面向被动移动模型的算法.然后,针对每一分类,重点综述了其中具有代表性的一些容迟网络路由算法,并总结了各算法的优缺点.最后,讨论了未来的研究方向.
摘要:
传感器网络应用通常部署在如地下停车场、煤矿井下通道等条件复杂的环境中.这种复杂环境使短距离无线通信变得低效.早期传感器网络通信协议更多关注网络连通问题,较少考虑信道特性对协议的影响.随着对短距离无线链路特性认识的加深,人们尝试使用如链路估计、不相交多路径、缠绕多路径等机制提高网络抵达率和能量效率.通过模型分析了基于ARQ的多链路传输机制,给出该机制优于单链路的充分条件,同时分析了冲突对于网络效率的影响,并通过NS2验证模型分析的各项结论.
传感器网络应用通常部署在如地下停车场、煤矿井下通道等条件复杂的环境中.这种复杂环境使短距离无线通信变得低效.早期传感器网络通信协议更多关注网络连通问题,较少考虑信道特性对协议的影响.随着对短距离无线链路特性认识的加深,人们尝试使用如链路估计、不相交多路径、缠绕多路径等机制提高网络抵达率和能量效率.通过模型分析了基于ARQ的多链路传输机制,给出该机制优于单链路的充分条件,同时分析了冲突对于网络效率的影响,并通过NS2验证模型分析的各项结论.
摘要:
作为一种重要的主动队列管理手段,PI控制器算法通过积分器的引入有效地消除了队列长度控制的稳态误差,在提高网络吞吐的同时缩短了排队时延.但是PI控制器不能根据网络状态变化而自动调整控制参数,故当网络流量变化时PI控制器的收敛速度很慢.基于TCP-AQM系统模型,对经过中间节点的活动连接数、平均往返时间和前向链路容量等3个参数进行估计.通过计算击中概率的倒数,估计出活动流数;通过计算单位时间的数据包数,估计出网络容量;通过往返时延、活动流数、网络容量以及丢包概率在稳态时的关系式,估算出平均往返时延.在此基础上,提出了对网络状态变化自适应调整控制参数改进的快速收敛PI算法——FCPI算法.仿真结果表明,该算法有效提高了算法的收敛速度,并且鲁棒性好,易于实现,适用于未来高速网络的路由器.
作为一种重要的主动队列管理手段,PI控制器算法通过积分器的引入有效地消除了队列长度控制的稳态误差,在提高网络吞吐的同时缩短了排队时延.但是PI控制器不能根据网络状态变化而自动调整控制参数,故当网络流量变化时PI控制器的收敛速度很慢.基于TCP-AQM系统模型,对经过中间节点的活动连接数、平均往返时间和前向链路容量等3个参数进行估计.通过计算击中概率的倒数,估计出活动流数;通过计算单位时间的数据包数,估计出网络容量;通过往返时延、活动流数、网络容量以及丢包概率在稳态时的关系式,估算出平均往返时延.在此基础上,提出了对网络状态变化自适应调整控制参数改进的快速收敛PI算法——FCPI算法.仿真结果表明,该算法有效提高了算法的收敛速度,并且鲁棒性好,易于实现,适用于未来高速网络的路由器.
摘要:
IEEE 802.16作为全球微波接入互操作系统技术标准,虽然定义了5类信流(分别是UGS,rtPS,ertPS,nrtPS和BE),并将服务质量支持机制引入媒体接入控制层,却没有规定相应的调度算法.为有效保证各种多媒体通信的服务质量,提出了一种基于正交频分多址接入技术和自适应调制编码机制的二级调度方案.该调度方案采用跨层设计思想,适用于PMP WiMAX网络下行链路中.一级调度器按照QoS优先级顺序调度位于不同类型缓存器的队头分组,从而满足rtPS业务的最大时延限定和nrtPS业务的最小速率要求;完成一级调度后,为满足用户速率公平性,二级调度器根据自适应调制编码信息及用户状态信息调度位于不同用户缓存器的队头分组.仿真结果表明该方案能够有效保证各种多媒体通信服务满足QoS要求并兼顾用户速率公平,同时也可获得较高的WiMAX系统吞吐量.
IEEE 802.16作为全球微波接入互操作系统技术标准,虽然定义了5类信流(分别是UGS,rtPS,ertPS,nrtPS和BE),并将服务质量支持机制引入媒体接入控制层,却没有规定相应的调度算法.为有效保证各种多媒体通信的服务质量,提出了一种基于正交频分多址接入技术和自适应调制编码机制的二级调度方案.该调度方案采用跨层设计思想,适用于PMP WiMAX网络下行链路中.一级调度器按照QoS优先级顺序调度位于不同类型缓存器的队头分组,从而满足rtPS业务的最大时延限定和nrtPS业务的最小速率要求;完成一级调度后,为满足用户速率公平性,二级调度器根据自适应调制编码信息及用户状态信息调度位于不同用户缓存器的队头分组.仿真结果表明该方案能够有效保证各种多媒体通信服务满足QoS要求并兼顾用户速率公平,同时也可获得较高的WiMAX系统吞吐量.
摘要:
IEEE 802.11s WLAN Mesh没有定义客户端的漫游认证协议,并且其初始接入认证协议EMSA中,申请者和认证者的认证密钥是通过认证服务器产生的,所以申请者和认证者之后的所有通信完全可以被认证服务器获取.同时该协议中的基于共享密钥的认证方式不能保证前向保密性,一旦长期密钥丢失,由其保护的所有通信内容都将被泄露.在EMSA的基础上,利用三方Diffie-Hellman密钥交换和单独认证载荷技术提出了客户端漫游接入认证协议.该协议不但克服了上述缺陷,而且只需要4轮的协议交互便可以实现上述三者之间的相互认证和密钥确认,不需要4步握手进行密钥确认.并且新的协议将基于签名的认证方式和基于共享密钥的认证方式统一于单独的认证载荷,这样认证方式的改变并不影响认证协议的结构.最后对新的协议进行了可证明安全分析和NS2性能仿真,结果表明:新的协议是通用可组合安全的,并且性能优于现有协议.
IEEE 802.11s WLAN Mesh没有定义客户端的漫游认证协议,并且其初始接入认证协议EMSA中,申请者和认证者的认证密钥是通过认证服务器产生的,所以申请者和认证者之后的所有通信完全可以被认证服务器获取.同时该协议中的基于共享密钥的认证方式不能保证前向保密性,一旦长期密钥丢失,由其保护的所有通信内容都将被泄露.在EMSA的基础上,利用三方Diffie-Hellman密钥交换和单独认证载荷技术提出了客户端漫游接入认证协议.该协议不但克服了上述缺陷,而且只需要4轮的协议交互便可以实现上述三者之间的相互认证和密钥确认,不需要4步握手进行密钥确认.并且新的协议将基于签名的认证方式和基于共享密钥的认证方式统一于单独的认证载荷,这样认证方式的改变并不影响认证协议的结构.最后对新的协议进行了可证明安全分析和NS2性能仿真,结果表明:新的协议是通用可组合安全的,并且性能优于现有协议.
摘要:
由于良性蠕虫可以主动地防御蠕虫的传播,因此引起了蠕虫研究领域专家的广泛关注.通过分析分而治之的混合型良性蠕虫的特点,将其划分为3个子类.在有延迟以及无延迟的情况下,推导了分而治之的混合型良性蠕虫的3个子类的数学传播模型,这些传播模型描述了分而治之的混合型良性蠕虫对抗蠕虫传播的过程.最后,仿真实验验证了传播模型,并且得到如下结论:在相同的感染条件下,复合的分而治之的混合型良性蠕虫抑制蠕虫传播的效果最好.
由于良性蠕虫可以主动地防御蠕虫的传播,因此引起了蠕虫研究领域专家的广泛关注.通过分析分而治之的混合型良性蠕虫的特点,将其划分为3个子类.在有延迟以及无延迟的情况下,推导了分而治之的混合型良性蠕虫的3个子类的数学传播模型,这些传播模型描述了分而治之的混合型良性蠕虫对抗蠕虫传播的过程.最后,仿真实验验证了传播模型,并且得到如下结论:在相同的感染条件下,复合的分而治之的混合型良性蠕虫抑制蠕虫传播的效果最好.
摘要:
在科学计算中,稀疏矩阵向量乘(SpMV)是一个十分重要且经常被大量调用的计算内核.由于SpMV一般实现算法的浮点计算和存储访问次数比率非常低,且其存储访问模式极为不规则,其实际运行性能往往很低.通过采用寄存器分块算法和启发式分块大小选择算法,将稀疏矩阵分成小的稠密分块,重用保存在寄存器中向量x元素,可以提高该计算内核的性能.剖析和总结了OSKI软件包所采用的若干关键优化技术,并进行了实际应用性能测试.测试表明,在实际应用这些优化技术的过程中,应用程序对SpMV的调用次数要达到上百次的量级,才能抵消由于应用这些性能优化技术所带来的额外时间开销,取得性能加速效果.在Pentium 4和AMD Athlon平台上,测试了10个矩阵,其平均加速比分别达到了1.69和1.48.
在科学计算中,稀疏矩阵向量乘(SpMV)是一个十分重要且经常被大量调用的计算内核.由于SpMV一般实现算法的浮点计算和存储访问次数比率非常低,且其存储访问模式极为不规则,其实际运行性能往往很低.通过采用寄存器分块算法和启发式分块大小选择算法,将稀疏矩阵分成小的稠密分块,重用保存在寄存器中向量x元素,可以提高该计算内核的性能.剖析和总结了OSKI软件包所采用的若干关键优化技术,并进行了实际应用性能测试.测试表明,在实际应用这些优化技术的过程中,应用程序对SpMV的调用次数要达到上百次的量级,才能抵消由于应用这些性能优化技术所带来的额外时间开销,取得性能加速效果.在Pentium 4和AMD Athlon平台上,测试了10个矩阵,其平均加速比分别达到了1.69和1.48.
摘要:
构件特别是第三方构件的可靠性及安全性是影响构件技术发展的重要因素之一.目前在构件安全漏洞的测试方法和技术方面研究还不够深入.提出了一种构件安全测试错误注入模型FIM(fault injection model of component security testing),并对FIM模型的相关定义及其矩阵形式进行了详细阐述,同时基于FIM模型给出了一种错误注入测试用例生成算法TGSM(test-case generating based on solution matrix).TGSM算法根据矩阵形式的FIM模型生成满足K因素覆盖的解矩阵,解矩阵的所有行数据组成了错误注入测试用例.在研究项目CSTS(component security testing system)中实现了FIM模型,实验结果表明FIM生成的三因素覆盖错误注入测试用例效果显著,能用适当的测试用例触发绝大部分构件安全异常.FIM模型具有较好的可操作性及可用性.
构件特别是第三方构件的可靠性及安全性是影响构件技术发展的重要因素之一.目前在构件安全漏洞的测试方法和技术方面研究还不够深入.提出了一种构件安全测试错误注入模型FIM(fault injection model of component security testing),并对FIM模型的相关定义及其矩阵形式进行了详细阐述,同时基于FIM模型给出了一种错误注入测试用例生成算法TGSM(test-case generating based on solution matrix).TGSM算法根据矩阵形式的FIM模型生成满足K因素覆盖的解矩阵,解矩阵的所有行数据组成了错误注入测试用例.在研究项目CSTS(component security testing system)中实现了FIM模型,实验结果表明FIM生成的三因素覆盖错误注入测试用例效果显著,能用适当的测试用例触发绝大部分构件安全异常.FIM模型具有较好的可操作性及可用性.
摘要:
针对传统的编程题自动评分方法没有考虑学生程序是怎样实现编程任务的,以及不能从程序文本的语法结构和语义角度衡量学生程序与正确答案的接近程度等问题,提出一种基于程序理解的自动评分方法.以程序理解的一般过程及基本策略为依据,结合人工阅卷的思维过程,建立评分模型.评分过程可划分为3个阶段:首先将程序代码转换成系统依赖图中间表示形式;然后,对系统依赖图进行标准化转换,消除程序表达方式的多样性;最后,匹配标准化后的学生程序与模板程序系统依赖图并根据匹配结果给出评分.该方法被应用于“C语言编程题自动评分系统”中.实验结果表明:它可以根据学生程序的语法和语义衡量学生程序实现编程任务的正确程度,具有较高的准确性.
针对传统的编程题自动评分方法没有考虑学生程序是怎样实现编程任务的,以及不能从程序文本的语法结构和语义角度衡量学生程序与正确答案的接近程度等问题,提出一种基于程序理解的自动评分方法.以程序理解的一般过程及基本策略为依据,结合人工阅卷的思维过程,建立评分模型.评分过程可划分为3个阶段:首先将程序代码转换成系统依赖图中间表示形式;然后,对系统依赖图进行标准化转换,消除程序表达方式的多样性;最后,匹配标准化后的学生程序与模板程序系统依赖图并根据匹配结果给出评分.该方法被应用于“C语言编程题自动评分系统”中.实验结果表明:它可以根据学生程序的语法和语义衡量学生程序实现编程任务的正确程度,具有较高的准确性.
摘要:
工作流模型的验证技术主要包括语法验证、结构验证和语义验证,其中语义验证是层次最高、最为严格的验证,验证的范围十分广泛,也是难点所在,目前尚缺乏有效的方法.而且,语义的正确性会影响工作流模型的控制逻辑,也是结构合理性的影响因素之一.从工作流模型表达的语义出发,通过分析工作流模型刻画的业务规则以及相应的约束集部分,基于对约束集语义的形式化,问题转换为对约束集语义的完整性验证.如果工作流模型中的条件节点所描述的约束集语义有遗漏、冗余或者无意义,也决定了模型错误的拓扑结构.提出全域覆盖性判定定理及基于判定树的验证算法,通过验证工作流业务规则语义的完整性, 对工作流模型结构的合理性也给予了保证.这种验证方法具有很强的通用性,不依赖于具体的建模方法,适用范围广泛.
工作流模型的验证技术主要包括语法验证、结构验证和语义验证,其中语义验证是层次最高、最为严格的验证,验证的范围十分广泛,也是难点所在,目前尚缺乏有效的方法.而且,语义的正确性会影响工作流模型的控制逻辑,也是结构合理性的影响因素之一.从工作流模型表达的语义出发,通过分析工作流模型刻画的业务规则以及相应的约束集部分,基于对约束集语义的形式化,问题转换为对约束集语义的完整性验证.如果工作流模型中的条件节点所描述的约束集语义有遗漏、冗余或者无意义,也决定了模型错误的拓扑结构.提出全域覆盖性判定定理及基于判定树的验证算法,通过验证工作流业务规则语义的完整性, 对工作流模型结构的合理性也给予了保证.这种验证方法具有很强的通用性,不依赖于具体的建模方法,适用范围广泛.
摘要:
由于可信软件评估需求的动态多变以及专家主观决策的有限理性,多维多尺度可信软件评估问题是一个重要而困难的研究课题.在分析现有可信软件评估需求的基础上,提出一种基于效用和证据理论的可信软件评估方法.首先设计了一个需求驱动的可信指标树动态构造模型:开放式可信指标数据库和指标树生成算法;接着讨论分析了基于效用的可信软件定性和定量指标的信息预处理技术,并重点介绍基于分布式评估框架和Dempster合成规则的可信软件评估证据推理算法;最后通过案例证明了该方法的有效性和合理性.相信该模型的提出能对复杂环境下软件可信性评估理论的进一步研究起推动作用.
由于可信软件评估需求的动态多变以及专家主观决策的有限理性,多维多尺度可信软件评估问题是一个重要而困难的研究课题.在分析现有可信软件评估需求的基础上,提出一种基于效用和证据理论的可信软件评估方法.首先设计了一个需求驱动的可信指标树动态构造模型:开放式可信指标数据库和指标树生成算法;接着讨论分析了基于效用的可信软件定性和定量指标的信息预处理技术,并重点介绍基于分布式评估框架和Dempster合成规则的可信软件评估证据推理算法;最后通过案例证明了该方法的有效性和合理性.相信该模型的提出能对复杂环境下软件可信性评估理论的进一步研究起推动作用.
摘要:
2006年,conformant规划问题成为国际规划竞赛不确定性问题域中的标准测试问题,得到研究人员的广泛关注.目前,conformant规划系统都是将其看成信念状态空间上的启发式搜索问题予以求解.通过分析conformant规划问题的语法和语义,提出新的基于模态逻辑的规划框架,将其转换为模态逻辑D公理系统的一系列定理证明问题.提出2种基于模态逻辑的编码方式,构造相应的公理与推理规则形成模态公式集,保证对于D系统的定理证明过程等同于原问题的规划过程,并通过问题实例验证该方法的有效性.继基于SAT、CSP、线性规划、模型检测等求解技术的规划方法后,该规划框架是基于转换的规划方法的一种新的尝试.
2006年,conformant规划问题成为国际规划竞赛不确定性问题域中的标准测试问题,得到研究人员的广泛关注.目前,conformant规划系统都是将其看成信念状态空间上的启发式搜索问题予以求解.通过分析conformant规划问题的语法和语义,提出新的基于模态逻辑的规划框架,将其转换为模态逻辑D公理系统的一系列定理证明问题.提出2种基于模态逻辑的编码方式,构造相应的公理与推理规则形成模态公式集,保证对于D系统的定理证明过程等同于原问题的规划过程,并通过问题实例验证该方法的有效性.继基于SAT、CSP、线性规划、模型检测等求解技术的规划方法后,该规划框架是基于转换的规划方法的一种新的尝试.
摘要:
定性空间推理(QSR)研究空间关系,多数工作集中在单维空间关系,但在地理信息系统(GIS)中多维对象很常见.混合维对象空间关系是指点、线和区域3类对象出现在同一场景的情况,该类问题对定性空间推理研究有着重要的理论意义和应用价值,但这方面的研究工作还比较少.在已有的混合维区域连接演算的基础上进行完善,提出了MRCC5混合维拓扑模型,并研究了其上约束满足推理问题的复杂度.对定性尺寸关系进行了混合维扩展,给出了MDS模型,进而研究了其推理问题.在以上工作基础上,提出了RCC5和MDS的结合模型,给出并分析了结合模型的推理算法.将定性空间推理相关研究推广到混合维领域,深入研究了混合维拓扑关系推理,提出了混合维尺寸以及混合维拓扑尺寸结合模型.
定性空间推理(QSR)研究空间关系,多数工作集中在单维空间关系,但在地理信息系统(GIS)中多维对象很常见.混合维对象空间关系是指点、线和区域3类对象出现在同一场景的情况,该类问题对定性空间推理研究有着重要的理论意义和应用价值,但这方面的研究工作还比较少.在已有的混合维区域连接演算的基础上进行完善,提出了MRCC5混合维拓扑模型,并研究了其上约束满足推理问题的复杂度.对定性尺寸关系进行了混合维扩展,给出了MDS模型,进而研究了其推理问题.在以上工作基础上,提出了RCC5和MDS的结合模型,给出并分析了结合模型的推理算法.将定性空间推理相关研究推广到混合维领域,深入研究了混合维拓扑关系推理,提出了混合维尺寸以及混合维拓扑尺寸结合模型.
摘要:
随着互联网的不断发展和数据量的不断增加,搜索引擎的作用日益明显,用户更多地依靠搜索引擎来查找需要的信息.利用潜在语义索引(LSI)理论和自组织映射神经网络(SOM)理论,提出了一种文本聚类的新方法——LSOM. 该方法应用SOM网络来实现检索结果文本聚类,不必预先给定类别个数,具有聚类灵活和精度高等特点;同时,该方法应用LSI理论来建立向量空间模型,在词条的权重中引入了语义关系,对于高维的文本特征向量,消减原词条矩阵中包含的噪声,提高聚类速度.LSOM使用一种新的类别标签提取方法,并将提取的标签用于解决SOM基本类划分问题,算法在类别标签和聚类效果评价指标上都比已有的算法有所提高.
随着互联网的不断发展和数据量的不断增加,搜索引擎的作用日益明显,用户更多地依靠搜索引擎来查找需要的信息.利用潜在语义索引(LSI)理论和自组织映射神经网络(SOM)理论,提出了一种文本聚类的新方法——LSOM. 该方法应用SOM网络来实现检索结果文本聚类,不必预先给定类别个数,具有聚类灵活和精度高等特点;同时,该方法应用LSI理论来建立向量空间模型,在词条的权重中引入了语义关系,对于高维的文本特征向量,消减原词条矩阵中包含的噪声,提高聚类速度.LSOM使用一种新的类别标签提取方法,并将提取的标签用于解决SOM基本类划分问题,算法在类别标签和聚类效果评价指标上都比已有的算法有所提高.
摘要:
时序多文档文摘是针对新闻领域跨时段的相关文档集,即系列新闻报道进行问题无关的、抽取式文摘.根据系列新闻报道不同细节层次的时序特性,提出一种基于宏微观重要性判别模型的内容选择方法.从宏观和微观角度挖掘信息随着时间进化的时序特性,以指导时序多文档文摘的内容选择.首先通过宏观模型确定重要的时间点,然后通过微观模型在重要的时间点选择重要的句子,从而更有效地获取文摘.实验证明该方法是有效的.
时序多文档文摘是针对新闻领域跨时段的相关文档集,即系列新闻报道进行问题无关的、抽取式文摘.根据系列新闻报道不同细节层次的时序特性,提出一种基于宏微观重要性判别模型的内容选择方法.从宏观和微观角度挖掘信息随着时间进化的时序特性,以指导时序多文档文摘的内容选择.首先通过宏观模型确定重要的时间点,然后通过微观模型在重要的时间点选择重要的句子,从而更有效地获取文摘.实验证明该方法是有效的.
摘要:
注意把有限的处理资源优先分配给那些需要精细加工的信息,能提高视觉信息加工中的检测能力和响应速度.基于生物视觉系统的生理结构特点,建立了模拟生物视觉注意系统的有指向性的视觉注意计算机模型.模型首先模拟生物视网膜的成像机制,将视场图像转化为视网膜图像;然后将最大梯度边缘检测和c-均值聚类等方法相结合,对视网膜图像中的目标进行编码,分别提取每个目标的颜色、中心以及边缘点集合等基本信息;最后用知识库中指向性目标的特征来指导注意焦点的转移.实验结果表明,利用此模型能较好地实现注意焦点的转移.
注意把有限的处理资源优先分配给那些需要精细加工的信息,能提高视觉信息加工中的检测能力和响应速度.基于生物视觉系统的生理结构特点,建立了模拟生物视觉注意系统的有指向性的视觉注意计算机模型.模型首先模拟生物视网膜的成像机制,将视场图像转化为视网膜图像;然后将最大梯度边缘检测和c-均值聚类等方法相结合,对视网膜图像中的目标进行编码,分别提取每个目标的颜色、中心以及边缘点集合等基本信息;最后用知识库中指向性目标的特征来指导注意焦点的转移.实验结果表明,利用此模型能较好地实现注意焦点的转移.
摘要:
场景图像分类是计算机视觉领域中的一个基本问题.提出一种基于内容相关性的场景图像分类方法.首先从图像上提取视觉单词,并把图像表示成视觉单词的词频矢量;然后利用产生式模型来学习训练集合中包含的主题,和每一幅图像所包含的相关主题;最后用判定式分类器进行多类学习.提出的方法利用logistic正态分布对主题的相关性进行建模,使得学习得到的类别的主题分布更准确.并且在学习过程中不需要对图像内容进行人工标注.还提出了一种新的局部区域描述方法,它结合了局部区域的梯度信息和彩色信息.在自然场景图像集合和人造场景图像集合上实验了提出的方法,它相对于传统方法取得了更好的结果.
场景图像分类是计算机视觉领域中的一个基本问题.提出一种基于内容相关性的场景图像分类方法.首先从图像上提取视觉单词,并把图像表示成视觉单词的词频矢量;然后利用产生式模型来学习训练集合中包含的主题,和每一幅图像所包含的相关主题;最后用判定式分类器进行多类学习.提出的方法利用logistic正态分布对主题的相关性进行建模,使得学习得到的类别的主题分布更准确.并且在学习过程中不需要对图像内容进行人工标注.还提出了一种新的局部区域描述方法,它结合了局部区域的梯度信息和彩色信息.在自然场景图像集合和人造场景图像集合上实验了提出的方法,它相对于传统方法取得了更好的结果.
摘要:
通过多个分类器的组合来提升分类精度是机器学习领域主要研究内容,弱学习定理保证了这种研究的可行性.分类器的线性组合,也即加权投票,是最常用的组合方法,其中广泛使用的AdaBoost算法和Bagging算法就是采取的加权投票.分类器组合的有效性问题以及最佳组合问题均需要解决.在各单个分类器互不相关和分类器数量较多条件下,得到了分类器组合有效的组合系数选取条件以及最佳组合系数公式,给出了组合分类器的误差分析.结论表明,当各分类器分类错误率有统一的边界时,即使采取简单投票,也能确保组合分类器分类错误率随分类器个数增加而以指数级降低.在此基础上,仿照AdaBoost算法,提出了一些新的集成学习算法,特别是提出了直接面向组合分类器分类精度快速提升这一目标的集成学习算法,分析并指出了这种算法的合理性和科学性,它是对传统的以错误率最低为目标的分类器训练与选取方法的延伸和扩展.从另一个角度证明了AdaBoost算法中采用的组合不仅有效,而且在一定条件下等效于最佳组合.针对多分类问题,得到了与二分类问题类似的分类器组合理论与结论,包括组合有效条件、最佳组合、误差估计等.还对AdaBoost算法进行了一定的扩展.
通过多个分类器的组合来提升分类精度是机器学习领域主要研究内容,弱学习定理保证了这种研究的可行性.分类器的线性组合,也即加权投票,是最常用的组合方法,其中广泛使用的AdaBoost算法和Bagging算法就是采取的加权投票.分类器组合的有效性问题以及最佳组合问题均需要解决.在各单个分类器互不相关和分类器数量较多条件下,得到了分类器组合有效的组合系数选取条件以及最佳组合系数公式,给出了组合分类器的误差分析.结论表明,当各分类器分类错误率有统一的边界时,即使采取简单投票,也能确保组合分类器分类错误率随分类器个数增加而以指数级降低.在此基础上,仿照AdaBoost算法,提出了一些新的集成学习算法,特别是提出了直接面向组合分类器分类精度快速提升这一目标的集成学习算法,分析并指出了这种算法的合理性和科学性,它是对传统的以错误率最低为目标的分类器训练与选取方法的延伸和扩展.从另一个角度证明了AdaBoost算法中采用的组合不仅有效,而且在一定条件下等效于最佳组合.针对多分类问题,得到了与二分类问题类似的分类器组合理论与结论,包括组合有效条件、最佳组合、误差估计等.还对AdaBoost算法进行了一定的扩展.
摘要:
隐私保护的数据挖掘近来已成为数据挖掘研究的热点,而数据隐私的保护则是其中的重要问题之一.针对已有方法信息损失程度高、聚集查询精度低的不足,在(alpha, k)隐私保护模型基础上,利用关系数据库理论的有损分解思想,提出了一种改进的数据隐私保护方法Alpha+.该方法首先利用(alpha, k)生成原始数据的匿名数据库,然后,将匿名数据库投影为2个可连接的数据库表NSS和SS,并利用NSS和SS有损连接的冗余信息保护数据隐私.接下来,Alpha+对NSS和SS的元组进行合并,以减少最终发布的数据库表大小.最后比较了Alpha+方法与其他类似方法的安全性.实验结果表明Alpha+在聚集查询精度方面明显优于同类方法.
隐私保护的数据挖掘近来已成为数据挖掘研究的热点,而数据隐私的保护则是其中的重要问题之一.针对已有方法信息损失程度高、聚集查询精度低的不足,在(alpha, k)隐私保护模型基础上,利用关系数据库理论的有损分解思想,提出了一种改进的数据隐私保护方法Alpha+.该方法首先利用(alpha, k)生成原始数据的匿名数据库,然后,将匿名数据库投影为2个可连接的数据库表NSS和SS,并利用NSS和SS有损连接的冗余信息保护数据隐私.接下来,Alpha+对NSS和SS的元组进行合并,以减少最终发布的数据库表大小.最后比较了Alpha+方法与其他类似方法的安全性.实验结果表明Alpha+在聚集查询精度方面明显优于同类方法.
摘要:
不完全信息环境下XML文档中的数据存在多值依赖时,为了避免在没有约束条件下XML文档数据出现冗余及更新异常,引入XML强多值依赖的概念和理论对XML文档的规范化进行了系统研究.基于节点信息等价、节点信息相容的概念给出了XML强多值依赖的定义;基于层次化的XML强多值依赖,提出了不完全XML文档树满足XML强多值依赖范式的条件;给出了满足该条件的不完全XML文档树无数据冗余的判定定理;提出了不完全XML文档树的规范化算法,对其时间复杂性进行了分析.理论研究和实例分析表明:研究成果较好地解决了在不完全信息环境下XML文档中存在层次化的XML强多值依赖引起的数据冗余问题.
不完全信息环境下XML文档中的数据存在多值依赖时,为了避免在没有约束条件下XML文档数据出现冗余及更新异常,引入XML强多值依赖的概念和理论对XML文档的规范化进行了系统研究.基于节点信息等价、节点信息相容的概念给出了XML强多值依赖的定义;基于层次化的XML强多值依赖,提出了不完全XML文档树满足XML强多值依赖范式的条件;给出了满足该条件的不完全XML文档树无数据冗余的判定定理;提出了不完全XML文档树的规范化算法,对其时间复杂性进行了分析.理论研究和实例分析表明:研究成果较好地解决了在不完全信息环境下XML文档中存在层次化的XML强多值依赖引起的数据冗余问题.
摘要:
随着集成电路工艺进入纳米时代,供电电压波动严重影响电路性能.制造中通孔对位不准,及运行中铜导线电迁移现象,都会在电源线/地线网络(P/G网)中产生大量潜在的开路故障,并使供电电压发生明显波动.为了在测试中对大量的开路故障进行快速测试,迫切需要提高故障分析的算法效率.为此,首次提出了单故障连续过松弛算法(SD-SOR),对发生单开路电阻故障的P/G网节点电压分布进行快速分析.基于无故障P/G网节点电压分布,SD-SOR仅对开路电阻周围受故障影响比较大的少数节点进行松弛计算.与传统的全局SOR方法相比,SD-SOR具有如下3个优点:1)局部松弛.由于电路中只有一个电阻q发生开路故障,SD-SOR不是采用全局电路节点的顺序松弛方法,而是采用从故障q所连的节点不断向周围节点进行松弛的波状松弛方法,当某些节点的IR电压降变化小于一个极小的设定值时,这些节点就不再向外进行松弛计算.2)高效.与传统的全局SOR方法相比, SD-SOR不仅参与松弛的节点非常少,而且松弛次数也有明显减少.3)高精度.与传统的全局SOR方法相比,由于距离故障比较远,电路中绝大多数节点电压变化非常小,所以SD-SOR只需对距离故障比较近的节点进行松弛计算,就能够保持较高的分析精度.大量的实验数据表明:与预条件全局SOR求解方法相比,SD-SOR在保持较高精度(误差小于0.95%)的前提下,速度可以提高57倍.
随着集成电路工艺进入纳米时代,供电电压波动严重影响电路性能.制造中通孔对位不准,及运行中铜导线电迁移现象,都会在电源线/地线网络(P/G网)中产生大量潜在的开路故障,并使供电电压发生明显波动.为了在测试中对大量的开路故障进行快速测试,迫切需要提高故障分析的算法效率.为此,首次提出了单故障连续过松弛算法(SD-SOR),对发生单开路电阻故障的P/G网节点电压分布进行快速分析.基于无故障P/G网节点电压分布,SD-SOR仅对开路电阻周围受故障影响比较大的少数节点进行松弛计算.与传统的全局SOR方法相比,SD-SOR具有如下3个优点:1)局部松弛.由于电路中只有一个电阻q发生开路故障,SD-SOR不是采用全局电路节点的顺序松弛方法,而是采用从故障q所连的节点不断向周围节点进行松弛的波状松弛方法,当某些节点的IR电压降变化小于一个极小的设定值时,这些节点就不再向外进行松弛计算.2)高效.与传统的全局SOR方法相比, SD-SOR不仅参与松弛的节点非常少,而且松弛次数也有明显减少.3)高精度.与传统的全局SOR方法相比,由于距离故障比较远,电路中绝大多数节点电压变化非常小,所以SD-SOR只需对距离故障比较近的节点进行松弛计算,就能够保持较高的分析精度.大量的实验数据表明:与预条件全局SOR求解方法相比,SD-SOR在保持较高精度(误差小于0.95%)的前提下,速度可以提高57倍.