一种工作流的控制流距离度量方法

为准确计算工作流中的控制流距离,提出一种工作流的控制流距离度量方法.介绍从工作流中分离控制节点生成控制流图的过程.在控制节点间距离基础上,建立通过控制流图进行工作流控制流距离度量的模型,并从理论上证明距离度量模型满足自反、对称及三角不等式性质.案例分析结果表明,该方法能更真实、准确地反映工作流间的距离.     

有向标记根树之间的语义编辑距离

有向标记根树之间的编辑距离(TED)被广泛应用在文档的结构化相似度计算上。文中提出有向标记根树之间的语义编辑距离(TSED)的概念,并给出计算公式。组合TED和TSED形成距离测度,并应用在XML文档的结构聚类上。实验表明该距离模型在结构化聚类的准确率和召回率上明显优于单纯利用TED算法的聚类结果。该算法在时间复杂性上也等同于利用动态规划计算TED的最好算法。     

基于新的距离度量的K-Modes聚类算法

传统的K-Modes聚类算法采用简单的0-1匹配差异方法来计算同一分类属性下两个属性值之间的距离, 没有充分考虑其相似性. 对此, 基于粗糙集理论, 提出了一种新的距离度量. 该距离度量在度量同一分类属性下两个属性值之间的差异时, 克服了简单0-1匹配差异法的不足, 既考虑了它们本身的异同, 又考虑了其他相关分类属性对它们的区分性. 并将提出的距离度量应用于传统K-Modes聚类算法中. 通过与基于其他距离度量的K-Modes聚类算法进行实验比较, 结果表明新的距离度量是更加有效的.     

基于加权重叠距离的K-modes聚类算法

传统的K-modes聚类算法在计算两个对象之间的距离时,并没有考虑不同属性之间的差异性。针对这一问题,本文基于粗糙集理论引入一种新的距离度量标准——加权重叠距离,并提出一种基于加权重叠距离的K-modes聚类算法WODKM。     

基于树编辑距离的层次聚类算法

为了识别犯罪嫌疑人伪造和篡改的虚假身份,利用树编辑距离计算个体属性相似性,证明了树编辑距离的相关数学性质,对属性应用层次编码方法,提出了一种新的基于树编辑距离的层次聚类算法HCTED(Hi-erarchical Clustering Algorithm Based on Tree Edit Distance)。新算法通过树编辑操作使用最少的代价计算属性相似性,克服了传统聚类算法标称型计算的缺陷,提高了聚类精度,通过设定阈值对给定样本聚类。实验证明了新方法在身份识别上的准确性和有效性,讨论了不同参数对实验结果的影响,对比传统聚类算法,HCTED算法性能明显提高。新算法已经应用到警用流动人口分析中,取得了良好效果。     

基于时间约束的Hausdorff距离的时空轨迹相似度量

从海量的轨迹数据中发现用户的相似轨迹是实现基于位置的个性化服务推荐的关键技术之一.位置和时间是轨迹数据的两个重要属性,而已有的基于Hausdorff距离的轨迹相似度量只着重关注了位置属性.针对在计算轨迹间相似性时忽略了轨迹的时间属性这一问题,提出一种基于时间约束的Hausdorff距离的时空轨迹相似度量.利用滑动窗口挖掘两条较长轨迹中所有相似的子轨迹,进而判断较长轨迹间的相似性.实验结果表明,该时空轨迹相似度量具有更好的效果.     

基于知识距离的粗糙粒结构的评价模型

在粒计算理论中,通过不同的粒计算机制可以生成不同的粒结构。在粗糙集中,对于同一个信息表而言,通过不同的属性添加顺序可以得到由不同的序贯层次结构,即粗糙粒结构。在粗糙粒结构中,不同的属性获取顺序导致了对不确定性问题求解的不同程度。因此,如何有效评价粗糙粒结构是一个值得研究的问题。本文将从知识距离的角度研究这个问题。首先,在前期工作所提出的知识距离框架上提出了一种粗糙近似空间距离,用于度量粗糙近似空间之间差异性。基于提出的知识距离,研究了粗糙粒结构的结构特征。在粗糙粒结构中,在对不确定性问题进行求解时,本文希望在约束条件下可以利用尽可能少的知识空间使不确定性降低达到最大化。基于这个思想并利用以上得出的结论,在属性代价约束条件下,引入了一个评价参数λ,并在此基础建立了一种粗糙粒结构的评价模型,该方法实现了在属性代价约束条件下选择粗糙粒结构的功能。最后,通过实例验证了本文提出的模型的有效性。     

基于编辑距离的Web数据挖掘

Div+CSS流行于Web页面的布局,在这种布局下,网页中很多数据记录以重复结构的形式聚集在一个层级。为了更好地从网页中挖掘数据,提出了一种新的Web数据挖掘算法,把树编辑距离转化为字符串编辑距离的计算,改进字符串编辑距离算法,利用字符串编辑距离评价树的相似度,进而找到网页中的重复模式,提取数据。通过针对不同重复模式特征的网页的实验说明,基于编辑距离的Web数据挖掘算法不仅能提取具有根节点及上面几层相同的网页的数据,对具有底层节点相同的网页也是有效的。     

基于有效距离的低秩表示

低秩表示（Low-Rank Representation,LRR）在探索数据中的低维子空间结构方面具有良好的效果,近年来引起了人们的广泛关注。然而,传统的LRR方法通常使用欧氏距离来度量样本的相似性,仅考虑相邻样本两两之间的距离信息,对于具有流形结构的数据往往不能反映其固有的几何结构。最近的研究表明,概率激励距离测量（即有效距离）可以有效地对数据的全局信息进行建模,来度量样本间的相似性。在此基础上,提出了一种基于有效距离的低秩表示模型。该方法用稀疏表示方法计算样本之间的有效距离来构造拉普拉斯矩阵,并将其进行低秩表示拉普拉斯正则化约束,该模型不仅能表示全局低维结构,而且能捕获流形结构数据中的几何结构信息。为了评估方法的有效性,在三个公开数据集上进行了分类实验。实验结果表明,该方法比基于传统欧氏距离的方法,具有更高的分类性能和更强的鲁棒性。     

一种改进的基于WSDL描述的操作相似性度量方法

在目前通用的Web服务描述标准WSDL基础上,文中提出一种改进的操作相似性度量方法MOSM.MOSM在数据预处理后将Web服务内含的操作(operation)建模为无序标签树,并通过计算满足约束的编辑距离对其进行相似性度量.其具体做法是抽取操作的XML模式的树形结构,对结构进行变形,只保留标签结点;然后计算生成的无序标签树之间满足约束的编辑距离,将操作相似性度量的问题转化为无序标签树匹配的问题.该文的创新主要在:建模时采用满足约束的无序树模型,在编辑距离算法中引入支持不对称性的代价模型,另外为结构和文字标签匹配引入了相似系数.文中最后给出实验了对比结果,MOSM算法能有效提高top-k查准率,对找寻相似的备选操作具有重要意义.     

高维数据的增量式聚类算法的距离度量选择研究

合适的距离度量函数对于聚类结果有重要的影响。针对大规模高维数据集,使用增量式聚类算法进行距离度量的选择分析。SpFCM算法是将大规模数据集分成小样本进行增量分批聚类,可在有限的计算机内存中获得较好的聚类结果。在传统的SpFCM算法的基础上,使用不同的距离度量函数来衡量样本之间的相似性,以得出不同的距离度量对SpFCM算法的影响。在不同的大规模高维数据集中,使用欧氏距离、余弦距离、相关系数距离和扩展的杰卡德距离来计算距离。实验结果表明,后3个距离度量相对于欧氏距离可以很大程度地提高聚类效果,其中相关系数距离可以得到较好的结果,余弦距离和扩展的杰卡德距离效果比较一般。     

基于模型结构和事件日志的流程相似度计算

流程相似度的计算在企业业务流程管理中具有重要作用。目前相似度的计算主要存在两个问题：一是大多数相似度计算方法只考虑模型结构或事件日志,导致算法不够精确;二是综合考虑了模型结构和事件日志的算法复杂度高且效率低。因此,提出了一种改进的流程模型结构和事件日志相结合的方法。首先将流程模型结构中的紧邻活动转化为邻接矩阵,然后根据事件日志中的行为信息对邻接矩阵进行加权得到加权邻接矩阵,最后采用符合距离度量特性的矩阵间距离的算法来度量流程间相似度。通过实验与MDS、GED以及WBPG等算法进行对比,所提方法的准确率更高,为99.51%,计算效率也更高。     

A bounded distance metric for comparing tree structure

Comparing tree-structured data for structural similarity is a recurring theme and one on which much effort has been spent. Most approaches so far are grounded, implicitly or explicitly, in algorithmic information theory, being approximations to an information distance derived from Kolmogorov complexity. In this paper we propose a novel complexity metric, also grounded in information theory, but calculated via Shannon's entropy equations. This is used to formulate a directly and efficiently computable metric for the structural difference between unordered trees. The paper explains the derivation of the metric in terms of information theory, and proves the essential property that it is a distance metric. The property of boundedness means that the metric can be used in contexts such as clustering, where second-order comparisons are required. The distance metric property means that the metric can be used in the context of similarity search and metric spaces in general, allowing trees to be indexed and stored within this domain. We are not aware of any other tree similarity metric with these properties.     

A new approach to fuzzy distance measure and similarity measure between two generalized fuzzy numbers

In this paper a fuzzy distance measure between two generalized fuzzy numbers is developed. The metric properties of this distance measure are also studied. The new distance measure is compared with the other fuzzy distance measures proposed by Voxman [W. Voxman, Some remarks on distances between fuzzy numbers, Fuzzy Sets and Systems 100 (1998) 353–365] and Chakraborty and Chakraborty [C. Chakraborty, D. Chakraborty, A theoretical development on fuzzy distance measure for fuzzy numbers, Mathematical and Computer Modelling 43 (2006) 254–261] and turned out to be more reasonable. A new similarity measure is also developed with the help of the fuzzy distance measure. Examples are given to compare this similarity measure with the other similarity measure previously proposed. A decision making scheme is proposed using this similarity measure and this scheme is found to be more acceptable than the existing methods due to the fact that it considers the degrees of confidence of the experts’ opinion.     

面向分类属性数据的一种改进相异性度量及其在客户细分中的应用*

具有层次结构的分类属性在客户细分应用中广泛存在。针对传统相异性度量无法准确反映决策者在与细分目标相关的决策指标上的偏好信息,提出一种改进的距离层次并给出使用该度量,基于聚类分析的客户细分基本流程。该度量利用距离层次计算各分类属性值概念间的相异性,同时引入指标距离的概念描述对于特定指标,决策者在不同分类属性值上的偏好,结合模糊相似优先比决策方法和树的广度优先遍历计算不同分类属性值间的指标距离,最后通过将所求得的概念距离和指标距离进行加权求和以更全面地度量不同分类属性值间的相异性。对陕西省电力公司工业客户进行细分实验的结果表明：与传统距离层次相比,采用改进相异性度量能提高聚类质量和细分结果的可解释性。     

基于变迁图编辑距离的流程相似性算法

为了提高从企业模型库中查询检索模型的效率,提出一种基于变迁图编辑距离的流程相似性算法。首先,给出了变迁图的概念及其生成方法;其次,提出边的长度概念,且删除和插入边的代价由该边的长度决定,基于此定义出图编辑操作及其代价,并用节点匹配算法计算最小图编辑距离;然后,给出两个过程模型的相似性概念和计算方法;最后,通过实验验证了算法的正确性且满足七条相似性性质,并验证了变迁图编辑距离满足四条距离性质。     

XML文档的相似测度和结构索引研究

提出了一个可用于定量度量XML文档间差异的方法(称为XED距离)。利用结点间的模拟关系，一个XML文档可以表示为一棵精简的、带权重的结构索引树，两个XML文档间的相似度可以通过计算它们的索引树间的编辑距离来测定，利用索引树可以大大提高判定两个XML文档结构相似度的效率，XED距离测度可用于XML文档的结构搜索、XML文档聚类、XML文档结构抽取、XML文档的变换检测以及XML视图的增量计算和维护等。     

最小距离分类器的改进算法--加权最小距离分类器

最小距离分类器是一种简单而有效的分类方法。为了提高最小距离分类器的分类性能,主要的改进方法是选择更有效的距离度量。通过分析多重限制分类器和决策树分类器的分类原则,提出了基于标准化欧式距离的加权最小距离分类器。该分类器通过对标称型和字符串型属性的距离的加权定义。以及增加属性值的范围约束,扩大了最小标准化欧式距离分类器的适用范围,同时提高了其分类准确率。实验结果表明,加权最小距离分类器具有较高的分类准确率。     

A workflow net similarity measure based on transition adjacency relations

Many activities in business process management, such as process retrieval, process mining, and process integration, need to determine the similarity or the distance between two processes. Although several approaches have recently been proposed to measure the similarity between business processes, neither the definitions of the similarity notion between processes nor the measure methods have gained wide recognition. In this paper, we define the similarity and the distance based on firing sequences in the context of workflow nets (WF-nets) as the unified reference concepts. However, to many WF-nets, either the number of full firing sequences or the length of a single firing sequence is infinite. Since transition adjacency relations (TARs) can be seen as the genes of the firing sequences which describe transition orders appearing in all possible firing sequences, we propose a practical similarity definition based on the TAR sets of two processes. It is formally shown that the corresponding distance measure between processes is a metric. An algorithm using model reduction techniques for the efficient computation of the measure is also presented. Experimental results involving comparison of different measures on artificial processes and evaluations on clustering real-life processes validate our approach.