基于關(guān)聯(lián)規(guī)則挖掘與用戶情景感知的Web服務(wù)QoS預(yù)測(cè)

摘要：作為Web服務(wù)的非功能性屬性，QoS在服務(wù)選擇與服務(wù)組合中扮演著重要角色。由于一些QoS屬性值會(huì)隨著用戶情景屬性的變化而動(dòng)態(tài)變化，因此在做服務(wù)選擇或服務(wù)組合之前先對(duì)Web服務(wù)的QoS做預(yù)測(cè)是非常必要的。該文提出運(yùn)用數(shù)據(jù)挖掘技術(shù)挖掘服務(wù)組合執(zhí)行日志，研究服務(wù)QoS和用戶情景間的關(guān)聯(lián)關(guān)系，根據(jù)得到的關(guān)聯(lián)規(guī)則對(duì)不同用戶做個(gè)性化服務(wù)預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明我們的方法非常有研究?jī)r(jià)值。

關(guān)鍵詞：Web服務(wù)；服務(wù)質(zhì)量（QoS）；用戶情景；服務(wù)預(yù)測(cè)；關(guān)聯(lián)規(guī)則挖掘

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8158-02

作為近年來非常有前景的一項(xiàng)技術(shù)，Web服務(wù)的核心任務(wù)是產(chǎn)生和共享獨(dú)立自主的軟件程序。通常情況下，對(duì)于一個(gè)Web服務(wù)，有三個(gè)實(shí)體與之密切相關(guān)：服務(wù)提供者，服務(wù)注冊(cè)機(jī)構(gòu)以及用戶。隨著Web服務(wù)需求的不斷增長(zhǎng)，越來越多的服務(wù)提供者開始提供種類繁多的Web服務(wù)，其中有許多功能相同、模型結(jié)構(gòu)相似，但服務(wù)質(zhì)量（QoS）各異。

研究者普遍認(rèn)為，基于QoS的Web服務(wù)的搜索和選擇是一項(xiàng)非常重要的技術(shù)，因?yàn)樗梢杂行ПＷC以Web服務(wù)為基本元組的應(yīng)用系統(tǒng)的質(zhì)量。Web服務(wù)的QoS屬性包括可用性、費(fèi)用、響應(yīng)時(shí)間和產(chǎn)量等。作為衡量Web服務(wù)的非功能性屬性的主要指標(biāo)之一，QoS是重要的決策依據(jù)。通過測(cè)量和比較不同候選Web服務(wù)的QoS值，我們可以找出最優(yōu)值所對(duì)應(yīng)的那個(gè)Web服務(wù)。在實(shí)際情況中，一些QoS屬性如服務(wù)價(jià)格的值基本上保持穩(wěn)定，但另一些如響應(yīng)時(shí)間和產(chǎn)量卻常常是動(dòng)態(tài)變化的，因此QoS的應(yīng)用較為復(fù)雜。事實(shí)上，我們很難預(yù)先知道一個(gè)Web服務(wù)的非功能性性能。一種解決方法就是預(yù)測(cè)服務(wù)的QoS值。QoS預(yù)測(cè)的方法包括利用統(tǒng)計(jì)學(xué)模型、仿真模擬和數(shù)據(jù)挖掘等技術(shù)[1]。

近年來，利用數(shù)據(jù)挖掘技術(shù)做服務(wù)預(yù)測(cè)得到了較大關(guān)注。常見的運(yùn)用于服務(wù)組合領(lǐng)域的數(shù)據(jù)挖掘技術(shù)主要有對(duì)Web服務(wù)或用戶進(jìn)行分類、挖掘服務(wù)之間、用戶之間或服務(wù)與用戶之間的關(guān)聯(lián)規(guī)則等。Ying Chen收稿日期：2014-11-08

作者簡(jiǎn)介：劉宇喬（1990-），女，內(nèi)蒙古鄂爾多斯人，同濟(jì)大學(xué)碩士研究生，研究方向?yàn)榉?wù)組合預(yù)測(cè)。等人在一個(gè)服務(wù)型系統(tǒng)框架的研究中詳細(xì)闡述了4種數(shù)據(jù)挖掘技術(shù)的用法，包括服務(wù)分類分析、服務(wù)（用戶）聚類、服務(wù)關(guān)聯(lián)規(guī)則分析和服務(wù)順序調(diào)用模式分析等。Jorge Cardoso[1]利用數(shù)據(jù)挖掘技術(shù)對(duì)組合服務(wù)工作流的QoS數(shù)據(jù)進(jìn)行處理，實(shí)現(xiàn)對(duì)工作流QoS值的預(yù)測(cè)。目前，關(guān)聯(lián)規(guī)則挖掘在服務(wù)組合領(lǐng)域運(yùn)用較為廣泛。如張明衛(wèi)[3]等人曾提出挖掘組合服務(wù)分支路徑關(guān)聯(lián)規(guī)則的方法。

現(xiàn)存研究有一個(gè)共同的缺點(diǎn)：不能充分反應(yīng)用戶的偏好，即不能體現(xiàn)用戶情景對(duì)服務(wù)組合的影響。其結(jié)果就是，相同請(qǐng)求得到的組合服務(wù)總是相同的，而用戶的差異性被忽略了。事實(shí)上，在服務(wù)組合中，僅僅考慮客觀屬性指標(biāo)（包括功能性屬性和非功能性屬性）是不夠的，用戶情景屬性（如地理位置和偏好等）也是影響組合結(jié)果的重要因子。具體說來，用戶情景與Web服務(wù)的QoS密切相關(guān)，一些QoS屬性會(huì)根據(jù)用戶情景屬性的變化而發(fā)生變化?；诖耍撐奶岢鼋Y(jié)合QoS和用戶情景對(duì)組合服務(wù)的影響，運(yùn)用數(shù)據(jù)挖掘技術(shù)找出QoS與用戶情兩者之間的關(guān)聯(lián)規(guī)則，根據(jù)找到的關(guān)聯(lián)規(guī)則對(duì)Web服務(wù)做出QoS預(yù)測(cè)，從而明確哪些Web服務(wù)對(duì)特定用戶是最優(yōu)選擇。

1 問題描述

理想情況下，當(dāng)用戶的服務(wù)請(qǐng)求相似時(shí)，同一組Web服務(wù)即可滿足他們的需求。但實(shí)際情況是，雖然功能性需求可以保證滿足，但非功能性需求的實(shí)現(xiàn)情況對(duì)不同用戶的差異性很大。由于QoS會(huì)隨著用戶情景的變化而變化，即使用戶的服務(wù)請(qǐng)求相似，適合某一用戶的Web服務(wù)不一定是其他用戶的最優(yōu)選擇。這些用戶不同的地理位置或網(wǎng)絡(luò)環(huán)境都將對(duì)服務(wù)的調(diào)用結(jié)果產(chǎn)生重要影響。

下面我們具體用一個(gè)例子來加以說明。如圖1所示，用戶A和用戶B發(fā)出同一個(gè)服務(wù)請(qǐng)求。4個(gè)組件服務(wù)對(duì)其功能性需求做出響應(yīng)（假設(shè)該服務(wù)組合的模式是序列模式）。被兩個(gè)用戶調(diào)用后，Web服務(wù)S1，S2 和Sr的QoS值是一樣的，但服務(wù)S3的QoS值卻存在差異。有時(shí)候，即使是很小的差異，也會(huì)對(duì)整個(gè)組合服務(wù)的運(yùn)行結(jié)果產(chǎn)生巨大影響。引起這種QoS差異的主要因素是用戶情景因子，A、B用戶的情景（如地理位置、偏好等）不同，導(dǎo)致調(diào)用同一Web服務(wù)S3得到的QoS值不同。為解決這個(gè)問題，一些學(xué)者對(duì)用戶相似性進(jìn)行了研究，認(rèn)為同一Web服務(wù)經(jīng)相似用戶調(diào)用后得到的QoS值是一致的，所以相似用戶的相同的服務(wù)請(qǐng)求可得到相同的執(zhí)行結(jié)果。因此，要想知道某個(gè)Web服務(wù)對(duì)一個(gè)新用戶是否合適，可以通過研究與該用戶具有相似情景的用戶調(diào)用這個(gè)服務(wù)的日志，預(yù)測(cè)服務(wù)的QoS值來間接判斷。

2 基于關(guān)聯(lián)規(guī)則挖掘的Web服務(wù)QoS預(yù)測(cè)方法

與傳統(tǒng)的量化屬性因子值、計(jì)算用戶相似度的方法不同，本研究把不同情景屬性作為影響QoS的獨(dú)立因子，運(yùn)用數(shù)據(jù)挖掘方法挖掘用戶情景與服務(wù)QoS的相互關(guān)系。關(guān)聯(lián)規(guī)則挖掘?qū)τ诜治鲆粋€(gè)數(shù)據(jù)集中各元素關(guān)聯(lián)關(guān)系非常有效。一個(gè)關(guān)聯(lián)規(guī)則常被表示為X→Y，意思是當(dāng)元素集合X出現(xiàn)的時(shí)候，集合Y會(huì)以較大概率出現(xiàn)。對(duì)于本研究，用戶情景屬性與服務(wù)QoS屬性作為元素單元組成數(shù)據(jù)集，我們的主要目標(biāo)就是挖掘這兩種屬性元素的關(guān)聯(lián)關(guān)系。為了保證得出有效關(guān)聯(lián)規(guī)則，在應(yīng)用挖掘算法的時(shí)候需設(shè)置限制參數(shù)。關(guān)聯(lián)規(guī)則挖掘最常用的兩個(gè)參數(shù)是支持度和置信度。

假設(shè)I={I1，I2，I3，...Im}是元素項(xiàng)的集合。給定一個(gè)交易數(shù)據(jù)庫(kù)D，其中每個(gè)事務(wù)（Transaction）t是I的非空子集，即，每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符TID對(duì)應(yīng)。關(guān)聯(lián)規(guī)則在D中的支持度（support）是D中事務(wù)同時(shí)包含X、Y的百分比，即概率，算法如公式（1） 所示；置信度 （confidence）是D中事務(wù)已經(jīng)包含X的情況下，包含Y的百分比，即條件概率，算法如公式（2） 所示。如果滿足最小支持度閾值和最小置信度閾值，則認(rèn)為關(guān)聯(lián)規(guī)則是有趣的。這些閾值是根據(jù)挖掘需要人為設(shè)定的。endprint

為了運(yùn)用關(guān)聯(lián)挖掘算法，首先需要建立數(shù)據(jù)事務(wù)集D。為此，對(duì)于每條服務(wù)組合執(zhí)行日志，我們提取出所有的用戶情景屬性和Web服務(wù)QoS屬性，以及對(duì)應(yīng)的Web服務(wù)ID，將它們組成一條有效事務(wù)，每個(gè)情景屬性（或QoS屬性）即為該條事務(wù)一個(gè)元素項(xiàng)目（簡(jiǎn)稱項(xiàng)目）。表1所示為一條包含兩個(gè)情景屬性元素項(xiàng)和一個(gè)QoS屬性項(xiàng)目的服務(wù)事務(wù)。一條組合服務(wù)包含的組件服務(wù)可能有2個(gè)、3個(gè)甚至更多，則可從該條組合服務(wù)中可提取出滿足要求的相應(yīng)個(gè)數(shù)的服務(wù)事務(wù)。

其次，需要對(duì)各元素項(xiàng)目的值進(jìn)行規(guī)范化，使它們落在重復(fù)出現(xiàn)的幾個(gè)值域內(nèi)，以便進(jìn)行關(guān)聯(lián)規(guī)則挖掘。具體處理措施如下：對(duì)離散分布的用戶情景屬性值，我們把它們根據(jù)需要分在若干個(gè)區(qū)間域內(nèi)；對(duì)連續(xù)分布的QoS屬性值，我們把它們劃分成不同的等級(jí)，用整數(shù)1～5表示，代表質(zhì)量從高到低。

3 總結(jié)與未來工作展望

本文提出一種運(yùn)用關(guān)聯(lián)規(guī)則挖掘技術(shù)做Web服務(wù)QoS預(yù)測(cè)的方法。作為Web服務(wù)的重要特征指標(biāo)，QoS受用戶情景影響，隨著用戶的不同而動(dòng)態(tài)變化。為了針對(duì)不同用戶作個(gè)性化服務(wù)推薦，本研究著力于挖掘用戶情景屬性與QoS屬性的關(guān)聯(lián)關(guān)系，根據(jù)關(guān)聯(lián)關(guān)系分析某一Web服務(wù)是否可為某一用戶提供高質(zhì)量QoS，從而判斷是否將該服務(wù)推薦給該用戶。實(shí)驗(yàn)結(jié)果表明我們的方法能夠保證較高的預(yù)測(cè)準(zhǔn)確率，有廣闊的應(yīng)用前景。

雖然本研究實(shí)現(xiàn)了準(zhǔn)確預(yù)測(cè)服務(wù)QoS的目標(biāo)，但所用算法有待進(jìn)一步改進(jìn)：傳統(tǒng)的Apriori算法有兩大缺點(diǎn)，即可能產(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫(kù)，當(dāng)實(shí)驗(yàn)數(shù)據(jù)量較大時(shí)，實(shí)驗(yàn)性能可能會(huì)受到影響。未來的研究工作擬探索用FP-樹頻集算法挖掘用戶情景與服務(wù)QoS的關(guān)聯(lián)關(guān)系。

參考文獻(xiàn)：

[1] Cardoso J.Workflow Quality of Service Management using Data Mining Techniques[C].3rd International IEEE Conference Intelligent Systems London， 2006：479-482.

[2] Chen Y，Cohen B.Data mining and service rating in service-oriented architectures to improve information sharing[C]. Aerospace Conference， 2005 IEEE，2005：1-11.

[3] 張明衛(wèi)，魏偉杰，張斌，等.基于組合服務(wù)執(zhí)行信息的服務(wù)選取方法研究[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（8）： 1398-1411.

[4] Agrawal R， Imielinski T， Swami A N.Mining Association Rules between Sets of Items in Large Databases[C].Proceedings of 1993 ACM International Conference on Management of Data，Washington D.C，USA， 1993：207-216.endprint

為了運(yùn)用關(guān)聯(lián)挖掘算法，首先需要建立數(shù)據(jù)事務(wù)集D。為此，對(duì)于每條服務(wù)組合執(zhí)行日志，我們提取出所有的用戶情景屬性和Web服務(wù)QoS屬性，以及對(duì)應(yīng)的Web服務(wù)ID，將它們組成一條有效事務(wù)，每個(gè)情景屬性（或QoS屬性）即為該條事務(wù)一個(gè)元素項(xiàng)目（簡(jiǎn)稱項(xiàng)目）。表1所示為一條包含兩個(gè)情景屬性元素項(xiàng)和一個(gè)QoS屬性項(xiàng)目的服務(wù)事務(wù)。一條組合服務(wù)包含的組件服務(wù)可能有2個(gè)、3個(gè)甚至更多，則可從該條組合服務(wù)中可提取出滿足要求的相應(yīng)個(gè)數(shù)的服務(wù)事務(wù)。

其次，需要對(duì)各元素項(xiàng)目的值進(jìn)行規(guī)范化，使它們落在重復(fù)出現(xiàn)的幾個(gè)值域內(nèi)，以便進(jìn)行關(guān)聯(lián)規(guī)則挖掘。具體處理措施如下：對(duì)離散分布的用戶情景屬性值，我們把它們根據(jù)需要分在若干個(gè)區(qū)間域內(nèi)；對(duì)連續(xù)分布的QoS屬性值，我們把它們劃分成不同的等級(jí)，用整數(shù)1～5表示，代表質(zhì)量從高到低。

3 總結(jié)與未來工作展望

本文提出一種運(yùn)用關(guān)聯(lián)規(guī)則挖掘技術(shù)做Web服務(wù)QoS預(yù)測(cè)的方法。作為Web服務(wù)的重要特征指標(biāo)，QoS受用戶情景影響，隨著用戶的不同而動(dòng)態(tài)變化。為了針對(duì)不同用戶作個(gè)性化服務(wù)推薦，本研究著力于挖掘用戶情景屬性與QoS屬性的關(guān)聯(lián)關(guān)系，根據(jù)關(guān)聯(lián)關(guān)系分析某一Web服務(wù)是否可為某一用戶提供高質(zhì)量QoS，從而判斷是否將該服務(wù)推薦給該用戶。實(shí)驗(yàn)結(jié)果表明我們的方法能夠保證較高的預(yù)測(cè)準(zhǔn)確率，有廣闊的應(yīng)用前景。

雖然本研究實(shí)現(xiàn)了準(zhǔn)確預(yù)測(cè)服務(wù)QoS的目標(biāo)，但所用算法有待進(jìn)一步改進(jìn)：傳統(tǒng)的Apriori算法有兩大缺點(diǎn)，即可能產(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫(kù)，當(dāng)實(shí)驗(yàn)數(shù)據(jù)量較大時(shí)，實(shí)驗(yàn)性能可能會(huì)受到影響。未來的研究工作擬探索用FP-樹頻集算法挖掘用戶情景與服務(wù)QoS的關(guān)聯(lián)關(guān)系。

參考文獻(xiàn)：

[1] Cardoso J.Workflow Quality of Service Management using Data Mining Techniques[C].3rd International IEEE Conference Intelligent Systems London， 2006：479-482.

[2] Chen Y，Cohen B.Data mining and service rating in service-oriented architectures to improve information sharing[C]. Aerospace Conference， 2005 IEEE，2005：1-11.

[3] 張明衛(wèi)，魏偉杰，張斌，等.基于組合服務(wù)執(zhí)行信息的服務(wù)選取方法研究[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（8）： 1398-1411.

[4] Agrawal R， Imielinski T， Swami A N.Mining Association Rules between Sets of Items in Large Databases[C].Proceedings of 1993 ACM International Conference on Management of Data，Washington D.C，USA， 1993：207-216.endprint

為了運(yùn)用關(guān)聯(lián)挖掘算法，首先需要建立數(shù)據(jù)事務(wù)集D。為此，對(duì)于每條服務(wù)組合執(zhí)行日志，我們提取出所有的用戶情景屬性和Web服務(wù)QoS屬性，以及對(duì)應(yīng)的Web服務(wù)ID，將它們組成一條有效事務(wù)，每個(gè)情景屬性（或QoS屬性）即為該條事務(wù)一個(gè)元素項(xiàng)目（簡(jiǎn)稱項(xiàng)目）。表1所示為一條包含兩個(gè)情景屬性元素項(xiàng)和一個(gè)QoS屬性項(xiàng)目的服務(wù)事務(wù)。一條組合服務(wù)包含的組件服務(wù)可能有2個(gè)、3個(gè)甚至更多，則可從該條組合服務(wù)中可提取出滿足要求的相應(yīng)個(gè)數(shù)的服務(wù)事務(wù)。

其次，需要對(duì)各元素項(xiàng)目的值進(jìn)行規(guī)范化，使它們落在重復(fù)出現(xiàn)的幾個(gè)值域內(nèi)，以便進(jìn)行關(guān)聯(lián)規(guī)則挖掘。具體處理措施如下：對(duì)離散分布的用戶情景屬性值，我們把它們根據(jù)需要分在若干個(gè)區(qū)間域內(nèi)；對(duì)連續(xù)分布的QoS屬性值，我們把它們劃分成不同的等級(jí)，用整數(shù)1～5表示，代表質(zhì)量從高到低。

3 總結(jié)與未來工作展望

本文提出一種運(yùn)用關(guān)聯(lián)規(guī)則挖掘技術(shù)做Web服務(wù)QoS預(yù)測(cè)的方法。作為Web服務(wù)的重要特征指標(biāo)，QoS受用戶情景影響，隨著用戶的不同而動(dòng)態(tài)變化。為了針對(duì)不同用戶作個(gè)性化服務(wù)推薦，本研究著力于挖掘用戶情景屬性與QoS屬性的關(guān)聯(lián)關(guān)系，根據(jù)關(guān)聯(lián)關(guān)系分析某一Web服務(wù)是否可為某一用戶提供高質(zhì)量QoS，從而判斷是否將該服務(wù)推薦給該用戶。實(shí)驗(yàn)結(jié)果表明我們的方法能夠保證較高的預(yù)測(cè)準(zhǔn)確率，有廣闊的應(yīng)用前景。

雖然本研究實(shí)現(xiàn)了準(zhǔn)確預(yù)測(cè)服務(wù)QoS的目標(biāo)，但所用算法有待進(jìn)一步改進(jìn)：傳統(tǒng)的Apriori算法有兩大缺點(diǎn)，即可能產(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫(kù)，當(dāng)實(shí)驗(yàn)數(shù)據(jù)量較大時(shí)，實(shí)驗(yàn)性能可能會(huì)受到影響。未來的研究工作擬探索用FP-樹頻集算法挖掘用戶情景與服務(wù)QoS的關(guān)聯(lián)關(guān)系。

參考文獻(xiàn)：

[1] Cardoso J.Workflow Quality of Service Management using Data Mining Techniques[C].3rd International IEEE Conference Intelligent Systems London， 2006：479-482.

[2] Chen Y，Cohen B.Data mining and service rating in service-oriented architectures to improve information sharing[C]. Aerospace Conference， 2005 IEEE，2005：1-11.

[3] 張明衛(wèi)，魏偉杰，張斌，等.基于組合服務(wù)執(zhí)行信息的服務(wù)選取方法研究[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（8）： 1398-1411.

[4] Agrawal R， Imielinski T， Swami A N.Mining Association Rules between Sets of Items in Large Databases[C].Proceedings of 1993 ACM International Conference on Management of Data，Washington D.C，USA， 1993：207-216.endprint