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

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

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

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

基于密度的最小生成树聚类算法研究

基于密度的方法是一种相当有效的聚类方法,能够发现任意形状的聚类,对噪声数据不敏感,但是聚类结果严重依赖于用户参数的合理选择。针对其存在的问题,将最小生成树理论与基于密度的方法相结合,提出了一种基于密度的最小生成树聚类算法。通过构造、分割最小生成树得到确定样本空间划分的最小生成子树;根据子树特性,产生局部密度参数;并对生成子树进行局部密度聚类。理论分析和应用结果表明。该算法不仅体现了基于密度聚类方法的优点,聚类结果不依赖于用户参数的选择,使数据聚类更合理,特别是对大型数据库非常有效;也体现了数据分区的思想,使其可以并行执行,进一步提高了信息处理的时空效率和性能。     

一种基于聚类分析的R*树结点重叠判定算法

聚类分析可以对大量空间对象进行聚类划分,优化R*树的结点.根据R*树的强制重插原则,在聚类分析基础上提出一种扩展MBR的对角线段对相交算法以判定类结点的重叠.从根本上改变以往在解决R*树结点重叠时仅将MBR形状改变或单纯紧致正交MBR所存在的问题,以此为判定条件可以控制聚类算法迭代次数,减少噪声点对聚类的影响.其中判定算法时间复杂性为O(nlogn)级.实验结果表明在范围查询中引入基于聚类分析的对角线段对相交判定算法的查询效率优于基于R*树的Gain/Loss度量的贪婪算法和基于SR树的算法的查询效率.     

基于LKH树批量密钥更新方案的一种优化

基于LKH树的批量密钥更新可以有效解决实时密钥更新所产生的低效和失序等问题。文献[1]中设计一种基于LKH树的优化批量密钥更新方案,提出建立动态变动子树、增大更新路径重叠的概率来降低加密次数。对文献[1]中的优化方法进行改进,将LKH树划分为三个子树：高频变动子树、过渡子树和相对稳定子树。通过分析并比较,该方法可以进一步增大更新路径重叠概率,降低加密次数。     

动态数据库中的频繁子树挖掘算法

针对动态数据库随时间发生改变的特性,提出了一种新的在动态数据库中挖掘频繁子树的算法,引入树的转变概率、子树期望支持度和子树动态支持度等概念,提出了动态数据库中的支持度计算方法和子树搜索空间,从而解决了数据动态变化的频繁子树挖掘问题。随着子树搜索的进行,算法定义裁剪公式和混合数据结构,能有效地减少子树搜索空间和提高频繁子树的同构速度。实验结果表明,新算法有效可行,且具有较好的运行效率。     

最小频繁闭树的增量式更新算法

针对树挖掘算法产生大量频繁子树和树数据库随时间变化的问题,提出最小频繁闭树增量式更新算法以及增量式更新策略,能充分利用已有挖掘知识,无须重新运行树挖掘算法,并且只需进行一次数据库扫描操作。给出一种候选子树剪枝方法,能减少树同构判别次数,有效提高算法的运行效率。通过大量实验结果表明,该算法有效可行且效率较高。     

基于DBSCAN的批量更新聚类算法

为更新批量数据,提出一种基于DBSCAN的新聚类方法。该算法通过扫描原对象确定它们同增量对象间的关系,得到一个相关对象集,同时根据该相关对象和增量对象之间的关系获得新的聚类结果。实验结果表明,该算法与DBSCAN是等价的,能更有效地解决批量数据更新时的增量聚类问题。     

基于连通距离和连通强度的BIRCH改进算法

为解决利用层次方法的平衡迭代规约和聚类（BIRCH）算法聚类结果依赖于数据对象的添加顺序，且对非球状的簇聚类效果不好以及受簇直径阈值的限制每个簇只能包含数量相近的数据对象的问题，提出一种改进的BIRCH算法。该算法用描述数据对象个体间连通性的连通距离和连通强度阈值替代簇直径阈值，还将簇合并的步骤加入到聚类特征树的生成过程中。在自定义及iris、wine、pendigits数据集上的实验结果表明，该算法比多阈值BIRCH、密度改进BIRCH等现有改进算法的聚类准确率更高，尤其在大数据集上比密度改进BIRCH准确率提高6个百分点，耗时降低61%。说明该算法能够适用于在线实时增量数据，可以识别非球形簇和体积不均匀簇，具有去噪功能，且时间和空间复杂度明显降低。     

基于QCR-树的空间索引方法

QR-树处理海量空间数据时,其深度和R-树内目录矩形的重叠面积会变大,导致查询效率降低。针对该问题采用K-means算法对索引对象进行聚类分析,构造新的聚类中心使其能处理具有多种形体的索引对象,并在QR-树中引入超结点存储聚类结果。提出一种QCR-树空间索引结构来提高查询效率,给出QCR-树的插入、删除和查询算法。实验结果表明QCR-树的查询性能优于QR-树,适用于海量数据。     

低代价最短路径树的快速算法

低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.     

依存关系树在文本多语义约束检测中的运用

提出一种运用依存关系树比对来检测文本中多语义约束的方法.对每一类语义约束,搜集信号词以及相应的例句组成案例库,并定义部分依存关系树(PDT)核函数来计算两个对象之间的相似度.Apriori算法的运用,降低了计算该核函数的复杂度.在问答系统的问题分析中的应用结果表明,该方法比带有语义特征的字符串匹配方法精确度提高了18.05%,召回率提高了16.98%.另外,在三个TREC问题集上的实验结果表明,该方法在较大规模文本问题集上也可取得较稳定的结果.     

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

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

Efficient Phrase-Based Document Similarity for Clustering

In this paper, we propose a phrase-based document similarity to compute the pair-wise similarities of documents based on the Suffix Tree Document (STD) model. By mapping each node in the suffix tree of STD model into a unique feature term in the Vector Space Document (VSD) model, the phrase-based document similarity naturally inherits the term tf-idf weighting scheme in computing the document similarity with phrases. We apply the phrase-based document similarity to the group-average Hierarchical Agglomerative Clustering (HAC) algorithm and develop a new document clustering approach. Our evaluation experiments indicate that, the new clustering approach is very effective on clustering the documents of two standard document benchmark corpora OHSUMED and RCV1. The quality of the clustering results significantly surpass the results of traditional single-word textit{tf-idf} similarity measure in the same HAC algorithm, especially in large document data sets. Furthermore, by studying the property of STD model, we conclude that the feature vector of phrase terms in the STD model can be considered as an expanded feature vector of the traditional single-word terms in the VSD model. This conclusion sufficiently explains why the phrase-based document similarity works much better than the single-word tf-idf similarity measure.     

生成树协议(STP)在计算机网络中的应用

生成树算法的网桥协议STP(Spanning Tree Protocol)它通过自动形成生成树使得在网络中一个透明的网桥以动态方式在复杂的网络拓扑结构中沿环状工作。网络中的环路由网桥之间通过交换配置桥协议数据单元消息来进行监测,通过关闭选择的网桥接口的方式破除环路。局域网通常由多种网络设备相互连接形成,我们只有消除网络中的环路才能有效降低广播风暴的发生,也就是说网络中的链路应组成树形的无环路结构,使用STP(生成树协议)就可以解决这样的问题。     

Tree edit distance: Robust and memory-efficient

Hierarchical data are often modelled as trees. An interesting query identifies pairs of similar trees. The standard approach to tree similarity is the tree edit distance, which has successfully been applied in a wide range of applications. In terms of runtime, the state-of-the-art algorithm for the tree edit distance is RTED, which is guaranteed to be fast independent of the tree shape. Unfortunately, this algorithm requires up to twice the memory of its competitors. The memory is quadratic in the tree size and is a bottleneck for the tree edit distance computation.In this paper we present a new, memory efficient algorithm for the tree edit distance, AP-TED (All Path Tree Edit Distance). Our algorithm runs at least as fast as RTED without trading in memory efficiency. This is achieved by releasing memory early during the first step of the algorithm, which computes a decomposition strategy for the actual distance computation. We show the correctness of our approach and prove an upper bound for the memory usage. The strategy computed by AP-TED is optimal in the class of all-path strategies, which subsumes the class of LRH strategies used in RTED. We further present the AP-TED⁺ algorithm, which requires less computational effort for very small subtrees and improves the runtime of the distance computation. Our experimental evaluation confirms the low memory requirements and the runtime efficiency of our approach.     

基于有序双循环链表的低代价最短路径树快速算法

低代价最短路径树是一种广泛使用的多播树。在FLSPT算法的基础上,通过选择有序双循环链表作为待发展节点序列Q的运算与存储中心,提出了基于有序双循环链表的低代价最短路径树快速算法DKFLSPT。该算法构造的最短路径树与FLSPT算法构造的最短路径树具有相同的性能,利用有序双循环链表的局部性原理来达到改进节点路径最小值的搜索过程。随机网络模型的仿真结果表明,DKFLSPT 算法效率平均可以提高19%。     

Algorithms for search trees on message passing architectures

In this paper we describe a new algorithm for maintaining a balanced search tree on a message-passing MIMD architecture; the algorithm is particularly well suited for implementation on a small number of processors. We introduce a (2^B-2, 2^B) search tree that uses a bidirectional ring of O(log n) processors to store n entries. Update operations use a bottom-up node-splitting scheme, which performs significantly better than top-down search tree algorithms. The bottom-up algorithm requires many fewer messages and results in less blocking due to synchronization than top-down algorithms. Additionally, for a given cost ratio of computation to communication the value of B may be varied to maximize performance. Implementations on a parallel-architecture simulator are described     

Z树：一个高维度的数据索引结构

Z树能够高效地处理对高维度数据集的矩形区域查询和最邻近搜索。它按照节点的形状变化量优化数据的插入位置，使节点形状趋于合理。文章给出了一个新的无重叠分裂算法，减少超级节点的产生。引入了动态剪枝和重新插入策略，压缩超级节点的数量和体积。提出了矩形节点的球形化方法和最优子树搜索算法。实验表明Z树的矩形区域查询和最邻近搜索的效率远远高于X树和SR树。     

基于频繁模式的数据流聚类算法

数据流具有数据量无限且流速快的特点.针对上述问题,本文讨论了基于频繁模式的数据流聚类算法.本算法应用改造后的FP-Tree,更新树时增加一个数组减少了遍历树的时间,使算法的效率得到了很大的提高.