软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2008年第11期杂志 文档列表

软件学报杂志半监督学习

半监督学习专刊前言2789-2790

摘要：随着计算机技术的飞速发展，人类收集数据、存储数据的能力得到了极大的提高，无论是科学研究还是社会生活的各个领域中都积累了大量的数据，对这些数据进行分析以发掘数据中蕴含的有用信息，成为几乎所有领域的共同需求．传统的机器学习方法大多只考虑有标记数据（labeled data）或者只考虑未标记数据（unlabeled data），但是在很多真实问题中往往是二者并存，如何更有效地利用这些数据成为一个备受关注的问题．

基于成对约束的判别型半监督聚类分析2791-2802

摘要：现有一些典型的半监督聚类方法一方面难以有效地解决成对约束的违反问题，另一方面未能同时处理高维数据．通过提出一种基于成对约束的判别型半监督聚类分析方法来同时解决上述问题．该方法有效地利用了监督信息集成数据降维和聚类，即在投影空间中使用基于成对约束的K均值算法对数据聚类，再利用聚类结果选择投影空间．同时，该算法降低了基于约束的半监督聚类算法的计算复杂度，并解决了聚类过程中成对约束的违反问题．在一组真实数据集上的实验结果表明，与现有相关半监督聚类算法相比新方法不仅能够处理高维数据，还有效地提高了聚类性能．

基于近邻传播算法的半监督聚类2803-2813

摘要：提出了一种基于近邻传播（affinity propagation，简称AP）算法的半监督聚类方法．AP是在数据点的相似度矩阵的基础上进行聚类．对于规模很大的数据集，AP算法是一种快速、有效的聚类方法，这是其他传统的聚类算法所不能及的，比如：K中心聚类算法．但是，对于一些聚类结构比较复杂的数据集，AP算法往往不能得到很好的聚类结果．使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整，进而达到提高AP算法的聚类性能．实验结果表明，该方法不仅提高了AP对复杂数据的聚类结果，而且在约束对数量较多时，该方法要优于相关比对算法．

第4届数字媒体及其在博物馆和文化遗产中的应用（DMAMH 2009）国际会议征文通知2813-2813

一种半监督K均值多关系数据聚类算法2814-2821

摘要：提出了一种半监督K均值多关系数据聚类算法．该算法在K均值聚类算法的基础上扩展了其初始类簇的选择方法和对象相似性度量方法，以用于多关系数据的半监督学习．为了获取高性能，该算法在聚类过程中充分利用了标记数据、对象属性及各种关系信息．多关系数据库Movie上的实验结果验证了该算法的有效性．

半监督典型相关分析算法2822-2832

摘要：在典型相关分析算法（canonical correlation analysis，简称CCA）的基础上，通过引入以成对约束形式给出的监督信息，提出了一种半监督的典型相关分析算法（Semi—CCA）．在此算法中，除了考虑大量的无标号样本以外，还考虑成对约束信息，即已知两样本属于同一类（正约束）或不属于同一类（负约束），同时验证了两者的相对重要性．在人工数据集、多特征手写体数据集和人脸数据集（Yale和AR）上的实验结果表明，Semi-CCA能够有效地利用少量的监督信息来提高分类性能．

敬告作者2832-2832

基于局部与全局保持的半监督维数约减方法2833-2842

摘要：在很多机器学习和数据挖掘任务中，仅仅利用边信息（side-information）并不能得到最好的半监督学习（semi—supervised leaming）效果，周此，提出一种基于局部与全局保持的半监督维数约减（local and global preserving based semi—supervised dimensionality reduction，简称LGSSDR）方法．该算法不仅能够保持正、负约束信息而且能够保持数据集所在低维流形的全局以及局部信息．另外，该算法能够计算出变换矩阵并较容易地处理未见样本．实验结果验证了该算法的有效性．

基于图的半监督关系抽取2843-2852

摘要：提出利用基于图的半监督学习算法，即标注传递算法，指导计算机从非结构化的文本中自动识别出实体之间的关系．该方法首先利用图策略来建立关系抽取的模型．在这个图模型中，各个有标签和未标签的样本被表示成图上的各个节点，而样本间的距离则作为图上各边的权重．然后，关系抽取的任务就转化成在这个图上估计出一个满足全局一致性假设的标注函数．通过对ACE（automatic content extraction）语料库的评测，结果显示，当只有少量的标签样本时，采用该标注传递的方法可以获得比基于SVM（support vector machine）的有监督关系抽取更好的性能。同时也明显优于基于Bootstrapping的半监督关系抽取的方法．

基于张量表示的直推式多模态视频语义概念检测2853-2868

摘要：提出了一种基于高阶张量表示的视频语义分析与理解框架．在此框架中，视频镜头首先被表示成由视频中所包含的文本、视觉和听觉等多模态数据构成的三阶张量；其次，基于此三阶张量表达及视频的时序关联共生特性设计了一种子空间嵌入降维方法，称为张量镜头；由于直推式学习从已知样本出发能对特定的未知样本进行学习和识别壕：后在这个框架中提出了一种基于张量镜头的直推式支持张量机算法，它不仅保持了张量镜头所在的流形空间的本征结构，而且能够将训练集合外数据直接映射到流形子空间，同时充分利用未标记样本改善分类器的学习性能．实验结果表明，该方法能够有效地进行视频镜头的语义概念检测．

软件学报杂志算法设计与分析

实时动态规划的最优行动判据及算法改进2869-2878

摘要：主要以提高求解马尔可夫决策问题的实时动态规划（real-time dynamic programming，简称RTDP）算法的效率为目的．对几类典型的实时动态规划算法所使用的收敛判据进行了对比分析，并利用值函数上界、下界给出了称为最优行动判据的收敛判据，以及一个更适合实时算法的分支选择策略．最优行动判据可以更早地标定当前状态满足精度要求的最优行动供立即执行，而新的分支选择策略可以加快这一判据的满足．据此设计了一种有界增量实时动态规划（bounded incremental RTDP,简称BI-RTDP）算法．在两种典型仿真实时环境的实验中，BI-RTDP均显示出优于现有相关算法的实时性能．

P2-Packing问题参数算法的改进2879-2886

摘要：P2-Packing问题是一个典型的NP难问题．目前这个问题的最好结果是时间复杂度为O^＊（2^5．301k）的参数算法，其核的大小为15k．通过对P2-Packing问题的结构作进一步分析，提出了改进的核心化算法，得到大小为7k的核，并在此基础上提出了一种时间复杂度为O^＊（2^4．142k）的参数算法，大幅度改进了目前文献中的最好结果．

信息过滤中基于二元近似关系分布的噪声屏蔽算法2887-2898

摘要：针对信息过滤反馈中充斥噪声的缺陷，提出一种基于二元近似关系分布（distribution of two-dimen sionsimilarity,简称DTs）的过滤策略．DTS根据噪声和用户模型的相悖关系，为信息流建立二元近似关系模型．同时，根据信息在二维近似关系空间中的分布，采用基于LMS（least mean square）分类器的AdaBoost算法建立噪声和相关信息的分类曲线，从而辅助信息过滤系统识别和屏蔽反馈中的噪声．通过实验验证，该算法显著提高了过滤系统屏蔽噪声的能力．

一种求解最大团问题的并行交叉熵算法2899-2907

摘要：为了提高交叉熵算法求解最大团问题（maximum clique problem，MCP）的性能，提出一种领导者．跟随者协作求解的并行策略来实现交叉熵算法，从而达到减少计算时间和保障解的质量这两方面的平衡．算法中领导者活跃在并行处理器之间采集数据，并根据当前获得信息对跟随者作出决策；受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间，完成各自的集团产生任务．采用了OpenMPI在MIMD平台上实现了该算法，并应用到MCP基准测试问题上．加速比和效率分析结果表明，算法具有很好的加速比和效率．而与其它几种当前最好的启发式算法相比，结果表明算法相对于基于种群的启发式算法有一定的性能改善．

软件学报杂志模式识别与人工智能

针对环状流形数据的非线性降维2908-2920

摘要：近年来出现了多种新型的非线性降维方法，且在一些应用中体现出良好的效果．然而，当面对球体、柱体等环状流形产生的非线性流形数据时，这些方法往往会失效．针对这一问题，提出了针对环状流形数据的环结构检测算法与非线性降维方法．理论上，基于目前极受关注的Isomap降维方法的运行原理，给出了一个判断环状流形的充要条件：算法上利用所得的判断定理，制订了基于数据的环状流形检测算法；最后基于所找到的环结构，利用极坐标展开的思想设计了针对环状流形数据的非线性降维策略．针对一系列典型环状流形数据集的仿真实验结果表明，与其他流形学习降维方法相比滋方法对环状流形数据进行降维具有显著优势．

基于支持向量机的人脸检测训练集增强2921-2931

摘要：根据支持向量机（support vector machine，简称SVM）理论，对基于边界的分类算法（geometric approach）而言，类别边界附近的样本通常比其他样本包含有更多的分类信息．基于这一基本思路，以人脸检测问题为例，探讨了对给定训练样本集进行边界增强的问题，并为此而提出了一种基于支持向量机和改进的非线性精简集算法IRS（improved reduced set）的训练集边界样本增强算法，用以扩大训练集并改善其样本分布．其中，所谓IRS算法是指在精简集（reduced set）算法的核函数中嵌入一种新的距离度量——图像欧式距离——来改善其迭代近似性能，IRS可以有效地生成新的、位于类别边界附近的虚拟样本以增强给定训练集．为了验证算法的有效性，采用增强的样本集训练基于AdaBoost的人脸检测器，并在MIT＋CMU正面人脸测试库上进行了测试．实验结果表明，通过这种方法能够有效地提高最终分类器的人脸检测性能．

基于局部方向分布的角点检测及亚像素定位2932-2942

摘要：提出了一种基于局部方向分布的角点检测与定位算法．该算法主要由两步组成，首先利用绝对角点能量和相对角点能量进行角点检测，然后使用最小二乘技术拟合支撑像素方向线的交点得到角点的亚像素位置．实验结果表明，相对于常见的角点检测算法，基于局部方向分布的算法不仅具有更高的定位精度，同时对噪音也有较强的鲁棒性．

免疫克隆多目标优化算法求解约束优化问题2943-2956

摘要：针对现有的约束处理技术的一些不足之处，提出一种用于求解约束优化问题的算法——免疫克隆多目标优化算法（immune clonal multi-objective optimization algorithm，简称ICMOA）．算法的主要特点是通过将约束条件转化为一个目标，从而将问题转化为两个目标的多目标优化问题引入多目标优化中的Pareto-支配的概念，每一个个体根据其被支配的程度进行克隆、变异及选择等操作．克隆操作实现了全局择优，有利于得到高质量的解；变异操作提高算法的局部搜索能力，有利于所得解的多样性；选择操作有利于算法向着最优搜索，而且加快了收敛速度．基于抗体群的随机状态转移过程，证明该算法具有全局收敛性．通过对13个标准测试问题的测试，并与已有算法进行比较，结果表明，该算法在收敛速度和求解精度上均具有一定的优势．