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

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

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

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

基于WF-net的流程距离测度模型研究

流程比对一直是业务流程管理的一个研究热点。它是指通过比较得出两个流程的相似度或相异度。流程距离是对两个流程相异程度的描述。在WF-net的基础上,明确提出了流程距离的概念,并在业务控制流及其资源的角度上建立了流程距离测度模型,用于测量两个流程之间的距离。通过分析得出：在多个流程中,能够找到与指定流程最近或最远的流程。证明提出的流程距离测度方法是可行的。     

基于三维行为关系图的模型一致性检测方法

在业务流程模型的相似性分析过程中,有时会出现环结构。已有的方法一般不考虑环结构,忽略了环结构对模型一致性分析的影响。以Petri网的多重变迁集为基础,提出一种新的一致性度测量方法。首先通过分析5种行为序列关系来刻画Petri网的变迁之间的相互关系,给出了三维行为关系图的概念;然后对Petri网的三维行为关系图间的关系进行研究,提出了基于Petri网的三维行为关系图的一致性检测方法。理论分析和实例测试均表明了该方法的有效性。     

BPMN 2.0编排的形式语义和分析

BPMN 2.0编排已成为描述业务流程间交互事实上的标准.BPMN 2.0编排面向流的特征,使之会产生控制流方面的语义错误.因此,检查编排语义正确性是BPMN 2.0编排建模工具所期望具有的功能.但是,BPMN 2.0标准规约中编排缺少形式语义及相应的分析技术,这阻碍了对BPMN 2.0编排的语义分析.本文提出了一种映射,用于将BPMN 2.0编排转换为工作流网,使用Petri网来形式定义BPMN 2.0编排的语义.借助Petri网的分析技术,这种定义的语义可用来分析BPMN 2.0编排的结构和控制流方面的错误.该映射和语义分析已被实现为一种工具.实验结果表明,这种形式化可以识别BPM AI过程模型库中编排的语义错误.     

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

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

A methodology and tool environment for process analysis and reengineering

Most private and public organizations have recently turned their attention to the process by which they operate, to improve service and product quality and customer satisfaction. To support business process reengineering, methods and tools for process modeling and analysis are required. The paper presents the ARTEMIS methodology and associated tool environment for business process analysis for reengineering. In the ARTEMIS methodological framework, business processes are modeled as workflows and are analyzed according to an organizational structure perspective and an operational structure perspective. With these two perspectives, the analyst can plan reengineering interventions based on the degree of autonomy/dependency of organization units in terms of coupling, and the inter-process semantic correspondences, in terms of data and operation similarity, respectively. The ARTEMIS methodology and associated tool environment have been conceived and applied in the framework of the PROGRESS research project. In the paper, we report on a reengineering case study of this project involving the Italian Ministry of Justice.     

Classifying molecular sequences using a linkage graph with their pairwise similarities

This paper presents a method for classifying a large and mixed set of uncharacterized sequences provided by genome projects. As the measure of sequence similarity, we use similarity score computed by a method based on the dynamic programming (DP), such as the Smith-Waterman local alignment algorithm. Although comparison by DP based method is very sensitive, when given sequences include a family of sequences that are much diverged in evolutionary process, similarity among some of them may be hidden behind spurious similarity of some unrelated sequences. Also the distance derived from the similarity score may not be metric (i.e., triangle inequality may not hold) when some sequences have multi-domain structure. To cope with these problems, we introduce a new graph structure called p-quasi complete graph for describing a family of sequences with a confidence measure. We prove that a restricted version of the p-quasi complete graph problem (given a positive integer k, whether a graph contains a 0.5-quasi complete subgraph of which size k or not) is NP-complete. Thus we present an approximation algorithm for classifying a set of sequences using p-quasi complete subgraphs. The effectiveness of our method is demonstrated by the result of classifying over 4000 protein sequences on the Escherichia coli genome that was completely determined recently.     

BPEL 流程建模中的交叠模式分析与转换

由图形化流程建模语言生成可执行的业务流程语言(business process execution language,简称BPEL)时,对于源模型中顺序与并发结构交织的情况(称为交叠模式),传统的复制相关活动方法缺少系统分析及形式化描述.针对这一现状,提出基于工作流网的UML活动图生成BPEL方法,以自由选择工作流网作为活动图的理论基础,利用活的、有界的自由选择网系统的合成规则,定义合理的自由选择工作流网中的两种交叠模式,针对其中一种给出复制相关活动的形式化转换方法,并借助Petri网的并发正则表达式证明转换等价性,说明另一种交叠模式中复制相关活动方法的适用范围.针对BPEL流程建模及图形化流程语言生成块状语言过程中的交叠模式转换问题,给出形式化的描述与解决方法.     

Distance learning for similarity estimation

In this paper, we present a general guideline to find a better distance measure for similarity estimation based on statistical analysis of distribution models and distance functions. A new set of distance measures are derived from the harmonic distance, the geometric distance, and their generalized variants according to the Maximum Likelihood theory. These measures can provide a more accurate feature model than the classical Euclidean and Manhattan distances. We also find that the feature elements are often from heterogeneous sources that may have different influence on similarity estimation. Therefore, the assumption of single isotropic distribution model is often inappropriate. To alleviate this problem, we use a boosted distance measure framework that finds multiple distance measures which fit the distribution of selected feature elements best for accurate similarity estimation. The new distance measures for similarity estimation are tested on two applications: stereo matching and motion tracking in video sequences. The performance of boosted distance measure is further evaluated on several benchmark data sets from the UCI repository and two image retrieval applications. In all the experiments, robust results are obtained based on the proposed methods.     

Managing information measures for hesitant fuzzy linguistic term sets and their applications in designing clustering algorithms

Recently, the Hesitant Fuzzy Linguistic Term Sets (HFLTSs) have been widely used to address cognitive complex linguistic information because of its advantage in representing vagueness and hesitation in qualitative decision-making process. Information measures, including distance measure, similarity measure, entropy measure, inclusion measure and correlation measure, are used to characterize the relationships between linguistic elements. Many decision-making theories are based on information measures. Up to now, distance, similarity, entropy and correlation measures have been proposed by scholars but there is no paper focuses on inclusion measure. This paper dedicates to filling this gap and the inclusion measure between HFLTSs are proposed. We discuss the relationships among distance, similarity, inclusion and entropy measures of HFLTSs. Given that clustering algorithm is an important application of information measures but there are few papers related to clustering algorithm based on information measures in the environment of HFLTS, in this paper, we propose two clustering algorithms based on correlation measure and distance measure, respectively. After that, a case study concerning water resource bearing capacity is illustrated to verify the applicability of the proposed clustering algorithms.     

Clustering of biological time series by cepstral coefficients based distances

Clustering of stationary time series has become an important tool in many scientific applications, like medicine, finance, etc. Time series clustering methods are based on the calculation of suitable similarity measures which identify the distance between two or more time series. These measures are either computed in the time domain or in the spectral domain. Since the computation of time domain measures is rather cumbersome we resort to spectral domain methods. A new measure of distance is proposed and it is based on the so-called cepstral coefficients which carry information about the log spectrum of a stationary time series. These coefficients are estimated by means of a semiparametric model which assumes that the log-likelihood ratio of two or more unknown spectral densities has a linear parametric form. After estimation, the estimated cepstral distance measure is given as an input to a clustering method to produce the disjoint groups of data. Simulated examples show that the method yields good results, even when the processes are not necessarily linear. These cepstral-based clustering algorithms are applied to biological time series. In particular, the proposed methodology effectively identifies distinct and biologically relevant classes of amino acid sequences with the same physicochemical properties, such as hydrophobicity.     

Similarity of business process models: Metrics and evaluation

It is common for large organizations to maintain repositories of business process models in order to document and to continuously improve their operations. Given such a repository, this paper deals with the problem of retrieving those models in the repository that most closely resemble a given process model or fragment thereof. Up to now, there is a notable research gap on comparing different approaches to this problem and on evaluating them in the same setting. Therefore, this paper presents three similarity metrics that can be used to answer queries on process repositories: (i) node matching similarity that compares the labels and attributes attached to process model elements; (ii) structural similarity that compares element labels as well as the topology of process models; and (iii) behavioral similarity that compares element labels as well as causal relations captured in the process model. These metrics are experimentally evaluated in terms of precision and recall. The results show that all three metrics yield comparable results, with structural similarity slightly outperforming the other two metrics. Also, all three metrics outperform text-based search engines when it comes to searching through a repository for similar business process models.     

基于期望首达时间的形状距离学习算法

由于逐对形状匹配不能很好地反映形状间相似度,因此需要引入后期处理步骤提升检索精度. 为了得到上下文敏感的形状相似度,本文提出了一种基于期望首达时间（Mean first-passage time,MFPT）的形状距离学习方法. 在利用标准形状匹配方法得到距离矩阵的基础上,建立离散时间马尔可夫链对形状流形结构进行分析.将形状样本视作状态,利用不同状态之间完成一次状态转移的平均时间步长,即期望首达时间,表示形状间的距离.期望首达时间能够结合测地距离发掘空间流形结构,并可以通过线性方程进行有效求解.分别对不同数据进行实验分析,本文所提出的方法在相同条件下能够达到更高的形状检索精度.     

基于时间序列的感知QoS的云服务组合

研究基于时间序列的感知QoS的云服务组合,将服务的QoS偏好随时间不断变化的过程纳入云服务组合的研究范围,将云服务组合建模成时间序列的相似度对比问题。分别用欧几里得距离和扩展Frobenius范数距离度量二维时间序列的相似度,继而用基于主成分分析的扩展Frobenius范数距离和欧几里得距离、Brute Force等方法度量多维时间序列的相似度,通过实验对比验证扩展Frobenius范数距离度量相似度在时间和准确性上的优越性。关     

SRIHASS - a similarity measure for discovery of hidden time profiled temporal associations

Mining and visualization of time profiled temporal associations is an important research problem that is not addressed in a wider perspective and is understudied. Visual analysis of time profiled temporal associations helps to better understand hidden seasonal, emerging, and diminishing temporal trends. The pioneering work by Yoo and Shashi Sekhar termed as SPAMINE applied the Euclidean distance measure. Following their research, subsequent studies were only restricted to the use of Euclidean distance. However, with an increase in the number of time slots, the dimensionality of a prevalence time sequence of temporal association, also increases, and this high dimensionality makes the Euclidean distance not suitable for the higher dimensions. Some of our previous studies, proposed Gaussian based dissimilarity measures and prevalence estimation approaches to discover time profiled temporal associations. To the best of our knowledge, there is no research that has addressed a similarity measure which is based on the standard score and normal probability to find the similarity between temporal patterns in z-space and retains monotonicity. Our research is pioneering work in this direction. This research has three contributions. First, we introduce a novel similarity (or dissimilarity) measure, SRIHASS to find the similarity between temporal associations. The basic idea behind the design of dissimilarity measure is to transform support values of temporal associations onto z-space and then obtain probability sequences of temporal associations using a normal distribution chart. The dissimilarity measure uses these probability sequences to estimate the similarity between patterns in z-space. The second contribution is the prevalence bound estimation approach. Finally, we give the algorithm for time profiled associating mining called Z-SPAMINE that is primarily inspired from SPAMINE. Experiment results prove that our approach, Z-SPAMINE is computationally more efficient and scalable compared to existing approaches such as Naïve, Sequential and SPAMINE that applies the Euclidean distance.     

基于活动发生关系的流程相似性度量方法

针对现有的流程模型行为相似性度量方法大都基于变迁的发生序列, 存在时间复杂度较高的问题, 提出一种基于活动发生关系的流程相似性度量方法. 首先, 形式化左右集概念, 并引入违背度和左右集权重$\alpha,\beta$, 通过活动间的关系变化来确定$\alpha$和$\beta$的取值, 进而得到活动的相似性; 然后, 将流程中活动的相似性进行归一化, 提出基于活动发生关系的流程相似性算法(AOR), 进行业务流程的相似性度量. 最后, 使用实际事件数据案例对本文方法进行了评估, 实验结果表明: 该方法能够正确计算两个不同流程之间的相似性, 且具有较好的时空复杂度.     

基于海明距离的直觉模糊粗糙集相似度量方法

针对直觉模糊粗糙集的相似度量问题,提出了一种基于海明距离的直觉模糊粗糙集相似度量方法。首先给出了两个直觉模糊粗糙值问的相似度量方法,并揭示了它的若干重要性质。然后,在此基础上,又提出了一种基于海明距离的直觉模糊粗糙集相似度量方法,并证明它也具有同样的性质。最后用数值算例验证了这种方法的有效性。