计算机科学与探索杂志

计算机科学与探索杂志2019年第4期

• 无需感染时间信息的传播网络快速推断算法

  孙月明，张运加，颜钱，陈璐，黄浩，高云君

  现有的大多数传播网络推断方法需要节点的感染时间信息，但是在许多现实传播过程中，准确的感染时间信息往往是难以获得的。以准确、高效且无需感染时间信息的传播网络推断方法为目标，研究了如何仅利用多次传播过程结束时观测到的各节点的感染状态来推断节点间的影响关系和感染传播概率。为此，该方法首先利用节点感染状态间的互信息来量化它们之间的相互关联，找出可能的节点间影响关系。然后，构建以感染传播概率为变量的节点感染状态观测数据的对数似然函数，并采用期望最大化的方法最大化该对数似然函数并求解感染传播概率。实验结果表明，相较现有方法，该方法有效提高了传播网络推断的准确性，并且大幅缩短了算法运行所需时间。

• 基于生成式对抗网络的链路预测方法

  丁玥，黄玲，王昌栋

  近些年来，网络中链路预测问题逐渐兴起。相比于传统启发性模型，以神经网络为基础的链路预测方法由于其能够自我学习的优点，逐渐获得研究者的青睐。结合生成式对抗网络，一种创新性的链路预测方法WL-GAN（Weisfeiler-Lehman generative adversarial networks）被提出。WL-GAN首先利用子图提取算法与子图编码算法，为网络中的每条已知关系的节点对构造以该节点对为结构中心的节点对子图，并获得相应连接矩阵。随后，利用矩阵数据来训练生成式对抗网络，最终可以获得能够判断子图中心节点对是否存在链路的判别器。实验结果表明，WL-GAN拥有优秀的性能与稳定性。

• 结合动静态分析实现架构恢复的方法

  任武

  在大型遗留系统的维护活动中，通过聚类技术将系统划分为更小和更易于控制的子系统，是理解软件架构的一项重要措施。传统架构恢复的研究主要关注静态结构，而面向对象系统由于多态和动态绑定等复杂因素的存在，仅有结构分析还不足以支持架构恢复。功能特征作为一种可触发可观察的系统行为反映了系统实现的功能需求，已经成为构建核心架构的基础。提出一种动静态结合的分析方法，以软件特征作为出发点，通过特征的场景执行以及模块聚类，建立起目标系统的核心架构，然后分析系统的静态结构以提取模块的依赖关联，补充实体到已建立的聚类中。通过对两个开源项目的实验评估和讨论，分析所提方法的有效性和适用性。

• K-means型多视图聚类中的初始化问题研究

  洪敏，贾彩燕，王晓阳

  在K-means型多视图聚类算法中，最终的聚类结果会受到初始类中心的影响。因此研究了不同的初始中心选择方法对K-means型多视图聚类算法的影响，并提出一种基于采样的主动式初始中心选择方法（sampled- clustering by fast search and find of density peaks，SDPC）。该方法通过对数据集进行均匀采样，利用密度峰值快速搜索聚类算法（clustering by fast search and find of density peaks，DPC），以及K-means再迭代策略，进一步改善多视图聚类中的初始中心选择效率和类个数问题。实验验证了不同初始化方法对K-means型多视图聚类算法的影响。多视图基准数据集上的实验结果表明：全局（核）K-means初始化方法存在时间复杂度过高的问题，AFKMC2（assumption-free K-Markov chain Monte Carlo）初始化适用于大规模数据，DPC可以主动选择类个数和初始类中心，SDPC较DPC而言,不仅能主动式获得类个数，还在聚类精度和效率上取得了较好的折衷。

• 深度卷积自编码图像聚类算法

  谢娟英，侯琦，曹嘉文

  针对现有深度卷积嵌入聚类算法（deep convolutional embedded clustering，DCEC）的网络特征损失过大，对复杂图像没有提取有效特征的问题，提出一个具有17层网络结构的无监督深度聚类框架，并在编码层加入下采样层，减少参数和防止过拟合；在解码层加入上采样层还原下采样造成的细节损失。分别结合DEC（deep embedded clustering）算法的损失函数和IDEC（improved deep embedded clustering）算法的采用局部结构保留优势的损失函数，得到两种基于卷积自编码的深度学习图像聚类算法DEC_DCNN（deep embedded clustering based on deep convolutional neural network）和IDEC_DCNN（improved deep embedded clustering based on deep convolutional neural network），并使用自适应矩估计（adaptive moment estimation，Adam）和小批量随机梯度下降（mini-batch stochastic gradient decent，mini-batch SGD）两种优化方法调整模型参数。3个经典图像数据集的实验结果显示，提出的17层网络结构对图像特征具有很好的鲁棒性和通用性，基于该 网络结构的深度聚类算法取得了远优于现有深度聚类算法的结果，其聚类准确率均优于对比算法；对深度 聚类算法DEC_DCNN和IDEC_DCNN的聚类结果准确率、指标值AMI（adjusted mutual information）和ARI（adjusted rand index）进行比较，IDEC_DCNN比DEC_DCNN的聚类性能更好，说明IDEC_DCNN算法的性能更优越。

• 改进的深度置信网络分类算法研究

  徐毅，李蓓蓓，宋威

  深度置信网络（deep belief network，DBN）通过逐层无监督学习进行训练，但训练过程中易产生大量冗余特征，进而影响特征提取能力。为了使模型更具有解释和辨别能力，基于对灵长类视觉皮层分析的启发，在无监督学习阶段的似然函数中引入惩罚正则项，使用CD（contrastive divergence）训练最大化目标函数的同时，通过稀疏约束获得训练集的稀疏分布，可以使无标签数据学习到直观的特征表示。其次，针对稀疏正则项中存在的不变性问题，提出一种改进的稀疏深度置信网络，使用拉普拉斯函数的分布诱导隐含层节点的稀疏状态，同时将该分布中的位置参数用来控制稀疏的力度，即根据隐藏单元的激活概率与给定稀疏值的偏差程度而具有不同的稀疏水平。通过在MNIST和Pendigits手写体数据集上进行验证分析，并与多种现有方法相比，该方法始终达到最好识别准确度，并且具有良好的稀疏性能。

• 安全有效的无线传感器网络溯源数据方法

  章志明，邓建刚

  为了在不增加额外存储和计算负担的情况下，尽可能多地在一个数据包中嵌入更多节点的溯源数据，提出一种基于正交码和消息鉴别码链的安全溯源数据传输方案（orthogonal code-based provenance scheme, OP）。OP方案只需要一个数据包就能恢复出数据包的传输路径，并且溯源数据的大小与路径的长度无关。安全分析表明OP方案不仅能抵抗单个恶意节点修改或伪造溯源数据攻击，还能抵抗多个恶意节点合谋发起的删除、插入溯源数据等攻击，并能定位到发起攻击的恶意节点。性能分析及实验仿真表明，与现有的方案相比，随着路径长度的增加，方案在存储空间、能量消耗等方面具有明显优势。

• V-NDN中热点内容推送策略研究

  史锦山，李茹，李瑛琦

  在V-NDN（vehicular named data networking）中，因为车辆的移动性而导致未响应兴趣包的概率大大增加。目前的解决方法是车辆节点缓存所有收听到的数据包，但这种方法会使节点中缓存大量重复的数据包副本，增加缓存的开销。为了解决此问题，提出了一种适用于城市道路的热点内容推送算法。首先，提出了一种热点内容挖掘算法，将V-NDN中可能的热点内容从大量的数据中挖掘出来；然后，通过热点内容推送算法将热点内容推送给其他可能访问这些内容的节点，以此提高网络性能；最后，从理论上分析了热点内容挖掘时需要考虑的影响因素。仿真结果表明，与贪婪转发策略相比，添加了热点内容推送算法会使请求满足率提高4.6%到14.1%，缓存命中率增加了16.6%到33.0%。

• 标准模型下格上的密钥封装机制

  赵宗渠，范涛，彭婷婷，叶青，秦攀科

  密钥封装机制（key encapsulation mechanism，KEM）使得会话双方能够安全地共享一个随机的会话密钥，改善了使用公钥加密明文时空间受限的问题，是大规模网络中密钥分发和密钥管理问题的有效解决方案之一。提出一种标准模型下安全高效的格上的密钥封装机制，将陷门函数与带误差学习问题（learning with errors，LWE）算法相结合，并引入参与者的身份信息，保证密钥封装机制的机密性和可认证性，可抵抗现有已知量子算法攻击。采用密文压缩技术，对封装后的密文元素进行压缩，分析结果表明，能够有效提高传输效率。在标准模型下，该机制安全性归约至判定性LWE的难解性，并包含严格的安全性证明。其安全性为可证明的选择密文安全，适用于多种类型基于格的密钥交换协议方案。

• 近似多元信息多样性

  孙涛，周志华

  集成多样性，即个体学习器之间的差异性，是集成学习中的一个基础问题。多元信息多样性（multi-information diversity）基于信息论来刻画集成多样性，为理解集成多样性提供了一个可行方向，其在实际应用中面临的困难是高阶信息通常难以估计。提出基于一种特殊的[k]阶t-cherry联结树对高阶信息做低阶近似，从而得到多元信息多样性的近似估计。方法包括基于联结树直接近似估计多元信息和近似估计多元信息分量，并对两者的相关性进行了分析。实验结果表明，在同阶近似下，该估计方法优于现有近似估计方法。

• 自适应的SVM增量算法

  何丽，韩克平，刘颖

  支持向量机（support vector machine，SVM）算法因其在小样本训练集上的优势和较好的鲁棒性，被广泛应用于处理分类问题。但是对于增量数据和大规模数据，传统的SVM分类算法不能满足需求，增量学习是解决这些问题的有效方法之一。基于数据分布的结构化描述，提出了一种自适应SVM增量学习算法。该算法根据原样本和新增样本与当前分类超平面之间的几何距离，建立了自适应的增量样本选择模型，该模型能够有效地筛选出参与增量训练的边界样本。为了平衡增量学习的速度和性能，模型分别为新增样本和原模型样本设置了基于空间分布相似性的调整系数。实验结果表明，该算法在加快分类速度的同时提高了模型性能。

• 一种粒子群优化的SVM-ELM模型

  王丽娟，丁世飞

  极限学习机（extreme learning machine，ELM）是一种简单易用、有效的单隐层前馈神经网络（single hidden layer feedforward neural networks，SLFNs）学习算法，近几年来已成为机器学习研究的热门领域之一。但是ELM单个隐层节点的判断能力不足，分类正确率的高低在一定程度上取决于隐层节点数。为了提高ELM单个隐层节点的判断能力，将支持向量机（support vector machine，SVM）和ELM结合，建立一种精简的SVM-ELM模型。同时，该模型为了避免人为选择参数的主观性，利用粒子群算法（particle swarm optimization，PSO）的全局搜索最优解对参数进行自动优化选取，建立了PSO-SVM-ELM模型。实验证明，该模型较SVM-ELM和ELM分类精度有较大的提高，具有很好的稳健性和泛化性。

• RGB空间彩色零水印算法

  曲长波，吴德阳，肖成龙，郭鹏飞，姜思瑶

  针对现有零水印算法使用的版权标识大都为结构信息单一的二值图像，且对于几何攻击鲁棒性差等问题，提出一种RGB空间彩色零水印算法。首先将彩色载体图像和彩色水印转换成R、G、B颜色分量，其次对载体图像三个空间分量分别进行Arnold置乱和分块处理；然后计算每个颜色通道各个子块的均值，构成十进制均值矩阵，将均值矩阵转换成8位二进制矩阵，分别生成三个颜色通道的二进制特征矩阵；最后将置乱后的彩色水印分量转换成8位二进制水印信息，分别与载体图像的三个二进制特征矩阵异或生成三个零水印，将三个零水印通过逆编码技术生成彩色零水印。实验结果表明，算法能够有效地抵抗非几何攻击、几何攻击和组合攻击，与相似的零水印算法相比，鲁棒性更好，安全性更高。

• 自适应目标与内容匹配的层级图像分割算法

  魏明桦，郑金贵

  针对超度量轮廓图（ultrametric contour map，UCM）层级图像分割算法对轮廓适应性弱、层级匹配能力较弱且分割碎片较多等问题，提出了一种自适应目标与内容匹配的改进UCM层级图像分割算法。该算法首先使用“轮廓盒子”提取图像关键轮廓，然后使用加权分水岭算法合并区域，提升轮廓适应性，并产生UCM层级树；随后，采用动态规划的方式自适应完成目标与内容匹配，最后使用调整尺度后的UCM层级树完成图像分割。在BSDS500数据集上进行了分割实验，实验结果表明提出的算法在各项分割指标上获得了显著的提升。分割掩盖率（segment cover，SC）、概率边缘指标（probabilistic region index，PRI）和信息变化率（infor-mation variation，IV）三个衡量指标分别在最优数据集尺度（optimal dataset scale，ODS）和最优图像尺度（optimal image scale，OIS）上获得了最佳的效果。UCM层级树通过尺度的调整，能够保证相同尺度的层级分割为同一层，减少了分割碎片，保证了层级匹配。该算法在分割精度上超越了当前大多数主流图像分割算法，同时保证时间复杂度在同一个级别。

• 融合改进强化学习的认知无线电抗干扰决策算法

  朱芮，马永涛，南亚飞，张云蕾

  针对认知无线电环境中认知用户易受到干扰的问题，研究了具有跳频功能的认知用户与智能感知功能的干扰器之间的相互作用。为了充分利用无线电频谱资源，在综合考虑信道选择和功率分配的基础上，设计了以认知用户的频谱能效性能为参考标准的效用函数，并将改进强化学习算法融入认知学习决策引擎中。决策算法通过将认知环境与决策引擎的交互建模为强化学习中环境与智能体的交互，探索最大的动作奖励反馈给认知决策引擎，在交互过程中得到自适应的优化策略选择。仿真结果表明，提出的算法能够较快速地收敛，选择的策略能够有效地优化认知用户在干扰情况下的性能，比随机策略的性能提高50%以上。

• 概念格共有与独有属性（对象）的关系研究

  闫梦宇，李金海

  Wille概念格可用于共有属性（对象）的数据分析，而面向对象概念格和面向属性概念格可用于独有属性（对象）的数据分析，这两种数据分析方法在形式概念分析理论中均属于热点研究问题。为了区分这两种数据分析方法，首先引入了共有属性（对象）与独有属性（对象）的概念，对它们的算子性质进行了研究。其次围绕命题“共有属性（对象）是独有属性（对象）”展开讨论。具体地，证明了该命题的充分条件和必要条件均不成立，并提出了该命题成立的充要条件；在此基础上，表明了一个对象属性序对既是共有概念又是独有概念时，在概念序关系意义下它是唯一的，即不存在比该序对更大的概念，也不存在比该序对更小的概念。最后从共有与独有属性（对象）的角度给出了Wille概念格、面向对象概念格和面向属性概念格的异同。

• 自然最近邻优化的密度峰值聚类算法

  金辉，钱雪忠

  针对现有的基于密度的聚类算法存在参数敏感，处理非球面数据和复杂流形数据聚类效果差的问题，提出一种新的基于密度峰值的聚类算法。该算法首先根据自然最近邻居的概念确定数据点的局部密度，然后根据密度峰局部密度最高并且被稀疏区域分割来确定聚类中心，最后提出一种新的类簇间相似度概念来解决复杂流形问题。在实验中，该算法在合成和实际数据集中的表现比DPC（clustering by fast search and find of density peaks）、DBSCAN（density-based spatial clustering of applications with noise）和K-means算法要好，并且在非球面数据和复杂流形数据上的优越性特别大。