1.2?國內外研究現狀

1.2.1?推薦在工作流系統中的應用

遵照工作流領域[11]的術語規范，本書將模型中某項業務的最小邏輯執行單元稱為任務（Task）；將某項正在運行的業務中已經執行過的任務、滿足條件可以執行的任務、當前正在執行的任務統稱為活動（activity）。這些內容將在第2章中詳細講解。

為更好地描述各種不同類型的推薦工作，本書總結出了各種不同的推薦類型（recommendation type，RecType），參見表1-2。推薦不是憑空進行的，必須依據一定量的歷史信息，這些信息可以是大量的執行過的工作流實例，也可以是建模人員積累的大量模型信息，表1-2中第1列指出了推薦類型所依據的是何種信息。推薦可以是對當前不完整的工作流實例進行的下一項可能執行活動的推薦，也可以是對當前建模模型的下一個可能的Task的推薦。表1-2中第2列指出了推薦類型做的是何種推薦，第3列內容為對各種推薦類型進行標記。

一個WfMS經過一段時間的運行，會積累一定數量的工作流模型，這些模型既包含當前正在使用的，也包含過去曾經使用但現在不再使用的模型，它們共同構成了工作流模型庫。當模型設計者在設計一個新模型時，可將當前不完整模型與模型庫中模型進行相似性匹配，向模型設計者推薦其可能建模的下一個Task，從而輔助模型設計者快速地建模。

Agnes Koschmider等人[52]利用元數據信息篩選出與當前模型塊相似的業務模型或業務模型塊，供模型設計者選用。他們方法的推薦粒度比較大，不完全是一次推薦一個活動，推薦出的可能是Task或Task組合，其推薦類型為RecType Ⅲ，以輔助業務模型建模。文獻[51, 53]先利用圖挖掘的方法從模型庫中找出子圖在整個庫中出現的頻率，從而建立一個模式表；然后用最小DFS（depth-first search，深度優先搜索）編碼[54]將模式表中圖結構表示的模型轉化成字符串，接著用字符串匹配的方法向當前不完整模型推薦其下一個可能的Task，輔助模型設計者建模。這種仍然是模型級別上的推薦，推薦類型為RecType Ⅲ。

在面向服務的計算（service oriented computing）領域，Web服務的發現及組合優化可以看作是工作流模型的構建；每個具體的Web服務確定后，就構成了一個由多個Web服務組成的Web應用，Web應用的每次具體執行可看作是工作流實例在執行。Web應用是工作流系統的特例，其中的活動自動化程度較高， 幾乎不需人工干預。在構造Web應用時，要得到更好的Web服務，以達到更優的Web組合和應用，就需要使用推薦技術。

文獻[55]將語義信息加入到Web服務的描述中，利用語義匹配的方法找出與當前用戶需求相符合的Web服務——候選Web服務列表；用戶選擇符合的Web服務后，還要求用戶對該服務打分；有了打分數據后就形成了用戶對Web服務的打分矩陣，在后來的推薦中使用基于物品的協同過濾算法（item-based collaborative filtering）[56]向用戶推薦Web服務。該方法沒有考慮Web服務間的執行順序信息，僅僅是在局部情景下對用戶當前的需求做出反應。本書的推薦方法考慮了活動間的執行順序信息，未考慮活動名稱間的語義匹配信息，但這可能成為我們未來的工作方向。本書第5章介紹的協同過濾所基于的打分矩陣與文獻[55]中的產生過程不同，是根據用戶執行過的實例活動序列信息與庫中其他實例的序列信息進行比較分析自動生成的，反映的是用戶對一個完整實例的偏好程度，而不是對一個活動的偏好程度。另外一區別在于，文獻[55]推薦時所依據的語義描述是預先確定的，而本書第5章的推薦方法依據的實例庫是事先不確定的。

文獻[50]提出的推薦方法，其應用場景是服務組合領域[57]。該文獻討論了如何更好地利用歷史服務組合例子來幫助構建當前的服務組合，利用離線創建的模式表向當前不完整的服務組合推薦下一個較合適的服務，是服務組合模型級別上的推薦，其推薦類型為RecType Ⅲ。拋開上述應用場景，該推薦方法同樣可以應用于本書的推薦場景——RecType I。因為該文獻中的實例庫的實例既不包含角色信息，也不包含用戶信息，所以在本書第4章中，我們將與文獻[50]的推薦方法通過實驗對比進行分析。

科學工作流系統[58-60]領域討論了如何根據工作流執行實例庫向用戶推薦和幫助用戶發現他們需要的、有用的工作流組件（workflow component）。此方法的缺點是，某個工作流組件的推薦是根據上游直接相鄰的一個結點，例如，如果a和b具有很強的相關性，即a→b，那么當執行a后，b就會被向用戶推薦。當不直接相鄰的上游結點存在強相關性時，這個推薦方法的結果就不準確。David Koop等人[61]提出了一種更復雜的方法，先利用實例庫信息確定所有可能的線性不間斷活動序列，為每個序列計算置信分（confidence score），向當前不完整的實例ě推薦時，從ě中找出置信分最大的那個序列，以其為基準向ě推薦其下一項可能的活動。該方法的缺點是當間斷的序列對下一項活動具有較強的影響時，推薦的結果就不太準確。

與本書相似，文獻[62]的推薦類型為RecType I，它采用歷史工作流實例信息對不完整實例進行下一項可能的活動推薦，它采用三種不同的方法篩選與不完整實例相似的完整實例：前綴法、集合法和多重集合法。前綴法僅僅考慮不完整實例的最后一項活動，完整實例在對應索引位置上的活動與該活動完全匹配才被篩選出來，這個要求太苛刻且沒有考慮該活動之前的活動信息；集合法和多重集合法則完全忽略了活動的順序信息。為克服這個方法的不足，本書第4章介紹的算法不僅考慮了不完整實例的最后一項活動，也考慮了該活動之前的活動信息，同時也考慮了這些活動的順序信息。

1.2.2?協同過濾

推薦系統是用來向當前用戶（active user）推薦其感興趣的商品或服務的程序或應用系統。從20世紀90年代初開始研究它以來，誕生了各種各樣的推薦算法。值得一提的是，在2006年，Netflix為改善自己的推薦系統性能，以高額的獎金為舉辦了一個推薦系統大賽之后，推薦系統和推薦算法的研究蓬勃發展，出現了各種各樣的系統優化和改進。從推薦系統的發展歷程來看，協同過濾（collaborative filtering，CF）是使用最為廣泛、研究最為深入的推薦方法，并在學術和工業界得到了成功應用。CF考慮了用戶間的愛好關系，將與當前用戶具有相似興趣的用戶所感興趣的項推薦給當前用戶。

David Goldberg等人于1992年首次提出CF這一術語，并利用CF技術對信息進行過濾。他們設計了系統Tapestry用于過濾和篩選出當前用戶感興趣的電子郵件，是第一個使用CF技術的系統。每個用戶需對他們已讀過的郵件進行標注（annotation），這些標注對其他使用系統的用戶可見，通過這些已有的標注， 當前用戶可以構造出過濾查詢語句，從而得到其真正需要和感興趣閱讀的郵件。Tapestry使用的CF不是自動的，需要用戶基于預先設計的查詢語言構造復雜的查詢語句。

GroupLens是第一個自動化CF系統，使用了基于用戶近鄰的（user-based，neighborhood-based）推薦算法。GroupLens向用戶推薦他們可能喜歡的文章。它的新聞閱讀客戶端（news reader clients）能夠顯示當前用戶對未閱讀文章的預測評分，也能夠接收用戶對已閱讀文章的評分。最初的GroupLens系統采用Pearson相關系數度量用戶間的相似性，并用所有近鄰用戶評分與其各自平均評分的差的加權平均作為最終的評分預測。為保護隱私，用戶評分時使用假名，這樣并不影響評分預測效果。Konstan等人討論了實現GroupLens協同過濾系統面臨的挑戰、GroupLens的運作機制、評分預測方法、用戶興趣的分布等， 指出個性化推薦要好于非個性化推薦。

上述基于用戶近鄰的CF算法的計算量隨著用戶數的增加而增加，當用戶的數量遠遠大于項的數量時，例如，商務網站Amazon的用戶數量就遠大于待銷售的書籍的數量，基于用戶近鄰的CF算法所需的計算量就特別巨大，不能滿足商務網站推薦的實時性要求。為克服上述缺點，使得推薦系統能在很短的時間內推薦出高質量的結果，基于項近鄰的（item-based, neighborhood-based）CF推薦算法被設計出來并得以運用[56]。與基于用戶近鄰的CF算法類似，基于項近鄰的CF算法首先計算項間的相似性，然后向當前用戶推薦與他喜歡項相似的項。由于項間的關系相對穩定，所以基于項近鄰的CF算法在保持與基于用戶近鄰CF算法相同推薦效果下能夠使用較少的在線計算時間。

當數據比較稀疏時，CF算法既無法找出當前用戶的近鄰用戶，也無法找出某些項的近鄰項，因此，其推薦效果就受到影響。例如，如果沒有用戶對新加入的項評分，那么這個項就無法被推薦。為了使基于CF的推薦系統運作良好，必須有一定數量的用戶對項進行評分。為解決數據的稀疏問題，Sarwar等人使用了一些專門設計的智能體自動地填充一些數值，從而方便CF算法的執行。這些智能體是一些自動打分的機器人，本身攜帶非協同過濾信息（基于內容的信息）對新加入的項進行評分，以此來解決數據的稀疏性問題。此外，數據稀疏還會造成兩個用戶共同評分的項比較少，這對采用Pearson相關系數計算用戶間相似性的算法帶來不利影響，解決辦法是使用默認評分（default voting）。