不确定树数据库中的动态聚类算法

针对现有的树聚类算法不能适应数据的动态变化和不确定性等问题,研究不确定数据的聚类问题,提出一种在不确定树数据库中的动态聚类算法,有效地解决了因数据的动态变化而导致的无法聚类的问题.首先,提出转变树集、相似分组和树类集等概念来描述一个不确定树数据库的聚类模型.其次,为了更加准确的度量子树之间的相似性,考虑到子树即具有结点语义特征,又具有结构化特性,提出了一种语义相似度计算方法与结构相似度计算方法,同时对两者赋予一定比例的权值并求和得到最终的相似度.再次,设计了一个动态聚类过程,采用自适应获取聚类阈值,较大程度上减少了人为干扰导致聚类结果不准确的影响,使得具有相似结构的子树聚集在同一个相似分组中,不同分组之间的子树相似度达到最小化,同时对每个相似分组,定义一个提取代表性子树的公式,将其作为树类组成树的类集.最后,通过模拟数据和真实环境两部分实验可以表明,算法有效可行,聚类结果较准确且具有较好的运行效率.     

基于结构相似匹配的SQL程序自动评估模型研究

针对SQL语言编程能力评估的多因素影响、界限模糊特性造成的难度和偏差问题,本文提出了基于结构相似度匹配的评估模型(SQL-APAM)。结合静态评估与动态评估方法,给出了模型的整体框架;模型对提交的SQL语句进行规范化、分词处理后,将其转换成等价的单词序列对,进而构建对应的结构树S-tree;使用于代价模型、子结构贡献因子两方面上有所改进的树编辑距离算法计算与目标树的相似性值;最后利用正态分布思想将相似度值映射到成绩区间,并通过相似度阈值来调整影响因素所带来的偏差,给出SQL程序的定量评判结果。最后对模型作了基于数据的实验分析与验证,训练数据集进行参数调整,对模型进行优化。     

一种新的不确定树模式聚类算法

不确定树模式聚类是数据挖掘领域中的一个重要问题,提出了一种新的不确定树模式聚类算法,有效地解决了因数据的不确定性而导致的无法聚类的问题.为了更加准确地度量树模式之间的相似性,提出了一种语义相似度计算方法与结构相似度计算方法.设计了一个动态聚类过程,自适应获取聚类阈值,较大程度上减少了人为干扰导致聚类结果不准确的影响,使得具有相似结构的子树聚集在同一个相似分组中,不同分组之间的子树相似度达到最小化.通过模拟数据和真实环境两部分实验表明,算法有效可行,聚类结果较准确且具有较好的运行效率.     

一种改进的树路径模型在网页聚类中的研究

相似度计算是文本挖掘的基础,也是信息提取过程的关键步骤.对于结构复杂的网页,当前基于传统树路径模型的相似度计算方法在准确性上尚不完善.传统树路径模型未考虑路径出现的先后顺序,并且比较路径相似度时用的是完全匹配,难以在不完全匹配时更精确地描述路径之间的相似度.因此,从网页结构相似度入手,提出了一种改进的树路径模型.该模型充分考虑了兄弟节点之间的关系、路径位置以及路径权重,弥补了传统树路径模型无法表达文档结构和层次信息的缺陷.实验结果表明,该模型提高了识别网页结构相似性的能力,既能对结构差别较大的网页进行良好的区分,又能较好地反映来自同一模板的网页之间的差异性,同时在网页聚类中具有更优的效果.     

基于触发序列集合的过程模型行为相似性算法

过程模型的相似性计算是业务过程管理中不可缺少的任务,广泛应用于组织合并、用户需求变更、模型仓库管理等多个场景.对基于主变迁序列的相似性度量方法 PTS进行研究,并提出了改进方案.通过定义完整触发序列表示模型行为,基于A*算法结合剪枝策略实现触发序列集合间的映射,进而完成模型相似性计算.实验结果表明:该方法较主流的基于模型行为相似性算法,计算合理性有很大提升.     

基于树编辑距离的工作流距离度量方法

在工作流的发现和聚类等应用中,需要对两个工作流模型的距离进行度量。因此,提出一种计算两个不同结构化工作流的距离定量度量方法。首先介绍了结构化工作流,并将每一个结构化工作流转换为流程结构树;然后基于两个结构树之间的树编辑距离来计算工作流之间的距离及相应相似度。该距离度量方法满足距离度量的3个属性,即同实体不可区分性、对称性和三角不等式性质。这些属性使得该距离度量方法可以在工作流模型管理活动中作为定量分析工具。实验结果表明,基于树编辑距离的工作流度量方法是可行的。同时,与基于邻接矩阵的距离度量方法相比,该方法考虑了不同结构之间的语义距离,有效验证了此方法的合理性。     

基于延迟时间Petri网的工作流相似性度量方法

为了解决实时系统中流程相似性的判定问题,提出一种基于流程中活动的拓扑结构和触发点的流程相似性度量方法。采用延迟时间Petri网(Delay Time Petri Nets,DTPN)模型来表示流程,用于找出流程的触发调度;定义活动时间约束路由关系,给出它们之间的距离和相似度计算公式,进而计算出流程之间的相似度;在此基础上设计相关算法,并且分析时间复杂度。通过实例验证了该算法在时间约束工作流相似性度量方面的有效性。     

基于粒子群算法的三维CAD模型相似性计算

为了更加准确地度量两个模型之间的形状差异,提出了一种基于粒子群的模型相似性计算方法。利用面的组成边数来构造面相似度矩阵,通过粒子群算法对该矩阵进行搜索,得到了两个模型之间的最优面匹配序列。根据这个最优面匹配序列,从面相似度矩阵中提取对应的面相似性值。通过累积面之间的相似性来计算模型之间的整体相似性。以此为基础来度量模型之间的差异。实验结果表明：该方法能够准确地度量两个模型之间的相似程度。     

基于SA-BP算法的本体概念语义相似度综合计算

不同作战部队在指挥信息系统测试评估中建立的指标存在异构问题,导致在信息交互和测试数据共享上存在较大困难。实现指标本体概念的映射和集成,建立一个统一的全局指标本体树可以有效地解决该问题,其中本体概念相似度计算的准确性至关重要。针对现有本体概念相似度计算模型中存在的精度不高的问题,提出了基于模拟退火改进BP(Back Propagation)神经网络(Simulated Annealing Back Propagation,SA-BP)算法的相似度综合计算模型。首先,对经典的基于语义距离、信息内容和概念属性的相似度计算模型进行改进,同时提出了基于概念子节点重合度的相似度计算模型;然后,采用SA-BP算法进行相似度综合计算,避免现有方法中人为确定权重的主观性和简单线性加权的不准确性问题;最后,从某作战部队不同单位建立的各异的指挥信息系统评估指标的本体概念中提取样本数据,对相似度综合计算模型进行训练测试。实验数据表明,相比于PSO-BP计算模型和主成分分析确定权值的线性加权计算模型,基于SA-BP算法的相似度综合计算模型的计算结果与专家评价结果的Pearson相关系数分别提升了0.0695和0.1351,达到了极强相关的一致性。实验数据充分说明,模拟退火算法改进的BP神经网络在训练后可以较好地收敛,在综合计算本体概念相似度时更加准确,从而有效地解决了本体概念集成的关键问题。     

基于位置序列的广义后缀树用户相似性计算方法

为了解决移动数据形成的轨迹间用户相似性问题,提出了一种基于位置序列的广义后缀树(LSGST)用户相似性计算方法。该算法首先从移动数据中抽取位置序列,同时将位置序列映射为字符串,完成了对位置序列的处理到对字符串处理的转化工作;然后,构建不同用户间的位置序列广义后缀树;最后,分别从经过的相似地方个数、最长公共子序列、频繁公共位置序列三方面对相似性进行具体计算。理论分析和仿真表明,该算法提出的三个计算指标在计算相似性方面具有理想的效果;除此之外,与构造后缀树的普通方法相比,时间复杂度较低;与动态规划和朴素字符串匹配方法相比,该算法在寻找最长公共子串、频繁公共位置序列时,效率更高。实验结果表明LSGST能够有效测量相似性,同时减少了寻找测量指标时需要处理的轨迹数据量,并在时间复杂度方面明显优于对比算法。     

基于行为序列分析的学习资源推荐算法研究

利用数据挖掘技术分析网络学习行为数据可以挖掘出其隐含的行为规律特征,为学习者提供个性化的学习资源服务。针对现有的数据挖掘算法在对网络学习行为数据进行分析时普遍存在模型适用性不高的问题,提出了一种基于行为序列分析的学习资源推荐算法。首先,提出行为序列及其相关概念的定义,并提出行为序列相似度计算方法;然后提出基于行为序列相似度的协同过滤推荐算法,计算学习者相似度并为待推荐学习者生成学习资源推荐列表;接着给出基于学习风格的推荐方法,将学习者学习风格特征融入推荐过程;最后,给出基于行为序列分析的学习资源推荐算法的模型。提出的算法没有对行为序列的模式进行限制,具有较高的适用性,对深入研究网络学习行为序列数据为学习者提供个性化学习服务具有一定的借鉴作用。     

网络信息搜索匹配算法研究与仿真

研究网络信息搜索问题,提高搜索匹配的准确率。当前网络资源中,信息资源种类繁多,数量巨大,拥有相似特征的信息资源很多,传统的针对资源特征匹配的算法,很难在巨大数量的拥有众多相似特征的网络资源信息中,准确找到需要匹配的资源信息,信息匹配的准确性不高。为了解决这一问题,提出了一种基于语义距离的服务相似度信息匹配方法,首先将数据集用本体语言描述出来,然后对所定义的信息量、本体中的连接路径进行形式化定义,确定两个概念之间的语义距离,进而进行匹配。实验表明,新算法是能够实现海量数据之间匹配的最佳信息搜索方案,摆脱传统方法对于特征的依赖。大幅提高了匹配的准确度,取得了不错的效果。     

Similarity measure models and algorithms for hierarchical cases

Many business situations such as events, products and services, are often described in a hierarchical structure. When we use case-based reasoning (CBR) techniques to support business decision-making, we require a hierarchical-CBR technique which can effectively compare and measure similarity between two hierarchical cases. This study first defines hierarchical case trees (HC-trees) and discusses related features. It then develops a similarity evaluation model which takes into account all the information on nodes’ structures, concepts, weights, and values in order to comprehensively compare two hierarchical case trees. A similarity measure algorithm is proposed which includes a node concept correspondence degree computation algorithm and a maximum correspondence tree mapping construction algorithm, for HC-trees. We provide two illustrative examples to demonstrate the effectiveness of the proposed hierarchical case similarity evaluation model and algorithms, and possible applications in CBR systems.     

基于RFID路径数据的异常路径检测

RFID技术在物流、供应链管理等需要跟踪物品流动的领域的广泛使用产生了大量路径数据。路径数据描述了物品在RFID系统中的移动轨迹, 路径数据中每个节点同时包含地点和时间信息, 使路径数据比一般的序列数据更复杂。针对现有的序列数据异常点检测算法不适合处理路径数据的情况, 对路径数据的异常路径检测进行了研究, 提出适用于路径数据的扩展概率后缀树(EPST)模型和一种采用该模型检测异常路径的方法。该模型用来计算每个路径和路径数据集的相似度, 在计算相似度时主要利用了路径数据的“短期记忆”性质, 同时考虑了地点和时间信息对路径数据相似度的不同影响。实验表明提出的算法能够准确地检测出异常路径, 并具有较低的空间复杂度。     

Distributed workflow mapping algorithm for maximized reliability under end-to-end delay constraint

A distributed scientific workflow mapping algorithm for maximized reliability under certain end-to-end delay (EED) bound is proposed. It is studied in a heterogeneous distributed computing environment, where computing node and communication link failures are inevitable. The mapping decision and the stored table information is distributed among various nodes in order to achieve scalability and robustness, which are especially important for large-scale distributed systems. This Distributed Reliability Maximization workflow mapping algorithm under End-to-end Delay constraint (dis-DRMED) considers both the maximum reliability and the minimum EED objectives in a two-step procedure. In the first step, a mapping algorithm combining iterative Critical Path search and Layer-based priority assigning techniques (CPL) is adopted to minimize the EED by focusing on the optimal allocation of tasks on the critical path. In the second step, tasks on noncritical paths are remapped to improve the overall execution reliability. Simulation results under various system setups demonstrated that dis-DRMED achieved considerably higher reliability values under the same EED constraint compared with some representative workflow mapping algorithms.     

基于完全有限前缀展开的行为等价过程树生成算法

过程树能够兼具过程模型的行为和结构,对简化模型结构的复杂度方面具有重要意义.现有过程树转化仅能将基于块结构的简单过程模型转化为过程树,但是无法将具有复杂结构的过程模型转化过程树.为此,提出了一种基于完全有限前缀展开的行为等价过程树生成算法,用于将与过程树行为等价的过程模型转化为行为等价过程树.该方法首先利用完全有限前缀展开技术分析过程模型,抽取模型的活动关系;其次通过分析活动关系,进而对模型进行重构.最终通过活动关系判断和模型重构的不断迭代操作,构建行为等价过程树.在实验部分通过在测试模型上的实验,验证了该算法在行为等价过程树生成方面的正确性和可行性.     

Fast indexing and visualization of metric data sets usingslim-trees

Many recent database applications need to deal with similarity queries. For such applications, it is important to measure the similarity between two objects using the distance between them. Focusing on this problem, this paper proposes the slim-tree, a new dynamic tree for organizing metric data sets in pages of fixed size. The slim-tree uses the triangle inequality to prune the distance calculations that are needed to answer similarity queries over objects in metric spaces. The proposed insertion algorithm uses new policies to select the nodes where incoming objects are stored. When a node overflows, the slim-tree uses a minimal spanning tree to help with the splitting. The new insertion algorithm leads to a tree with high storage utilization and improved query performance. The slim-tree is a metric access method that tackles the problem of overlaps between nodes in metric spaces and that allows one to minimize the overlap. The proposed "fat-factor" is a way to quantify whether a given tree can be improved and also to compare two trees. We show how to use the fat-factor to achieve accurate estimates of the search performance and also how to improve the performance of a metric tree through the proposed "slim-down" algorithm. This paper also presents a new tool in the slim-tree's arsenal of resources, aimed at visualizing it. Visualization is a powerful tool for interactive data mining and for the visual tracking of the behavior of a tree under updates. Finally, we present a formula to estimate the number of disk accesses in range queries. Results from experiments with real and synthetic data sets show that the new slim-tree algorithms lead to performance improvements. These results show that the slim-tree outperforms the M-tree by up to 200% for range queries. For insertion and splitting, the minimal-spanning-tree-based algorithm achieves up to 40 times faster insertions. We observed improvements of up to 40% in range queries after applying the slim-down algorithm     

HotRank：热度敏感的非结构化数据检索排名算法

为满足用户对非结构化数据检索的需求,分析用户对数据的操作行为,提出一种新型的数据热度敏感的非结构化数据检索排名算法HotRank。通过对数据操作情况(任务、访问次数、编辑时长等)进行日志记录,形成非结构化数据检索数据集。在此基础上,定义数据的任务相似度和数据热度计算方法实现该算法。结合实例仿真,对算法进行评估,并将仿真结果与其他算法进行比较,证明了该排名算法的准确率优于其他算法。     

Bulk construction of dynamic clustered metric trees

Repositories of complex data types, such as images, audio, video and free text, are becoming increasingly frequent in various fields. A general searching approach for such data types is that of similarity search, where the search is for similar objects and similarity is modeled by a metric distance function. An important class of access methods for similarity search in metric data is that of dynamic clustered metric trees, where the index is structured as a paged and balanced tree and the space is partitioned hierarchically into compact regions. While access methods of this class allow dynamic insertions typically of single objects, the problem of efficiently inserting a given data set into the index in bulk is largely open. In this article we address this problem and propose novel algorithms corresponding to its two cases, where the index is initially empty (i.e. bulk loading), and where the index is initially non empty (i.e. bulk insertion). The proposed bulk loading algorithm builds the index bottom-up layer by layer, using a new sampling based clustering method, which improves clustering results by improving the quality of the selected sample sets. The proposed bulk insertion algorithm employs the bulk loading algorithm to load the given data into a new index structure, and then merges the new and the existing structures into a unified high quality index, using a novel decomposition method to reduce overlaps between the structures. Both algorithms yield significantly improved construction and search performance, and are applicable to all dynamic clustered metric trees. Results from an extensive experimental study show that the proposed algorithms outperform alternative methods, reducing construction costs by up to 47% for CPU costs and 99% for I/O costs, and search costs by up to 48% for CPU costs and 30% for I/O costs.     

A vision-based collision avoidance technique for micro air vehicles using local-level frame mapping and path planning

This paper presents a vision-based collision avoidance technique for small and miniature air vehicles (MAVs) using local-level frame mapping and path planning. Using computer vision algorithms, a depth map that represents the range and bearing to obstacles is obtained. Based on the depth map, we estimate the range, azimuth to, and height of obstacles using an extended Kalman filter that takes into account the correlations between obstacles. We then construct maps in the local-level frame using cylindrical coordinates for three dimensional path planning and plan Dubins paths using the rapidly-exploring random tree algorithm. The behavior of our approach is analyzed and the characteristics of the environments where the local path planning technique guarantees collision-free paths and maneuvers the MAV to a specific goal region are described. Numerical results show the proposed technique is successful in solving path planning and multiple obstacle avoidance problems for fixed wing MAVs.