蹤跡聚類下組織實體的重要度排序方法

徐濤 孟野

摘要：針對簡單套用交接網絡等社會網絡分析方式不能很好地反映蹤跡聚類生成的一系列流程的組織實體的重要度的問題，提出了一種蹤跡聚類下組織實體的重要度排序方法。首先，對于參與蹤跡聚類生成的一系列流程的組織實體構建蹤跡聚類與組織實體關系網絡；其次，定義基于蹤跡聚類與組織實體關系網絡的節點重要度評估方法；最后，對蹤跡聚類下的各個組織實體節點計算其在關系網絡中的重要度評分并排序。實驗結果表明，所提方法構建的關系網絡相比蹤跡聚類下的交接網絡能夠更準確地反映組織實體的實際重要度；與基于拓撲勢的網絡社區節點重要度排序算法相比，所提方法的節點重要度排序結果更符合實際業務流程，能更好地區分關系網絡中重要度不同的節點。

關鍵詞：流程挖掘；組織挖掘；重要度排序；社會網絡；復雜網絡

中圖分類號：TP391.4 文獻標志碼：A

Abstract： Aiming at the issue that the social network analysis method like handover network cannot express the importance of organizational entities precisely， a method to sort the quantified importance of organizational entities organized under the trace clusters was proposed. Firstly， a relation network was constructed to describe the relationship between trace clusters and organizational entities； secondly， a quantitative assessment of the nodes importance of this network was defined； finally， all these nodes were sorted respectively according to their quantified importance. The experimental results show that this relation network can express the actual importance of organizational entities more precisely than the handover network generated by trace clustering. Compared to the importance sorting algorithm of network community nodes based on topological potential， the proposed method is more suitable for the actual business processes， meanwhile it can distinguish distinct organizational entities better than the importancesorting algorithm based on topological potential.

Key words：process mining； organizational mining； importance sorting； social network； complex network

0 引言

業務流程運行數據往往來自于企業信息系統生成的業務流程日志，而流程挖掘（process mining）技術可以提取流程日志中的有用信息用于流程分析，并重現業務流程的真實過程，為管理者提供流程運行的知識[1-2]。流程挖掘通過分析流程日志中的任務、 參與者和時間等數據，結合工作流管理和數據挖掘等相關技術，從控制流、組織結構等角度提取流程運行的知識，利用這些知識可以發現業務執行與企業戰略目標的偏差、流程瓶頸、組織之間的低效率協作等問題，從而對業務流程進行優化[3]。

業務流程日志包含了一系列業務流程實例（instance）。業務流程實例可以表示為業務流程開始到結束所調用的活動的序列，這種活動序列又被稱作蹤跡（trace），而組成蹤跡的活動又對應著不同的組織實體[1，4]。組織實體根據不同級別可分為執行活動的企業部門、員工等，是企業組織結構的組成部分。因此，既可以通過流程挖掘算法挖掘蹤跡所可能表示的流程模型，又可以采用社會網絡分析方法挖掘蹤跡中活動對應的組織實體的交接網絡（handover network）等關系網絡[1，5]。通常情況下，流程模型的發現與組織挖掘是各自獨立的。

組織挖掘能夠發現組織實體之間的協作關系和組織實體在流程中的重要性。文獻[5]對某醫療流程中的醫務人員進行模塊化的社區挖掘，每次迭代都計算社區聚類結果的模塊化程度，最后將模塊化最高的聚類作為團體聚類結果，從而得到團體內部協作緊密，而團體之間的協作關系松散的社區。繪制此醫療流程的社交圖譜，對同一社區的醫務人員進行統一著色，通過人員節點間的連線體現醫務人員、團體之間的協作程度，從而分析得出應適當增加對急救科的人員分配，以適應急救環節在社交圖譜中所體現的中心地位，避免因人員不足影響整個流程的效率。

文獻[6]使用聚類算法分析了知識維護業務中員工之間的知識層次結構。將交接網絡中，入度為0的節點的知識層次視為最低，出度為0的節點的知識層次視為最高，具有相同前驅和后繼節點的節點視為處于同一領域的同一知識層次。但該方法的挖掘結果與目標單位的組織結構對比往往存在較大不同，且該方法對普通員工在知識層次結構中的專業知識水平估計過高，與實際情況存在差異。文獻[7]提出基于社會網絡分析的員工自動組合方法，定義關鍵貢獻者、影響者和協調者三種特殊的社交角色，并分別通過度中心性、向量中心性、中間中心性對員工的重要性進行度量。

企業實際業務流程日志往往表現出結構化程度低的特點。傳統的流程挖掘算法在處理這類低結構化流程時易生成結構復雜且難于理解的流程模型，其原因在于這類流程挖掘算法難以為處于低抽象層次的流程日志指定合適的抽象層次，而蹤跡聚類是解決這一問題的方式之一[8]。對蹤跡聚類后，意味著各類蹤跡所代表的實例之間具有相關性，因此可采用分治的策略將原始日志的流程模型表示為一系列結構復雜度較低且易于理解的流程模型。蹤跡聚類解決了直接對原始日志進行流程挖掘時流程模型難以理解的問題，但同時，蹤跡聚類也相應對組織實體生成的社會網絡構成了一種新的社區劃分，簡單套用元日志的社會網絡分析方法時，組織實體的實際重要度不能被準確地表示。

本文提出一種基于蹤跡聚類的組織實體關系網絡的組織實體重要度排序方法，依照蹤跡聚類結果劃分該關系網絡的社區，并對組織實體在不同社區內的重要度進行度量。通過組織實體在不同社區中重要性的度量，對社區進行區分和理解，同時，通過社區內部組織實體的排序，體現社區內實體的差異性，為針對組織結構的真實情況開展流程優化提供幫助。

1 蹤跡聚類方法

蹤跡聚類結果通過對流程日志的蹤跡進行聚類得到，為了得到有意義的蹤跡聚類結果，需對蹤跡進行量化表征，并確定不同蹤跡間的相似性度量方式。以某產品售后服務流程為例，日志表1是某產品售后服務流程日志中流程實例的活動組成，表中組成流程實例的活動由大寫字母表示，A代表收到返回產品與保修請求，B代表檢查產品，C代表核對保單，D代表通知客戶，E代表修理產品，F代表測試修理后的產品，G代表收取修理費，H代表發送取消保修請求，I代表返回該產品。文獻[8]通過統計流程日志實例的活動頻次，構建蹤跡表示向量，并采用K均值、凝聚層次聚類（Agglomerative Hierarchical Clustering，AHC）、自組織映射（SelfOrganizing Map，SOM）等方法進行蹤跡聚類。表2是對表1流程日志中蹤跡進行活動頻次統計后的蹤跡表示結果，可以加入組織結構成員等統計信息進一步擴展蹤跡表示向量。文獻[9]基于上下文感知對蹤跡進行距離，該文獻引入ngram模型構建蹤跡表示向量。表3是引入2gram模型后，售后服務流程日志的蹤跡表示結果。文獻[10]將蹤跡表征為蹤跡中最大重復集合（maximal repeat set）等特征集合出現頻次的向量。

上述蹤跡聚類方法的思路均為通過構建蹤跡表示向量對蹤跡進行量化，將蹤跡聚類問題轉化為一般性的聚類問題，并用成熟的聚類算法求解。本文引入文獻[11-12]的混合概率模型估計蹤跡屬于各類簇的概率，用概率估計結果構建蹤跡表示向量； 并采用文獻[13]的球面K均值算法（spherical Kmeans）進行蹤跡聚類，將蹤跡聚類所得聚類結果應用于后續的組織實體重要度排序中。

2 復雜網絡節點重要度評估方法

對業務流程應用組織挖掘得到社會網絡后，可發現其節點多為流程日志中出現的各組織實體。因此復雜網絡節點的重要度評估方法對組織實體的重要度評估有重要參考價值。復雜網絡節點重要度評估方法主要有中心性指標、基于最短路徑和基于凝聚度等。文獻[14]定義一種基于復雜網絡凝聚度的節點重要度評估方法，將網絡凝聚度定義為節點數與平均路徑長度乘積的倒數，但這種方法不適合用于加權網絡。文獻[15]定義一種基于拓撲勢的網絡社區節點重要度排序算法，該算法考慮到單純計算拓撲勢并不能真正說明節點在網絡中的重要性，因此將社區中起不同作用的節點區分為內部節點和邊界節點，計算各節點拓撲勢后，再連接內部節點和邊界節點排序結果。文獻[16]提出了一種評估加權復雜網絡節點重要度方法，該方法以最短路徑為基礎，綜合考慮了節點的連接度和節點在網絡中的位置，并重新定義了加權網絡D=（V，E）的凝聚度（D）為：

3 蹤跡聚類下的組織實體重要度排序

對蹤跡聚類得到的子業務流程而言，負責流程關鍵環節組織實體，往往有較高的流程實例參與頻次，并與其他個體有著更多交互與合作。所以可建模基于蹤跡聚類與組織實體關系網絡，將組織實體的流程實例參與頻次量化為組織實體的重要度，并根據組織實體的實際情況，為組織實體設置合適的權重，從而綜合地進行評估。

3.1 相關定義

傳統社會網絡分析方法較少利用組織實體在蹤跡聚類得到的子業務流程中的參與度等信息，為此可建立定義如下：

4 實驗驗證與分析

本文選用國內某大型樞紐機場的流程日志數據集進行實驗。對日志數據集進行預處理后結果如下：數據集共有流程實例記錄2006條，蹤跡540條；流程日志的組織實體分為部門、角色和資源三個級別，其中部門10個、角色20個、資源500人。進行蹤跡聚類后，抽取其中的某一類簇對應的流程日志進行實驗，該類簇的實際含義為機場的機位分配業務流程。

4.1 實驗評價指標

為了驗證本文方法的合理性，選擇資源級別與角色級別的組織實體分別進行基于蹤跡聚類與組織實體關系網絡下組織實體重要度排序實驗。選用節點度（node degree）直觀觀察節點在網絡中的地位，并簡明地對網絡節點進行排序。同時，考慮到度中心性指標是衡量網絡節點重要性最為廣泛采用的方法 [17-18]；且網絡節點的重要度不僅和節點局部重要性有關，而且與其在網絡中所處位置以及節點之間的相互依賴程度密切相關[19-20]。因此，選用度中心性指標中的接近中心性（closeness centrality）與中介中心性（betweeness centrality）對節點進行進一步的評估，并通過與重要度排序結果的對比驗證方法的有效性。

4.2 組織實體重要度排序實驗

4.2.1 實驗1

將角色級別的基于蹤跡聚類與組織實體關系網絡節點排序結果與蹤跡聚類下交接網絡節點的排序結果進行對比，選取具有代表性的五個節點的排序結果如表4所示。蹤跡聚類下交接網絡節點度最大的節點為12號節點，對應實際組織實體為駐場單位之一的廊橋維修公司。由于機位分配流程涉及到對廊橋的安排，因此廊橋維修會依照機場運行控制相關角色的指令，頻繁進行維修、待命等活動，在本例的蹤跡聚類下的交接網絡中，廊橋維修公司的節點度為25，高于其他角色；運行控制中心下屬的機位分配部門作為整個機位分配流程的中樞，需要對下屬角色下達指令，這類活動不需要頻繁進行，導致該節點度僅為6，其在交接網絡中的地位與實際情況有較大偏差。而基于蹤跡聚類與組織實體關系網絡中，各節點的節點度排序與實際情況較為符合，說明基于蹤跡聚類的組織實體關系網絡能夠比蹤跡聚類下的交接網絡更好地體現網絡中組織實體的實際情況。

4.2.2 實驗2

繼續對角色級別的組織實體進行重要度排序實驗，結果如表5所示。重要度評分較高的3個節點為28號節點、11號節點與17號節點，分別對應了機位分配流程中的運控機位分配、航站樓指揮協調、飛行區指揮協調角色。節點28、11在關系網絡中的中心性指標與重要度評分相吻合，節點17的中心性指標較低。對流程日志統計發現，節點17參與的全部33個流程實例中，節點28或節點11也一同參與的實例個數達到了26個，且不存在其他頻繁出現的節點。 因此，節點17在中心性指標較低的情況下得到了較高的重要度評分。

4.2.3 實驗3

進一步對資源級別的組織實體進行重要度排序實驗，結果如表6所示。可以看出重要度評分最高的155號節點的在度、接近中心性、中介中心性三項指標均有較高的值，證明該方法在推廣到數量更多的資源級別關系網絡時，也能較好地反映節點在關系網絡中的重要度。

4.2.4 實驗4

選用文獻[15]基于拓撲勢的網絡節點重要度排序算法對角色級別組織實體進行重要度排序，其中算法的影響因子σ取優化值1.0203[21]。文獻[15]算法所得重要度排序結果與本文算法排序結果的比較如表7所示。該算法所得排序結果中，重要度評分最高的節點與本文算法同為對應運控機位分配的28號節點，對應廊橋維修公司的12號節點的重要度評分為0.067639，高于對應航站樓指揮協調的11號節點的0.062033；對應安保部門的13號節點的重要度評分為0.053064，高于對應飛行區指揮協調的17號節點的0.049701。而廊橋維修公司與安保部門作為機場具體業務的實施角色，在實際的機位分配業務流程中，其重要程度不足以與負責指揮協調的航站樓指揮協調以及飛行區指揮協調兩大指揮角色相提并論。此外，該算法計算得到的節點重要度評分結果中，評分值同為0.040732的有6個節點，評分值同為0.041853的有3個節點，造成一些重要度評分值相同節點的重要度難以區分。該算法在反映節點的重要度時強調網絡中節點的局域連接密集程度的重要性，因此在空手道俱樂部網絡以及海豚關系網絡上實現了網絡中社區內節點的有效區分，取得了較好的實驗結果。但該算法不能很好地體現節點在整個網絡或整個社區的地位，算法的組織實體排序結果雖然能夠根據業務流程關系網絡中節點的拓撲勢找出業務流程中的最重要組織實體節點，但對于一些次重要的節點并不能很好地反映其實際重要度；同時，該算法在評價節點的重要度時，依賴于節點拓撲勢的計算，因此當網絡中存在局域連接密集程度相近的節點，易得到相同的節點重要度評分，此時相同評分節點的重要度便變得難以區分。而本文算法在構造關系網絡后，通過蹤跡聚類信息進行社區劃分，得到的排序結果與實際業務流程更為一致；同時由于加入了蹤跡聚類信息，對于局域連接密集程度相近節點的重要度也能夠根據蹤跡聚類的社區劃分計算出不同的評分從而加以區分。

5 結語

本文針對傳統社會網絡分析方法對蹤跡聚類得到的業務流程進行組織挖掘時表現不佳的問題，提出了一種基于蹤跡聚類與組織實體關系網絡的組織實體重要度排序方法，通過建模蹤跡聚類與組織實體間的關系網絡，對關系網絡中的組織實體節點進行重要度評分的計算，從而對不同蹤跡聚類下各級別的組織實體進行重要度排序。實驗表明組織實體的重要度排序結果能夠反映為關系網絡在節點中的重要度排序，從而解決前述問題，并有助于對蹤跡聚類結果的理解。

參考文獻：

[1]van der AALST W M P. Process Mining： Discovery， Conformance and Enhancement of Business Processes[M]. Berlin： Springer Science & Business Media， 2011： 11-16.

[2]ROZINAT A， de JONG I S M， GUNTHER C W， et al. Process mining applied to the test process of wafer scanners in ASML[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C： Applications and Reviews， 2009， 39（4）： 474-479.

[3]van der AALST W M P， ADRIANSYAH A， de MEDEIROS A K A， et al. Process mining manifesto[C]// Proceedings of the 10th International Conference on Business Process Management. Berlin： Springer， 2012： 169-194.

[4]van der AALST W M P， DUSTDAR S. Process mining put into context[J]. IEEE Internet Computing， 2012， 16（1）： 82-86.

[5]FERREIA D R， ALVES C. Discovering user communities in large event logs[C]// Proceedings of the 7th International Workshop on Business Process Intelligence. Berlin： Springer， 2012： 123 -134.

[6]LI M， LIU L，YIN L， et al. A process mining based approach to knowledge maintenance[J]. Information Systems Frontiers， 2011， 13（3）： 371-380.

[7]LIU R， AGAWAL S， SINDHGATTA R R， et al. Accelerating collaboration in task assignment using a socially enhanced resource model[C]// Proceedings of the 11th International Conference of Business Process Management. Berlin： Springer， 2013， 8094： 251-258.

[8]SONG M， GUNTHER C W， van der AALST W M P. Trace clustering in process mining[C]// Proceedings of the 7th International Conference on Business Process Management. Berlin： Springer， 2009： 109-120.

[9]BOSE R P J C， van der AALST W M P. Context aware trace clustering： towards improving process mining results[C]// Proceedings of the 2009 SIAM Data Mining Conference. Philadelphia： SIAM， 2009： 401-412.

[10]BOSE R P J C， van der AALST W M P. Trace clustering based on conserved patterns： towards achieving better process models[C]// Proceedings of the 8th International Conference on Business Process Management. Berlin： Springer， 2010： 170-181.

[11]SUN Y， HAN J， ZHAO P， et al. RankClus： integrating clustering with ranking for heterogeneous information network analysis[C]// Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology. New York： ACM， 2009： 565-576.

[12]SUN Y， YU Y， HAN J. Rankingbased clustering of heterogeneous information networks with star network schema[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 797-806.

[13]ZHONG S. Efficient online spherical kmeans clustering[C]// Proceedings of the 2005 IEEE International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2005： 3180-3185.

[14]譚躍進，吳俊，鄧宏鐘.復雜網絡中節點重要度評估的節點收縮方法[J].系統工程理論與實踐，2006，26（11）：79-83.（TAN Y J， WU J， DENG H Z. Evaluation method for node importance based on node contraction in complex networks[J]. Systems Engineering — Theory & Practice， 2006， 26（11）： 79-83.）

[15]張健沛，李泓波，楊靜，等.基于拓撲勢的網絡社區結點重要度排序算法[J].哈爾濱工程大學學報，2012，33（6）：745-752.（ZHANG J P， LI H B， YANG J， et al. An importancesorting algorithm of network community nodes based on topological potential[J]. Journal of Harbin Engineering University， 2012， 33（6）： 745-752.）

[16]朱濤，張水平，郭茂瀟，等.改進的加權復雜網絡節點重要度評估的收縮方法[J].系統工程與電子技術，2009，31（8）：1902-1905.（ZHU T， ZHANG S P， GUO M X， et al. Improved evaluation for node importance based on node contraction in weighted complex networks[J]. Systems Engineering and Electronics， 2009， 31（8）： 1902-1905.）

[17]CHEN D， LU L， SHANG M， et al. Identifying influential nodes in complex networks[J]. Physica A： Statistical Mechanics and its Applications， 2012， 391（4）： 1777-1787.

[18]陳靜，孫林夫.復雜網絡中節點重要度評估[J].西南交通大學學報，2009，44（3）：426-429.（CHEN J， SUN L F. Evaluation of node importance in complex networks[J]. Journal of Southwest Jiaotong University， 2009， 44（3）： 426-429.）

[19]趙毅寰，王祖林，鄭晶，等.利用重要性貢獻矩陣確定通信網中最重要節點[J].北京航空航天大學學報，2009，35（9）：1076-1079.（ZHAO Y H， WANG Z L， ZHENG J， et al. Finding most vital node by node importance contribution matrix in communication networks[J]. Journal of Beijing University of Aeronautics and Astronautics， 2009， 35（9）： 1076-1079.）

[20]周漩，張鳳鳴，李克武，等.利用重要度評價矩陣確定復雜網絡關鍵節點[J].物理學報，2012，61（5）：050201.（ZHOU X， ZHANG F M， LI K W， et al. Finding vital node by node importance evaluation matrix in complex networks[J]. Acta Physica Sinica， 2012， 61（5）： 050201.）

[21]淦文燕，赫南，李德毅，等.一種基于拓撲勢的網絡社區發現方法[J].軟件學報，2009，20（8）：2241-2254.（GAN W Y， HE N， LI D Y， et al. Community discovery method in networks based on topological potential[J]. Journal of Software， 2009， 20（8）： 2241-2254.）