计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2005年第08期杂志 文档列表

计算机学报杂志研究论文与技术报告

基于基因表达式编程的频繁函数集挖掘1247-1254

摘要：函数挖掘旨在从观测数据中发现有效的函数关系,传统的函数挖掘以发现单个函数为挖掘目标,难以处理复杂数据集.为解决上述问题,作者做了如下工作:(1)提出了描述能力更强的频繁函数集FFS概念;(2)提出并实现了基于基因表达式编程的频繁函数集挖掘算法FFSM;(3)在GEP中采用了精度阈值队列策略PTQ,有效地提高了FFSM的成功率;(4)用实验证实了FFS更强的描述能力和PTQ的有效性,其中,在挖掘高精度复杂函数时PTQ使FFSM的成功率提高了55倍.

一种针对多媒体扩展指令集和实际多媒体程序的自动向量化方法1255-1266

摘要：自动向量化编译是利用处理器的多媒体扩展指令集提升多媒体程序性能的理想工具.但目前的研究不能有效加速实际程序.其主要原因是:普通算术操作的向量化不一定有性能提升;而多媒体典型操作因为其在源代码中表现形式多样而不能充分向量化.为了解决这一问题,文章对经典向量化算法[1]进行改进以灵活统一地向量化这两类操作.主要的改进是增加了两个步骤:统一操作的不同表现形式和识别有价值的向量化操作.改进后的算法可以充分利用指令集生成高效代码,从而对实际多媒体程序拥有良好效果.此外,该算法可扩展性也很强.

基于仿射点对应的分层重构1267-1276

摘要：提出了一种基于仿射点对应的分层重构方法,所谓仿射点对应是指相差一个仿射变换的两个空间点集的图像对应.该方法主要分为以下三个步骤:首先,从点对应计算准仿射重构;然后,由仿射点对应的准仿射重构建立一个三维射影变换,并利用这个射影变换的特征向量来确定无穷远平面,从而得到仿射重构;最后,从仿射重构所获得的无穷远平面单应矩阵标定摄像机内参数,进而得到度量重构.在上述三个步骤中,第二个步骤是最关键的,即如何确定对应于无穷远平面的特征向量,这也是该文的新思想和主要贡献所在.仿真和真实图像实验均表明,该文的方法是有效的,并且有很好的鲁棒性.

层次泛函网络整体学习算法1277-1286

摘要：文中设计了一类单输入单输出泛函网络与双输入单输出泛函网络作为构造层次泛函网络基本模型,提出了一种层次泛函网络模型,给出了层次泛函网络构造方法和整体学习算法,而层次泛函网络的参数利用解方程组来进行逐层学习.以非线性代数方程组为例,指出人们熟知的一些数学解题方法可以用层次泛函网络来表达,探讨了基于层次泛函网络求解非线性代数方程组学习算法实现的一些技术问题.相对传统方法,层次泛函网络更适合于具有层次结构的应用领域.计算机仿真结果表明,这种层次学习方法具有较快的收敛速度和良好的逼近性能.

基于信息理论的合作聚类算法研究1287-1294

摘要：传统的聚类算法是针对一个独立数据集的学习分类算法,如FCM(Fuzzy-C-Means)聚类算法.在现实生活中,一个数据集独立于其它数据集,而往往通过与别的数据集交换信息与之相互合作.因此在聚类过程中,需要考虑来自其它数据集的影响,从而得到更能反映现实的数据结构.该文提出了一种基于信息理论的信息增益方法来建模并定量分析多个数据集间的合作关系.在此基础上,导出了相应的新合作聚类算法CCA(Cooperative Clustering Algorithm).理论分析表明该算法最终收敛.实验结果也进一步表明了该合作聚类算法的可行性与有效性.

机器学习中的核覆盖算法1295-1301

摘要：基于统计学习理论的支持向量机(SVM)方法在样本空间或特征空间构造最优分类超平面解决了分类器的构造问题,但其本质是二分类的,且核函数中的参数难以确定,计算复杂性高.构造性学习算法根据训练样本构造性地设计分类网络,运行效率高,便于处理多分类问题,但存在所得的分界面零乱、测试计算量大的缺点.该文将SVM中的核函数法与构造性学习的覆盖算法相融合,给出一种新的核覆盖算法.新算法克服了以上两种模型的缺点,具有运算速度快、精度高、鲁棒性强的优点.其次,文中给出风险误差上界与覆盖个数的关系.最后给出实验模拟,模拟结果证明了新方法的优越性.

最小二乘隐空间支持向量机1302-1307

摘要：在隐空间中采用最小二乘损失函数,提出了最小二乘隐空间支持向量机(LSHSSVMs).同隐空间支持向量机(HSSVMs)一样,最小二乘隐空间支持向量机不需要核函数满足正定条件,从而扩展了支持向量机核函数的选择范围.由于采用了最小二乘损失函数,最小二乘隐空间支持向量机产生的优化问题为无约束凸二次规划,这比隐空间支持向量机产生的约束凸二次规划更易求解.仿真实验结果表明所提算法在计算时间和推广能力上较隐空间支持向量机存在一定的优势.

基于可信度的投票法1308-1313

摘要：可信度投票法不仅使用了基分类器输出的类别,还使用了输出的可信度.推导了该方法训练错误率的界以及期望错误率的界.发现为了最小化期望错误率的界,应该使用错误独立的基分类器,如果基分类器的错误率不是很高,这个界以指数级速度随着基分类器错误率的降低而降低,而且这个界随着投票次数的增加也会下降.在最小化训练错误率的界的意义下,得到了一种权值分配方法.把这个方法应用于一种Bagging算法:AB,得到了综合分类算法CAB.使用UCI机器学习数据集中的数据,通过实验验证了CAB的有效性.

免疫阴性选择分类器在信息恢复中的应用1314-1319

摘要：文中的信息恢复系统是基于网络获取文本信息的系统,利用基于熵的信息抽取技术将获得的网络文本转换成特征向量文件.免疫阴性选择分类器是基于免疫系统T细胞选择原理设计检测器,利用协同进化算法进化检测器,进化得到的检测器对信息恢复系统中的文本特征向量进行分类.分类后得到的有用文件用于系统中的信息恢复.实验结果表明,与传统的朴素贝叶斯分类器比较,该方法具有更高的分类准确性,不仅验证了免疫阴性选择分类器的良好性能,同时也提高了信息恢复准确性.

基于个体密集距离的多目标进化算法1320-1326

摘要：外部种群维护和适应度赋值是多目标进化算法(MOEA)的两个重要部分,该文首先对这两个问题目前已有的处理方法进行了分析,然后提出了基于个体密集距离的外部种群维护方法,并在将所有个体根据Pareto支配关系分成四个层次的基础上,给出了一种由个体密集距离定义的适应度函数,最后将基于个体密集距离的多目标进化算法CMOEA应用于几个常用的测试函数,并和SPEA,SPEA-2进行了比较,计算结果表明CMOEA具有良好的搜索性能.

基于自验证公钥的3G移动通信系统认证方案1327-1332

摘要：鉴于单钥密码体制存在密钥管理困难和不能提供防抵赖功能的缺陷,在第三代(3G)移动通信系统中,基于公钥体制的认证方法得到越来越多的重视.为提高单钥体制认证方案的安全性,并改进现有公钥认证协议在性能上存在的缺陷,文章提出了一种高效的基于自验证公钥的认证方案.该方案包含PKBP(公钥广播协议)和SPAKA(基于自验证公钥的认证及密钥交换协议).其中,PKBP可使移动设备(ME)抵抗伪基站攻击并避免鉴别VLR(拜访位置寄存器)证书的合法性;而SPAKA可在无须传送公钥证书的前提下完成ME和VLR的相互认证及会话密钥协商.与现有公钥认证协议相比,PKBP和SPAKA减少了ME的数据传输量和在线计算量,获得了单钥认证协议所不能达到的安全目标和可扩展性,并可在特定场合实现对ME通话的可控、合法监听,满足国家安全部门的需求.因此,该方案很适合于支持3G系统的全球移动性和通信安全性.

无线局域网中的自适应节能机制1333-1341

摘要：为节省能量,无线局域网标准IEEE 802.11在分布式协调功能(DCF)的基础上定义了节能机制PSM,但该机制在重负载情况下性能严重劣化.为提高该机制在重负载情况下的性能,该文对现有PSM进行研究分析后提出自适应调整接入概率的PSM+和fairPSM+.仿真结果表明PSM+和fairPSM+在轻负载下性能与PSM相当,而在重负载下较大地提高了吞吐量及能量有效性.fairPSM+在PSM+的基础之上考虑了系统的稳定性和公平性,因此具有最好的性能.

TCP Yuelu：一种基于有线／无线混合网络端到端的拥塞控制机制1342-1350

摘要：无线链路传输数据的比特率出错导致TCP协议在有线/无线混合网络环境下性能低下,在改进算法TCP Reno的基础上,文章提出了一种适用于有线/无线混合网络的拥塞控制机制.该机制包括一种分阶段平滑慢启动机制,改善了突发流量对网络性能的损害,引入网络测量技术获得了往返时间(RTT)、网络带宽、瓶颈链路队列长度等网络状态参数,区分网络拥塞和无线链路比特差错,避免了终端节点对网络状态不了解产生的盲目行为,有效改进了TCP的加性增加乘性减少(AIMD)窗口调节机制,提高了网络性能.同时,在仿真软件NS2中实现了该算法,进行了大量的仿真实验,实验结果表明TCP Yuelu有效降低了网络抖动,提高了网络传输性能,并保持了良好的公平性和对其它TCP流的友好性.

自相似活跃子网前缀空间的路由查找1351-1359

摘要：IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空间是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化.文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前缀在不同的聚类规模上的次序统计量服从Pareto分布,主干路由表项的次序统计量也近似服从Pareto分布.该文提出了一种基于活跃度排序的路由逐次查找算法--SOSL,对IP地址查询进行了优化,在该文的模拟实验中,活跃路由表的规模、刷新周期和活跃度判定下限间存在一些对数线性关系,使得作者可以以很小的活跃路由表来实现全部路由查找需求的99%;为SOSL实现中最关键的活跃路由表排序问题提出了一个基于计数器溢出的方案,复杂度为O(1).对比发现该文的算法与TCAM结合能够提高TCAM的效率,高效地控制活跃路由表的规模,易于硬件实现.

宽带卫星网络TCP性能分析1360-1366

摘要：用卫星链路接入Internet或者自身组成一个宽带卫星网络并和Internet互联是卫星通信的重要发展方向.TCP的流量控制是Internet正常运行的基础,围绕着TCP流量控制的拥塞控制一直是Internet 研究的一个热点.在长时延特性的宽带卫星网络环境下,当前广泛使用的TCP协议性能相应地会受到影响.文章分析了基于分组的宽带卫星网络中TCP的各种性能,并通过网络仿真对理论分析结果进行了验证.

基于差分矩因子的灰度图像矩快速算法1367-1375

摘要：由于不变矩对图像的平移放大旋转的不敏感性,因此在图像处理、模式识别、场景匹配和计算机视觉等领域获得越来越广泛的应用.但是,求矩运算过程复杂,计算量大,使它的应用受到限制.快速求矩算法不少,但大多限于二值图像.文中提出一种新的适用于灰度图像的快速求矩算法.算法基于文中提出和证明的差分求和定理,即两个离散函数数组的乘积,等于将其中一个差分、另一个累进求和后的乘积.将矩因子作为一个函数数组,图像作为另一个函数数组,对矩因子数组实施多次差分,差分结果使得矩因子数组除边界1个或几个数组元素外,其余数组元素值皆为0.这样需对所有数组元素的乘积变为只对边界1个或几个数组元素的乘积.由于边界上不为0的数组元素值几乎都为1,这实际上就无需乘法计算.该算法原理简单,编程容易,求矩结果精确,适用于任意灰度图像.利用该算法,对任意大小和任意级别的灰度图像,无需任何乘法计算,且加法运算次数也大幅减少.和其它求矩算法相比,计算复杂性大大降低.

扩频CDMA水印性能分析及其多小波域内的应用研究1376-1385

摘要：通过对扩频码分多址(CDMA)水印模型的编码及检测方法进行理论分析,阐述了信息嵌入量、扩频码长、检测错误率等指标之间存在的制约关系,并使用实验进行比较和验证.在理论分析的基础上,依据多小波分解系数优良统计分布特征和图像多小波视觉掩蔽模型,提出了一种新颖的基于多小波变换的扩频CDMA数字水印方案.理论结果与实验数据对比表明所提出的模型和算法既有较高的嵌入容量,又具有较强的鲁棒性和安全性.

基于动态背景构造的视频运动对象自动分割1386-1392

摘要：提出了一种基于动态背景构造的视频运动对象自动分割算法.首先,基于前景分离的动态背景构造技术使用与当前帧相邻的前后多帧图像中的背景信息准确地构造当前背景;然后,通过背景消除分割出运动对象,同时对静态前景区域(即帧间静止的运动对象区域)进行检测并将其合并到已分割出的对象区域上,从而获得完整的对象区域;最后,以对象区域的边缘为初始位置,使用以彩色梯度为外部能量的活动轮廓(snake)算法获得精确的对象轮廓.实验结果表明,该文算法有效地克服了显露背景和对象的不规则运动对分割准确度的影响,能够准确地实现视频运动对象的自动分割.