摘要:研究加速K-medoids聚类算法，首先以PAM（partitioning around medoids）、TPAM（triangular inequalityelimination criteria PAM）算法为基础给出两个加速引理，并基于中心点之间距离不等式提出两个新加速定理.同时，以O（n+K²）额外内存空间开销辅助引理、定理的结合而提出加速SPAM（speed up PAM）聚类算法，使得K-medoids聚类算法复杂度由O（K（n-K）²）降低至O（（n-K）²）.在实际及人工模拟数据集上的实验结果表明：相对于PAM，TPAM，FKMEDOIDS（fast K-medoids）等参考算法均有改进，运行时间比PAM至少提升0.828倍.

摘要:随着并行计算时代的到来，形式概念的并行计算成为形式概念分析领域的研究热点之一.以属性拓扑为基本表示形式，通过属性拓扑的图特性进行并行概念计算算法设计.首先，根据属性拓扑中属性的伴生关系对属性拓扑进行自下而上的分解，将一个整体拓扑分解为若干个子拓扑；其次，根据属性间的相关关系去除各子拓扑间的概念耦合，保证不同子拓扑在概念计算层面的各自独立性，以避免后期合并运算的大规模时间消耗；最后，在各子拓扑上进行概念计算，并将各子拓扑概念直接累加可得原始背景的全部概念集合.实验结果表明：所提方法不但可以无重复地计算全部概念，而且可以根据硬件平台情况提高计算效率，减少概念计算所需时间.

摘要:孪生参数化不敏感支持向量回归机（twin parametric insensitive support vector regression，简称TPISVR）是一种新型机器学习方法.与其他回归方法相比，TPISVR在处理异方差噪声方面具有独特的优势.标准TPISVR的训练算法可以归结为在对偶空间求解一对具有不等式约束的二次规划问题.然而，这种求解方法的时间消耗比较大.引入最小二乘思想，将TPISVR的两个二次规划问题转化为两个线性方程组，并在原始空间上直接求解，提出了最小二乘孪生参数化不敏感支持向量回归机（least squares TPISVR，简称LSTPISVR）.为了解决LSTPISVR的参数选择问题，提出了混沌布谷鸟优化算法，并用其对LSTPISVR的参数进行优化选择.在人工数据集和UCI数据集上的实验结果表明：LSTPISVR在保持精度不下降的情况下，具有更高的运行效率.

摘要:广义弧相容是求解约束满足问题应用最广泛的相容性，MDDc，STR2和STR3是表约束上维持广义弧相容应用较多的算法，其中，MDDc基于对约束压缩表示的思想，将表约束表示成多元决策图，对各个元组之间存在较多交叠部分的约束具有很好的压缩效果；STR3同STR2一样，基于动态维持有效元组的思想，当元组集规模缩减较慢时，STR3维持广义弧相容的效率高于STR2.通过深入分析发现，MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR，对于同一操作，可以根据回溯搜索不同阶段的局势，自适应地选择代价最小的实现方法.得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异，AdaptiveMDDc和AdaptiveSTR相比，原算法速度提升显著，其中，AdaptiveSTR在一些问题上相比STR3提速3倍以上.

摘要:隐喻理解已成为语言学、认知学、计算机科学等研究的重要课题，也是自然语言处理中不可避免的任务.提出一种基于相关性约束的隐喻理解方法，利用隐含的相关角度计算目标域和源域的相关程度.首先，基于词、词的主题及语篇的主题扩展出多层次的语义表示；然后，利用上下文信息的相关关系，构建多层次的相关性模型，模型通过多种角度的相关关系将跨层次的语义信息关联起来；接着，采用random walk的方法，通过迭代计算获得隐含角度的相关关系；最后，选择与目标域具有最大相关度的属性作为隐喻理解的结果.将模型应用到隐喻理解任务中，实验结果表明，该方法能够有效地实现隐喻自动理解.

摘要:中文微博的大数据、指数传播和跨媒体等特性，决定了依托人工方式监控和处理中文微博是不现实的，迫切需要依托计算机开展中文微博情感自动分析研究.该项研究可分为3个任务：中文微博观点句识别、情感倾向性分类和情感要素抽取.为完成上述任务，研制了一个评测系统：通过构建多级词库、制定成词规则、开展串频统计等给出一种基于规则和统计的新词识别方法，在情感词和评价对象的依存模式的基础上给出基于词语特征的观点句识别算法；以词序流表示文本的LDA-Collocation模型，采用吉布斯抽样法推导了算法，实现中文微博情感倾向性自动分类；针对中文微博情感要素抽取召回率较低的问题，利用依存关系分析理论，按主语类和宾语类把依存模式分为两类，建立了6个优先级的评价对象和情感词汇的依存模式，通过评价对象归并算法实现计算机自动抽取情感要素.实验包括两个部分：一是参加NLP&CC2012的公开评测，所提方法在微博观点句识别任务中的准确率为第2，在中文微博情感要素抽取任务中的准确率和F值均为第2，验证了该算法的实用性；二是在分析公开评测结果的基础上，分别比较了参加公开评测的各类算法在处理中文微博情感分析时的效率，给出了相关结论.

摘要:数据收集是无线监测网络的关键环节.利用无人机进行数据收集的本质是通过无人机的移动代替网络中的转发节点，减少数据从源节点到基站的转发次数，有效节约监测网络能量，从而成为未来发展的趋势.现有的研究关注如何利用无人机有限的能量获得更多的数据，缺乏对获取数据的价值评估，从而导致无人机数据收集能效比不高.如何利用无人机最少的能量付出在监测区域获取最大的数据价值，其难点在于数据价值是针对不同应用的主观评价，而不同节点获取的数据价值如何比较，目前还缺乏统一的标准.可以发现，数据相似节点的数据价值存在相似性.在此基础上，提出了一种数据收集方法OnValueGet，利用关键性代表节点的数据，最大程度地近似代表整个监测区域的数据，从而在能量约束下获得最大数据价值.核心思想在于：从分析感知数据的时空相似性入手，确定数据价值较高的感知节点，即数据关键节点.在应用的误差范围内，它们采集的数据可以近似表示全部网络感知节点采集的数据.无人机以数据关键节点为数据采集的核心目标，在能量有限的情况下，根据遇到的障碍物和节点感知到数据的异常与否，动态地规划数据收集路线，从而使收集到的数据具有最大价值，显著提升数据收集的能效比.

摘要:相似连接是数据管理领域的一个热门话题，已在社会生产生活中得到广泛应用.然而，现有的相似连接方法并不能满足真实世界不断增长的客观需求.通过引入定义在多种数据类型上的满足操作符和每条数据的独立阈值，定义了一种相似连接——泛化双向相似连接.这种连接扩展了相似连接的应用范围.同时，还提出了两种高效的解决泛化双向相似连接问题的方法：子连接集算法和映射-过滤-验证算法.通过真实与合成数据集上的大量实验，得出了所提方法的正确性和有效性.

摘要:在深网数据集成过程中，用户希望仅检索少量数据源便能获取高质量的检索结果，因而数据源选择成为其核心技术.为满足基于相关性和多样性的集成检索需求，提出一种适合小规模抽样文档摘要的深网数据源选择方法.该方法在数据源选择过程中首先度量数据源与用户查询的相关性，然后进一步考虑候选数据源提供数据的多样性.为提升数据源相关性判别的准确性，构建了基于层次主题的数据源摘要，并在其中引入了主题内容相关性偏差概率模型，且给出了基于人工反馈的偏差概率模型构建方法以及基于概率分析的数据源相关性度量方法.为提升数据源选择结果的多样性程度，在基于层次主题的数据源摘要中建立了多样性链接有向边，并给出了数据源多样性的评价方法.最后，将基于相关性和多样性的数据源选择问题转化为一个组合优化问题，提出了基于优化函数的数据源选择策略.实验结果表明：在基于少量抽样文档进行数据源选择时，该方法具有较高的选择准确率.

摘要:基于压缩感知的数据收集算法在能量受限、数据冗余的无线传感网中有巨大的应用潜力，现有研究大多假定无线链路理想.通过实验说明，有损链路丢包会严重影响压缩感知数据收集算法的数据重构质量.提出了一种基于重传与时间序列相关性预测（CS data gathering based on retransmission and time series correlation prediction，简称CS-RTSC）的数据收集算法，将有损链路上的丢包建模为随机丢包和块状丢包，设计了基于滑动窗统计的丢包类型预判算法，在检测到链路丢包时判断丢包类型，对随机丢包采用重传恢复，对块状丢包设计了基于时间序列相关性预测算法恢复.仿真结果表明：该算法能够有效降低有损链路丢包对CS数据收集的影响；在网络丢包率达到30%时，CS数据重构的相对误差仅比理想链路下的CS相对重构误差高0.1%.

摘要:近年来，安全多方计算一直是密码领域的一个研究热点，保密几何计算是其一个重要分支.过两私有点坐标安全地计算一条直线问题，在空间信息安全方面有重要应用前景.首先，提出一个由加密方计算（或选取）加密底数的Paillier变体同态加密方案，并证明了其在标准模型下对适应性选择明文攻击（adaptive chosen-plaintext attack，简称CPA）是安全的；然后，在半诚实模型下，基于该变体同态加密方案设计了一个能够安全计算过两私有点直线的协议.还可以将此协议推广应用到可以归约为安全计算两私有点坐标差商的所有安全多方几何计算问题，从而解决了原有的基于同态加密体制的安全两方计算协议存在的信息泄露问题.

摘要:Radon变换是一种用于形状分析的非常有用的数学工具.它是一种无损变换，利用该变换，可以方便地抽取到目标形状结构的重要视觉特征.但因为该变换含有目标的大小、位置和方向信息，所以并不能将其直接用于目标形状的识别任务.现有的基于Radon变换的形状分析方法虽然通过各种途径消除这些信息，以保证抽取的形状特征的不变性，但这些操作也损失了大量有用的形状信息，使得描述的精度有限.为解决该问题，提出了一种λ-变换的数学工具.该变换利用平行直线的相对位置关系（用一个属于区间[0，1]的变量r来表达）和它们对形状函数的积分，构造了一个变量r和直线的方向角变量θ的二维函数，用于形状的描述和差异性度量.从理论上分析了λ-变换满足对平移、缩放的不变性，以及对旋转变换仅使其在θ维发生平移的特性，也从理论上分析了λ-变换对Radon变换信息的保持特性，而这种保持特性使得该变换比其他基于Radon变换的形状描述子具有更高的描述精度.λ-变换的有效性和相较于其他同类方法的优越性，通过几组常用形状图像检索实验得到验证.

摘要:传统有意义图像分存方案存在认证能力偏低、攻击后不具备修复能力或修复能力整体较弱以及嵌入掩体视觉质量不高等问题.针对以上问题，提出一种结合非等量备份和双认证自修复有限域图像分存方案，包含分存和恢复阶段.在分存阶段，首先对密图做1级离散小波变换，取LL子带按密钥置乱，并对置乱后LL子带每个系数比特按比特位重要程度分组进行非等量备份来构造与密图等大备份图；然后对密图和备份图每个像素及其对应7K-13位认证信息在GF（2⁷）有限域进行（K，N）分存，将产生的7位分存信息和使用密钥产生的1位认证信息使用优化LSB法嵌入到N个掩体2×2分块中；最后对密钥进行（K，N）分存，将子密钥对应的MD5值公开到第3方公信方并将子密钥和嵌入掩体分发给参与者.在恢复阶段，首先对参与者提供的子密钥真实性进行检验，利用检验通过子密钥对密钥进行恢复；其次对分发掩体2×2分块嵌入的分存信息和1位认证信息使用密钥进行第1重认证，利用第1重认证通过分存信息重建GF（2⁷）有限域分存多项式，提取出密图和备份图每个像素及其对应的7K-13位认证信息并对其进行第2重检验和构造初步密图、备份图以及认证图；再次由备份图和认证图重构密图LL子带，然后对其做逆置乱和逆离散小波变换得到密图修复参考图；最后对认证图每一个认证不通过秘密像素，根据其周围像素认证情况选择多项式插值拟合或进行修复参考图像素替代修复.理论和实验结果表明，与现有方法相比，所提方法具备更好的认证能力，并能充分使用双认证和自然图像邻近像素相关性来提升其攻击后修复能力，且分发掩体具备较高视觉质量.

摘要:针对稀疏子空间聚类和最小二乘回归子空间聚类求得的表示系数存在类内过于稀疏和类间过于稠密的问题，利用A₂范数，提出一种基于欧氏距离的且具有组效应的加权低秩子空间聚类算法，该算法通过基于欧氏距离的加权方式，使得最终的表示系数在保证同一子空间数据点联系的同时，减小不同子空间数据点之间的联系.利用该表示系数建立相似矩阵J，将J应用到谱聚类得到聚类结果.实验结果表明，与当前流行的算法比较，该算法取得了较好的聚类效果.

摘要:STL（stereo lithography）作为3D扫描数据和快速原型制造事实上的标准，广泛应用于娱乐、制造业和Internet等领域.随着3D模型越来越复杂，数据量越来越庞大，从STL文件难以快速获得完整拓扑关系且其存在大量冗余信息的缺点，制约了STL网格模型的进一步优化处理与应用.为此，需要针对STL网格模型进行网格重建.针对2维流形的STL三角形曲面网格模型，提出了一种快速的网格重建方法.主要利用删除在重建过程中达到饱和的顶点，以便减少需要比对的顶点数，并结合STL文件数据的相关性来提高顶点搜索与比较的效率.对于非封闭的曲面网格，该算法在提高曲面网格重建效率的同时，还有效地提取了曲面网格模型的边界信息.另外，重建的曲面网格数据文件减少了存储空间，有效地去除了冗余数据.实验结果表明了该算法的高效性及鲁棒性.

摘要:智能手机后台应用的网络请求极大地影响着待机时间.已有的工作提出了节省手机能耗的应用网络请求调度算法，然而，如何将算法自动地应用到既有手机系统，仍面临着巨大挑战：（1）在没有应用源代码的情况下，实现单个应用内的网络请求合并；（2）在不对操作系统进行任何修改的情况下，按需合并多个应用中的网络请求.以安卓应用为目标，给出了一种通过自动程序转换来支持现有移动应用中网络请求延迟调度的方法及其框架实现——DelayDroid，用以提升手机整体待机时间.通过字节码分析和程序自动转换技术解决以上挑战.与已有工作相比，DelayDroid有两大特色：一是程序转换自动执行；二是转换后的应用可支持多应用的后台网络请求调度，该调度机制可以降低安卓应用的待机耗电.此外，DelayDroid被设计为可对只有dex字节码的安卓应用进行转换，更具实用性.

摘要:目前大数据处理过程较少关注任务所处理数据间的依赖关系，在任务执行过程中可能产生大量数据迁移，影响数据处理效率.为减少数据迁移，提升任务执行性能，从数据关联性及数据本地性两个角度出发，提出了一种数据关联性驱动的大数据处理任务优化调度方案：D³S²（data-dependency-driven scheduling scheme）.D³S²由两部分组成：（1）数据关联性感知的数据优化放置机制（dependency-aware placement mechanism，简称DAPM），根据日志信息挖掘数据关联性，进而将强关联的数据聚合并放置于相同机架上，减少了跨机架的数据迁移；（2）数据迁移代价感知的任务优化调度机制（transfer-aware scheduling mechanism，简称TASM），完成数据放置后，以数据本地性为约束，对任务进行统一调度，最小化任务执行过程中的数据迁移代价.DAPM和TASM互相提供决策依据，以任务执行代价最小化为目标不断迭代调整调度方案，直至最优任务调度方案.在Hadoop平台上进行的实验结果表明：较之原生Hadoop，在不增加作业完成时间的基础上，D³S²减少了作业执行过程中的数据迁移量.