基于有效距离的谱聚类算法

在现有多种距离度量和传统谱聚类算法的基础上,提出了一种新的基于有效距离的谱聚类算法(spectral clustering based on effective distance,SCED)。SCED算法通过稀疏重构系数来构建样本与样本之间的有效距离,从而代替传统谱聚类算法中的欧氏距离,进行样本之间的相似度评估。与传统距离度量相比,有效距离不仅利用了样本对之间的距离信息,同时考虑了目标样本与其他所有相关样本之间的距离信息,因而该距离度量具有全局特性。在UCI标准数据集上的实验结果表明,SCED算法能有效提高聚类效果。     

基于距离度量学习的集成谱聚类

无监督学习聚类算法的性能依赖于用户在输入数据集上指定的距离度量,该距离度量直接影响数据样本之间的相似性计算,因此,不同的距离度量往往对数据集的聚类结果具有重要的影响。针对谱聚类算法中距离度量的选取问题,提出一种基于边信息距离度量学习的谱聚类算法。该算法利用数据集本身蕴涵的边信息,即在数据集中抽样产生的若干数据样本之间是否具有相似性的信息,进行距离度量学习,将学习所得的距离度量准则应用于谱聚类算法的相似度计算函数,并据此构造相似度矩阵。通过在UCI标准数据集上的实验进行分析,结果表明,与标准谱聚类算法相比,该算法的预测精度得到明显提高。     

半监督极大熵聚类的研究

聚类是一门非常重要的技术.所谓聚类就是按照某种度量(相似性度量、不相似性度量或距离),根据一定的准则将个体集合分成若干类,使得同类个体之间的相似程度大于不同类个体之间的相似程度即做到"物以类聚".半监督聚类算法研究无监督学习中如何利用少量的监督信息来提高聚类性能,目前正得到不断应用.针对前人提出的半监督模糊聚类,本文为了验证该种半监督学习方法是否可以用于其它聚类算法,对极大熵算法进行了改进,将半监督距离学习引入极大熵聚类,生成半监督极大熵聚类算法,并通过实验证明极大熵聚类算法通过半监督方法改进之后确实有效.     

基于半监督距离学习和多模态信息的图像聚类

通过融合图像中不同模态的信息并利用少量带标记的图像进行半监督距离学习,来对图像进行聚类。首先,提取彩色图像中RGB颜色空间的直方图信息、纹理信息,并采用SIFT算法提取Bag of Words来重新表达图像,从而基于图像的颜色特征、纹理特征以及语义特征,建立图像的多模态表达机制,将原始图像投射到表达空间;然后,利用少量标记的图像,通过半监督距离学习,获得图像在多模态信息空间的相似性度量;最后,通过半监督聚类方法,实现图像分组,在多个图像数据库中验证提出的方法的有效性。     

基于最近邻原则的半监督聚类算法

基于最近邻原则的半监督聚类算法是以基于最近邻的聚类中心求解算法为基础的。在基于最近邻的聚类中心求解算法中,用相似度矩阵记录数据点间的相似程度,由目标函数最小值求得聚类的类中心点。在基于最近邻原则的半监督聚类算法中,根据约束信息来调整相似度矩阵G,数据点间相似度的变化引起了数据点间加权欧式距离的变化,由此更新加权欧式距离矩阵M,最后执行聚类中心求解算法完成聚类。大量实验结果表明,该算法能获得较好的聚类结果。     

基于测地距离的半监督增强

在许多模式识别任务中,研究者常常使用有标记样本的信息,而忽略无标记样本信息,但在现实生活中有标记样本的获得可能需要花费大量的人力、物力、财力,而无标记数据的获得却相对容易得多。如何利用无标记的数据来增强分类器的性能成为近年来模式识别中的研究热点。在以往的半监督增强学习中,主要是根据无标记样本和有标记样本的相似度来利用无标记样本的,相似度主要使用欧氏距离来度量,而欧氏距离只反映样本间的空间位置关系,没有反映样本间的流形信息。因此,提出了基于测地距离的半监督增强学习算法,从而可以反映样本空间的流形信息。多个数据库上的实验结果表明提出算法的有效性。     

基于余弦距离选取初始簇中心的文本聚类研究

文本聚类是文本信息进行有效组织、摘要和导航的重要手段,其中基于余弦相似度的K-means算法是最重要且使用最广泛的文本聚类算法之一。针对基于余弦相似度的K-means算法改进方案设计困难,且众多优异的基于欧氏距离的K-means改进方法无法适用的问题,对余弦相似度与欧氏距离的关系进行探讨,得到标准向量前提下二者的转化公式,并在此基础上定义一种与欧氏距离意义相近关系紧密的余弦距离,使原有基于欧氏距离的K-means改进方法可通过余弦距离迁移到基于余弦相似度的K-means算法中。在此基础上理论推导出余弦K-means算法及其拓展算法的簇内中心点计算方法,并进一步改进了聚类初始簇中心的选取方案,形成新的文本聚类算法MCSKM++。通过实验验证,该算法在迭代次数减少、运行时间缩短的同时,聚类精度得到提高。     

面向时间序列的鲁棒性半监督模糊C均值聚类

针对时间序列模糊C均值聚类算法对噪声数据敏感,及其未能将数据中少量已标记数据所包含的监督信息进行有效利用的问题,提出了一种改进的鲁棒性半监督模糊C均值聚类算法。该算法中先使用马氏距离提出一种样本不确定性分析方法,并加入到半监督模糊C均值聚类建模中,以消除噪声点的影响。并改进半监督模糊C均值聚类的部分监督机制来加大已标记数据的监督能力。采用能够弹性度量时间序列相似性的时间扭曲编辑距离代替欧氏距离进行聚类。通过对7组公开的时间序列数据集进行实验对比,结果表明所提算法具有良好的聚类效果。     

有效距离在聚类算法中的应用

聚类分析是数据挖掘领域的重要组成部分之一,而度量学习是聚类分析中的关键性步骤。传统聚类算法中通常使用欧氏距离进行距离度量,但是欧氏距离只关注两两样本之间的距离关系,并没有顾及数据的全局性分布结构。考虑到数据的全局性结构信息,提出了一种新的具有全局性的度量方法——有效距离度量(effective distance metric),其主要思想是通过稀疏重构的方法计算数据样本之间的有效距离。进一步地,将有效距离应用到K-means、K-medoids和FCM(fuzzy C-means)3种经典聚类算法中开发了3种基于有效距离的聚类算法,即EK-means,EK-medoids和EFCM聚类算法。通过与传统聚类算法在UCI标准数据集上的实验结果进行比较,验证了基于有效距离的聚类算法能显著提高聚类效果。     

基于传递距离的谱聚类算法

谱聚类算法受到度量中尺度因子的影响,同时传统谱聚类算法通过欧氏距离度量样本间相似性也不准确。针对上述问题,提出一种基于传递距离的谱聚类算法。算法首先通过改进传统谱聚类中的度量方式,用基于传递距离的度量方式度量样本间相似性,并构建传递矩阵,接着用传递矩阵做相似度变换构建拉普拉斯矩阵,最终通过求特征值和特征向量完成聚类。基于传递距离的谱聚类算法在人工数据集及UCI数据集上均取得了良好的聚类结果,具有较好的鲁棒性和有效性。     

The “dead reckoning” signed distance transform

Consider a binary image containing one or more objects. A signed distance transform assigns to each pixel (voxel, etc.), both inside and outside of any objects, the minimum distance from that pixel to the nearest pixel on the border of an object. By convention, the sign of the assigned distance value indicates whether or not the point is within some object (positive) or outside of all objects (negative). Over the years, many different algorithms have been proposed to calculate the distance transform of an image. These algorithms often trade accuracy for efficiency, exhibit varying degrees of conceptual complexity, and some require parallel processors. One algorithm in particular, the Chamfer distance [J. ACM 15 (1968) 600, Comput. Vis. Graph. Image Process. 34 (1986) 344], has been analyzed for accuracy, is relatively efficient, requires no special computing hardware, and is conceptually straightforward. It is understandably, therefore, quite popular and widely used. We present a straightforward modification to the Chamfer distance transform algorithm that allows it to produce more accurate results without increasing the window size. We call this new algorithm Dead Reckoning as it is loosely based on the concept of continual measurements and course correction that was employed by ocean going vessel navigation in the past. We compare Dead Reckoning with a wide variety of other distance transform algorithms based on the Chamfer distance algorithm for both accuracy and speed, and demonstrate that Dead Reckoning produces more accurate results with comparable efficiency.     

三维带符号的欧氏距离变换及其应用

距离变换是图像处理中历史悠久的研究课题．该文将二维带符号的欧氏距离变换推广到三维，对其进行了优化，分析了它的计算复杂度，并应用于解决计算机图形学中的两个重要问题：第一，将图形对象的三角网格表示转换为它的距离场表示．即首先将三角网格模型离散为体素表示，利用三维带符号的距离变换，将求空间一点到图形对象的最短距离的全局搜索过程，转化为求这一点到离它最近的特征体素所包含的图形对象部分的局部搜索过程；第二，利用类似的思想，求两张空间曲面之间的最短距离．     

软硬件测试中预确定距离测试

在随机测试的基础上提出了VLSI电路测试中的一个新概念,即预确定距离测试.随机测试广泛应用于软硬件测试中已经有多年了.众所周知,随机测试中每个测试码都是随机选取的而不管它是否与先前生成的测试码重复.尽管由于测试码选取的随机性使得随机测试并不是十分有效,但是对它作了一些实质性修改从而大大提高了它的测试效率.在预确定距离测试中,总是选择总距离最大的测试码来进行测试,以便使得该测试码所检测到的故障与先前的测试码所检测到的故障尽可能地不同.还详细介绍了构造一个预确定距离测试序列的生成算法,并将其应用到软件测试中.最后,从基准电路上获得的实验结果以及从理论上的分析也表明这种新方法的有效性.     

一种人脸表情分类的新方法——Manhattan距离

提出了一种利用Manhattan距离进行人脸表情分类的新方法。Manhattan距离计算出具有不同模式的两个对象的距离更大。在实验中,比较了Manhattan距离、欧氏距离、余弦距离在人脸表情分类中的性能,得出Manhattan距离比另外两类距离有着更好的识别效果。     

准完全最大距离伪随机测试研究

对超大规模集成电路进行随机测试的测试码之间的距离作了定量分析,在此基础上,改进了最大距离随机测试算法中测试码的生成方法,使得所生成的伪随机测试码集合同时达到最大海明距离与近似最大笛卡尔距离。因此每一个测试码可以尽可能多地独立检测到更多不重复的故障。进而提出了准完全最大距离测试新算法的思想和构建理论,并详细阐述了该算法的执行流程。在ISCAS'85基准电路上进行的大量实验数据分析表明,本方法确实有效地提高了随机测试效率,降低了随机测试成本。     

点到任意多面体距离的快速计算方法

提出了一种快速计算空间点到任意多面体的有符号距离的方法,该方法以空间点为中心,采用动态搜索技术,能够快速准确地获得一个含多面体最近体元素在内的候选面片集,而且在一般情况下该候选集都足够小,从而对计算空间点到复杂多面体的最近距离起到明显的加速作用,与采用层次结构表示的方法相比,此方法避免了频繁计算点到各层次结构的距离,本算法可应用在需大量距离计算的环境,如距离场计算、虚拟环境下的碰撞检测,机器人运动规划及数据控加工过程的干涉检查等。     

How social distance shapes human–robot interaction

This paper investigates how social distance can serve as a lens through which we can understand human–robot relationships and develop guidelines for robot design. In two studies, we examine the effects of distance based on physical proximity (proxemic distance), organizational status (power distance), and task structure (task distance) on people׳s experiences with and perceptions of a humanlike robot. In Study 1, participants (n=32) played a card-matching game with a humanlike robot. We manipulated the power distance (supervisor vs. subordinate) and proxemic distance (close vs. distant) between participants and the robot. Participants who interacted with the supervisor robot reported a more positive user experience when the robot was close than when the robot was distant, while interactions with the subordinate robot resulted in a more positive experience when the robot was distant than when the robot was close. In Study 2, participants (n=32) played the game in two different task distances (cooperation vs. competition) and proxemic distances (close vs. distant). Participants who cooperated with the robot reported a more positive experience when the robot was distant than when it was close. In contrast, competing with the robot resulted in a more positive experience when it was close than when the robot was distant. The findings from the two studies highlight the importance of consistency between the status and proxemic behaviors of the robot and of task interdependency in fostering cooperation between the robot and its users. This work also demonstrates how social distance may guide efforts toward a better understanding of human–robot interaction and the development of effective design guidelines.     

基于类别距离和Bhattacharyya距离的雷达信号特征评价

从瞬时自相关法、小波变换法和时频原子法提取的脉内特征比较分析入手,提出了一种新的最优特征评价准则。以类内距离、类间距离和Bhattacharyya距离为基础,从特征的空间分布和错误识别率的上界等方面对不同算法提取出的脉内特征进行分析,实现了最优特征的选择。实验的仿真结果表明,这种最优特征评价准则是有效的,为雷达辐射源信号的特征评价提供了有意义的参考。     

Fostering Library as a Place for Distance Students: Best Practices From Two Universities

The concept of library as a place is now in action in many academic libraries: from physical library spaces to Web presences. In the constantly growing market of online and distance learning, however, libraries must foster library as a place for students who may never set foot in the physical building. This article provides a profile of two universities serving two very different bodies of distance students as well as the challenges associated with these populations. These libraries work to provide services to distance students that cultivate the library as a place to go for learning, research, and support by focusing on six categories: access, environment, resources, instruction, availability at the point of need, and “being real.” Tangible examples and best practices are provided throughout. This article is based on a presentation given at the 15th National Conference of the Association of College and Research Libraries in Philadelphia in March 2011.     

改进的边界距离变换算法在虚拟内窥镜中应用

为提高虚拟内窥镜实现中提取中心路径的时间效率,改善虚拟内窥镜的实时漫游,边界距离变换算法是提取中心路径的常用算法.上述算法在建立边界距离场和源距离场时非常耗时,故实时性很差.针对建立两个场非常耗时的缺点,提出定义超大数组,建立体素点ID值和体素点在体素点集中位置的一一对应关系,减少在确定体素点位置时对体素集的扫描次数,从而提高算法的效率.实验结果表明,改进后的算法时间效率高,实时漫游效果好,速度快,提取的中心路径漫游效果好,实现了虚拟漫游效果,具有一定的实际应用与理论研究价值.