[發(fā)明專利]基于完備主干子系統(tǒng)的模型相似度度量方法

有效

• 申請?zhí)枺?/td>: 201410019455.8
• 申請日: 2014-01-16
• 公開（公告）號: CN103793597B
• 公開（公告）日: 2017-02-22
• 發(fā)明（設計）人: 蔣昌俊;陳閎中;閆春鋼;丁志軍;于汪洋
• 申請（專利權）人: 同濟大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 上海天協(xié)和誠知識產(chǎn)權代理事務所31216
• 代理人: 葉鳳

技術領域

本發(fā)明涉及一種業(yè)務模型相似度度量方法。

背景技術

如今，業(yè)務流程模型普遍用于業(yè)界分析業(yè)務流程或創(chuàng)建新模型。大規(guī)模的企業(yè)通常會有流程模型庫，內含數(shù)以百計或數(shù)以千計的模型。這些模型由不同人員開發(fā)，是企業(yè)寶貴的智力財富。為了方便管理和操作這些模型，如模型搜索、模型合并等，需要研究模型相似度度量方法。

目前已經(jīng)有許多模型相似度度量方法。基于跡等價、互模擬和分支互模擬的方法只能給出是與否的二元回答，例如用1表示等價，用0表示不等價。然而在實際應用中，人們往往希望知道不同模型之間有多大程度的不同，這就使得這些方法的應用受到限制。跡相似度被定義為兩個模型中相同跡的個數(shù)與跡的總數(shù)的比值。該方法與跡等價方法臨著同樣的問題，就是由于模型中存在并發(fā)、選擇或環(huán)結構，會造成跡的集合非常大甚至無窮，這給計算帶來很大困難。而且跡相似度方法仍然過于嚴格，兩個跡稍微不同都會造成整個跡不能匹配。為此，有學者提出了基于觀測行為的度量方法，通過比較事件日志中的典型行為，計算precision和recall指標，以度量模型的相似度。該方法受制于事件日志的完備性。基于變遷鄰接關系的方法可看作是對基于活動依賴圖的方法的改進，但這種方法只關注直接的因果關系，忽略了間接因果關系，對模型的變化缺乏足夠的敏感性。基于因果足跡的方法計算效率太低。Weidlich?et?al.提出了基于因果行為輪廓的度量方法，將因果輪廓定義為嚴序關系、交叉關系、互斥關系和共現(xiàn)關系的集合。該方法可以非常高效地計算自由選擇網(wǎng)的模型相似度，但與前述方法一樣，度量精度依然不足。

發(fā)明內容

為了提高模型相似度的度量精度，本發(fā)明提供一種基于完備主干子系統(tǒng)的模型相似度度量方法，該方法從三個方面對因果行為輪廓進行了改造。一是將變遷對的重要度納入度量范疇；二是更細粒度刻畫因果行為輪廓；三是深化變遷對的一致度。

本發(fā)明給出的技術方案為：

一種基于完備主干子系統(tǒng)的模型相似度度量方法，其特征在于，依次包括對模型分解得到完備主干子系統(tǒng)、為個完備主干子系統(tǒng)建立行為輪廓、進行完備主干子系統(tǒng)相似度比較、計算模型相似度，具體步驟為：

1）對于變遷對的重要度，本發(fā)明采用了基于完備主干子系統(tǒng)的度量方法。首先在工作流網(wǎng)上增加一個短循環(huán)變遷，通過求變遷不變量的外延子網(wǎng)，將模型分解成若干完備主干子系統(tǒng)。一個完備主干子系統(tǒng)由一個簡單主干子系統(tǒng)和若干循環(huán)結構構成，它描述了一類實例的執(zhí)行路徑。這些路徑至少執(zhí)行了簡單主干子系統(tǒng)中所有活動，還可能執(zhí)行任意次循環(huán)結構中的活動。本發(fā)明并不直接對變遷對的重要度進行計算，而是通過對各完備主干子系統(tǒng)相似度計算中得以體現(xiàn)。一個變遷在各完備主干子系統(tǒng)中出現(xiàn)的次數(shù)越多，其參與計算的次數(shù)就越多，對于模型相似度的影響也就越大，從而表明其越重要。

2）為了更細粒度刻畫行為輪廓，本發(fā)明將行為輪廓定義在完備主干子系統(tǒng)上，每個完備主干子系統(tǒng)擁有一個行為輪廓，這些行為輪廓的集合構成模型的行為輪廓。為減少信息損失，行為輪廓中不再將并發(fā)關系并入交叉關系中，同時適當增加冗余變遷對，用于刻畫簡單主干子系統(tǒng)與其循環(huán)結構的公共部分。這樣并發(fā)關系與交叉關系的交集以及嚴序關系與交叉關系的交集都可能不再為空。這些冗余的變遷可作為計算變遷對一致度的約束。冗余變遷對由簡單主干子系統(tǒng)生成。

3）因果行為輪廓的相似度是建立在變遷對一致度基礎上的。本發(fā)明將變遷一致度定義為與該變遷對匹配成功的變遷對的個數(shù)和該變遷對應匹配的變遷對個數(shù)的比值。這樣變遷對一致度被映射到[0,1]區(qū)間上的某個值，而不再是0或1。這比原有方法在計算上又前進了一步。

4）每個完備主干子系統(tǒng)依次與另一模型的完備主干子系統(tǒng)進行相似度計算，定義為所有變遷對一致度的和與變遷對總數(shù)的比值。最后模型相似度定義為各完備主干子系統(tǒng)最大相似度的平均值。

本發(fā)明方法主要從行為的角度度量模型相似度，不考慮標簽相似度和結構相似度。本發(fā)明將變遷對的重要度、變遷對的一致度都納入相似度度量范疇，更精確定義了行為輪廓的概念。本發(fā)明具有的有益效果是：可以從行為角度提高模型相似度度量精確，為模型檢索、模型合并、模型復用等操作提供支持。本發(fā)明方法還可用于軟件行為可預期性評估，有利于提高軟件可信性。

本發(fā)明方法采用自由選擇的工作流網(wǎng)來描述模型，一是因為工作流網(wǎng)已成為當今描述工作流程最為廣泛的形式化模型；二是因為大多數(shù)工作流管理系統(tǒng)只允許自由選擇網(wǎng)工作流；三是因為自由選擇網(wǎng)已得到廣泛研究且易于理解，其soundness屬性驗證和行為輪廓獲取都可在多項式時間內完成。

附圖說明