基于蛋白质相互作用网络的聚类算法研究

蛋白质相互作用网络是计算机科学技术的一个新研究领域。蛋白质相互作用网络中结点之间的距离度量需要通过基于网络的最短路径距离来重新定义,其计算代价高,这使得已有的基于欧几何距离的聚类算法不能直接运用到这种环境中。因此,通过蛋白质相互作用网络的特征提出了一种新的聚类算法。算法使用网络中的边和结点信息来缩减搜索空间,避免了一些不必要的距离计算。实验结果表明,算法对于真实的蛋白质相互作用网络中的结点聚类是高效的。     

基于道路网络的约束聚类

聚类法是最重要的空间数据分析方法之一。在大多数真实的应用中,对受限于网络空间的数据访问和分析更有意义（如道路网络上对象的分析）。目前已有一些道路网络聚类方法,但都是基于理想的抽象空间,没有考虑现实存在的约束条件（如交通限制信息）,因此不能直接应用到现实环境中。本文提出了带约束条件的道路网络模型,扩展了已有的聚类算法。算法的实验结果表明,算法对真实的道路网络中的对象聚类是高效的。     

基于空间网络的多阈值对象聚类

为了提高空间网络上对象聚类的准确性,发现潜在的聚类结果,分析了多阈值选择的必要性,提取了空间网络上(以道路网为例)对象的相似性特征,首次提出了基于空间网络的支持向量回归多阈值方案,并将多阈值方案应用到已有的基于道路网络的对象聚类方法中,解决了已有聚类方法中聚类阈值选择困难的问题.性能分析及实验结果表明,多阈值对象聚类方案对真实的道路网络中的对象聚类是有效的.     

道路网络环境下的近似反k最近邻查询算法

针对欧式空间中基于R树索引结构的反最近邻查询技术不适用于道路网环境,利用任意度量空间中的M树索引结构代替R树索引结构,进行道路网络中的反最近邻查询处理.然而,由于网络距离的计算代价高的问题,使得基于M树索引的反k最近邻查询效率很低.因此,采用道路网络嵌入技术,映射道路网络到高维向量空间,简单的L∞距离准确近似计算网络距离.在此基础上,提出道路网中近似反k最近邻查询的ARkNN算法,并对本文L∞距离近似网络距离的质量、k-中心聚类算法选取参考点的有效性和ARkNN算法的查询效率进行了实验验证.     

遗传聚类的社团结构发现

近年来在复杂网络中发现社团的结构引起了广泛的关注,目前已经提出了一些采用进化计算来分析复杂网络社团结构的方法．但大部分算法还存在处理过程复杂,空间复杂度过高等问题．通过确定网络节点的距离关系和聚类中心,提出一种新的基于遗传聚类的社团发现算法．将该算法用于真实网络的社团发现,实验结果验证了算法的可行性和有效性．     

基于属性—关系综合相似度的聚类算法*

为弥补属性空间聚类方法只关注对象属性信息以及结构聚类方法只关注对象间关系信息的不足,提出一种基于属性-关系综合相似度的聚类算法.在构建基于属性距离的有权网络后,算法给出对象间综合相似度以及类间综合相似度的计算方法,并设计相应策略自底向上实现聚类.与属性空间聚类和结构聚类方法相比,该算法由于兼顾了属性和关系信息而具有更高...     

道路网络环境中的多对象最近邻查询

多对象最近邻查询(all nearest neighbors query)在地理信息系统、城市规划和资源分配等领域有着广泛的实际应用,也可作为某些聚类算法或应用的核心模块.针对欧氏空间的查询处理算法不能直接适用于道路网络环境,通过重复调用道路网络环境下的最近邻查询算法来进行多对象最近邻查询处理的计算代价较大,利用M树对道路网络中的边建立索引结构,基于该索引,提出了一个新颖的多对象最近邻查询处理算法BANNS(batched all nearest neighbors search).实验显示BANNS能稳定、快速、准确地处理道路网络中的多对象最近邻查询.     

一种具有方向特点的网络对象聚类算法

对分别采用欧氏距离和网络距离作为相似性测度的聚类方法进行分析,并从空间网络中对象间着手,提出一种具有方向特点的网络对象聚类算法.算法利用空间网络的邻接关系,将两种距离结合起来作为聚类的相似性测度以提高聚类的精度.算法分析和实验证明,该算法的聚类效果优于单一度量的聚类方法.     

标签共现的标签聚类算法研究

在社会网络中,标签聚类研究可以解决标签冗余和语义模糊等问题。为了提高聚类有效性,提出综合标签共现信息确定标签特征向量,通过特征向量的提取计算相似度,将传统聚类算法中用几何距离计算对象与中心对象的距离改为用皮尔森相关系数计算,提出结合K-means聚类算法对标签进行聚类的标签共现聚类算法,并分析了算法的复杂度。最后对不同聚类算法进行了相关对比实验,实验结果表明该聚类算法效果要好于其他的聚类算法,从而验证了该聚类算法的有效性和可行性。     

基于道路网络的移动对象聚类

现有的基于道路网络对象聚类算法eb-cls采用网络距离描述移动对象间的相似性,没有充分利用对象的时间和空间属性,造成算法不能体现移动对象动态演化的移动模式,频繁更新聚类结果并且聚类精度不理想,执行效率低等问题。针对这些不足,提出基于道路网络的移动对象聚类算法MOBORN（Moving Objects Based on Road Network）,该算法引入时空相似系数,考虑了移动对象速度、方向和位置。当移动对象间的时空相似系数达到给定阈值,将其分到同一聚类,并动态维护聚类结果,减少聚类次数。实验结果证明,与eb-cls算法相比,该算法聚类精度保持在97%以上,运行效率提高了40%。     

移动对象轨迹时空相似性度量方法

在分析移动对象行为时,移动对象轨迹因包含大量的信息而具有重要的作用。在实际应用中移动对象常受限于空间网络而无法利用现有欧氏空间中轨迹及其距离处理技术。分析了道路网络空间轨迹相似性性质,提出一种移动对象轨迹建模的时空表示方法,能有效地将轨迹从道路网络空间转化到欧氏空间;同时提出了一种基于兴趣点POI（Points Of Interesting）距离的轨迹间相似性测量方法,有效地对轨迹进行化简并减少轨迹中节点的数目,从而降低算法时间复杂度。该方法不仅可以用于搜索相似轨迹,还可方便地应用到轨迹聚类的相关工作中。     

Aggregate nearest neighbor queries in road networks

Aggregate nearest neighbor queries return the object that minimizes an aggregate distance function with respect to a set of query points. Consider, for example, several users at specific locations (query points) that want to find the restaurant (data point), which leads to the minimum sum of distances that they have to travel in order to meet. We study the processing of such queries for the case where the position and accessibility of spatial objects are constrained by spatial (e.g., road) networks. We consider alternative aggregate functions and techniques that utilize Euclidean distance bounds, spatial access methods, and/or network distance materialization structures. Our algorithms are experimentally evaluated with synthetic and real data. The results show that their relative performance depends on the problem characteristics.     

Search on transportation networks for location-based service

The issue of how to provide location-based service (LBS) attracted many researchers. In this paper, we focus on a typical situation of LBS which is to provide services for users in cars that move in a road network. To provide such kind of services, an integration method for representing transportation information with a road map is proposed. By using our integration method, since the transportation information of road networks is managed under the spatial index structure created for road networks, spatial queries on them can take advantages of the spatial index structure and achieve an efficient process. Moreover, we discuss path search, region search, nearest neighbor search and continuous nearest neighbor search in this paper, which are based on transportation networks with (or without) considering the static spatial objects outside the transportation networks. Using transportation information and the corresponding real road network, the paper offers evaluations by comparing our representation method and query method with those in related works. The results show a good performance of our methods.     

搜索路网空间中时空相似轨迹

为了分析移动对象行为特征,需要一种度量轨迹间相似性的方法,虽然在欧氏空间检索移动对象相似轨迹的研究较多,但在路网空间这种研究还不多见。在实际应用方面,大多数移动对象位于路网空间而不是欧氏空间。本文研究了路网空间相似轨迹的特性,并提出了一种在路网空间搜索相似轨迹的度量方法。实验结果表明该方法不仅是搜索相似轨迹的实用技术,也是一种较好的轨迹聚类方法     

自适应粒度的道路移动对象聚类算法

以往的聚类算法能够减少道路交通网络中移动对象与中心数据库的通信开销,但聚类粒度的大小是根据经验设定的.分析了影响距离聚类粒度大小的因素,提出用BP网络来训练历史数据,动态地获取距离聚类粒度值和时间粒度值,并把这些粒度值作为新的历史数据来训练网络,使得粒度值能够根据道路交通网络中因素的改变而动态改变,从而产生有效的道路网络聚类,减少通信开销,并预报道路交通的拥堵情况,为最优路径规划提供依据.     

Continuous range-based skyline queries in road networks

With the ever-growing popularity of smartphone devices in recent years, skyline queries over spatial Web objects in road networks have received increasing attention. In the literature, various techniques have been developed to tackle skyline queries that take both spatial and non-spatial attributes into consideration. However, the existing solutions only focus on solving point-based queries, where the query location is a spatial point. We observe that in many real-life applications, the user location is often represented by a spatial range. Thus, in this paper, we study a new problem of range-based skyline queries (CRSQs) in road networks. Two efficient algorithms named landmark-based (LBA) and index-based (IBA) algorithms are proposed. We also present incremental versions of LBA and IBA to handle continuous range-based skyline queries over moving objects. Extensive experiments using real road network datasets demonstrate the effectiveness and efficiency of our proposed algorithms.     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。