講義文案詳解5054a725

FrequentPatternMiningusingSemanticFP-GrowthforEffectiveWebServiceRankingOmairDepartmentofComputerScience,UniversityofCalgary,Calgary,Alberta,Canada.:moshafiq@ucalgary.ca

RedaAlhajj,JonG.RokneDepartmentofComputerScience,UniversityofCalgary,Calgary,Alberta,Canada.AutomatedRankingiscrucialintheprocessofautomatedWebServicesexecution.Oftenadaptationandranking(usedinterchangeably)ofdiscoveredWebservicesiscarriedoutusingfunctionalandnonfunctionalinformationofWebServices.Existingapproachesareeitherfoundtobeonlyfocusingonsemanticmodelingandrepresentationonly,orusingdataminingandmachinelearningbasedapproachesonunstructuredandrawdatatoperformdiscoveryandranking.WeproposeanapproachtoallowsemanticallyformalizedrepresentationoflogsduringWebServiceexecutionandthenusesuchlogstoperformrankinganptationofdiscoveredWebServices.WehavebuiltSemanticFPTreebasedtechniquetoperformassociationrulelearningonfunctionalandnonfunctionalcharacteristicsofWebServices.TheprocessofautomatedexecutionofWebServicesisimprovedintwosteps,i.e.,(1)weprovidesemanticallyformalizedlogsthatmaintainwellstructuredandformalizedinformationaboutpastinctionsofServicesConsumersandWebServices,(2)weperformanextendedassociationruleminingonsemanticallyformalizedlogstofindoutanypossiblecorrelationinfunctionalandnonfunctionalcharacteristicsofWebServicesduringpastexecutionwhichisthenusedinautomatedrankinganptationofWebServices.WebServices;Discovery;Ranking;AssociationRuleMining;SemanticFP-Growth,SemanticLogs WebServices[1]havechangedtheWebfromstatictodynamicnaturewhereapplicationsmayactasServiceConsumersinordertoinvokeandutilizeWebServicesovertheWeb.ApplicationsasServiceConsumerscandynamicallyinvokeaWebServicebyprovidinginputandcangetaresponsebackasoutputprocessedbasedonthefunctionalityprovidedbytheWebService.BecauseoftheopennatureoftheWeb,itisnotpossibleforServiceConsumerstohaveapre-knowledgeofalltheavailableWebServicesovertheWeb[2].DynamicinvocationofWebServicesrequiresdynamicdiscoveryandrankingofWebServicesthatarefoundovertheWeb.InordertobringdynamismintheprocessofWebServiceinvocationandexecution,itiscrucialtomaketheprocessofWebServicediscoveryandrankingautomated[9].SeveralapproacheshavebeenproposedtomaketheprocessofdiscoveryandrankingofWebServicesautomated.However,wehaveseenmajorlackinginsuchapproaches.TraditionaldiscoveryandrankingapproachesforWebServiceshavebeenfoundtoo

limitedandarebasedonlyonsyntacticandpre-knowninformationofserviceswhichcauseslimitationsforuser-applicationstousenewlyavailableservices.Insteadofusingsyntacticapproaches,newapproacheshavebeenbuiltwhicharebasedonusinginformationfromsemanticallyenricheddescriptionsofWebServices.Theseapproachesrequireprecise,expressiveandmachineinterpretabledescriptionofserviceswithanaimtomakeiteasierforuserstosearchfortheservicesrequired.TheseapproacheshaveshownagoodpotentialtowardsenablingautomationinWebServicesandbecauseofthatSemanticWebServicesresearchhavegainedmomentumbutarestillfoundtobenotintheirfullpotentialtobeusedinpracticalscenariosforautomateddiscoveryandrankingofWebServicesasitwouldbeimpracticaltoassumethateveryuserandserviceproviderwillorporatefull-fledgesemanticsinrequestsaswellasWebServicedescriptions,respectively.Ontheotherhand,usingonlythebasicinformationaboutWebServices(i.e.,WSDLbasedWebServicedescriptions)doesnotprovideenoughinformationtobeabletodiscoverrequiredWebServicesoutoftheavailableones.Weattempttosolvethisdilemmabyproposingahybridapproachofpartiallyusingsemantics(suchasfunctionalandnon-functionalpropertiesofWebServices),andusethisinformationtoperformdiscoveryandrankingofWebServices. RelatedTherehasbeenalotofrelatedwork[7][10][11][13]intheareaofautomatedrankinganptationofWebServices.SuchrelatedworkspansfromusinghighlyformalizedandsemanticallyenricheddescriptionsofWebServicesanduserqueries,totheusageofdataminingandmachinelearningapproachesonrawdataofWebServices.SeveralapproacheshavebeenfoundthathaveusedassociationruleminingforadaptationandrankingofWebServicesandothersimilarsystems.Givenbelowarerelatedandexistingapproachesfollowedbycomparativeysisofsuchapproaches.WehaveobservedfromtheysisandreviewofexistingandrelatedapproacheslistedabovethatalmostalltheapproachesareeitherfocusedtowardsapplyingdataminingandheuristictechniquesonsyntacticdataofWebServicesandhencearesyntacticandlimited.WebelievethatsuchinformationislimitedandisnotenoughtofindtherankingofWebServices.WealsoexploredotherapproacheswhicharebasedonsemanticallyenricheddescriptionsofWebServices,likeNon-Functional20142014IEEEInternationalConferenceonWebProperties(NFPs),whichattempttoperformautomateddiscovery,rankingofWebServicesbutarelimited.First,suchapproachesdonottakeintoaccountanypasthistoryofinctionsofusersandWebServices,andsecond,suchapproachesdonottakeintoaccountanyextensivedataminingormachinelearningbasedapproachestomakeuseofsuchsemanticallyformalizedandwell-structureddata.Therefore,suchapproachesarestillnotintheirfullpotentialtoperformautomatedrankingofWebServices.Suchapproachesarenotonlylimitedfromtheofaccuracyandcompleteness,butarealsolimitedfromtheofscalabilityandhencetakesignificantamountoftimetoperformthetaskofautomateddiscoveryandranking.ThistakesustothedilemmaofeitheruserhighlyenrichedandformalsemanticsofWebServiceswhichwouldprovidealotofinformationaboutWebServices. OurproposedSemanticFP-GrowthalgorithmusingSemanticLogsenablestoperformeffectiveandefficientrankinganptationofWebServices.First,itproposestotakeintoaccountpastinctionsofusersandprovidersofWebServicesduringtheprocessofrankingandproposestosemanticallyformalizelogsforpastinctionsbetweenusersandprovidersofWebServices.Second,ituseslight-weightsemanticsforformalizationoflogsthatludefunctionalandnon-functionalaspectsofWebServicesaswellastheirpastinctions.Third,itprovidesanenhancedassociationruleminingalgorithmasSemanticFP-GrowthtoperformassociationruleminingbasedysisonSemanticLogswhichisthenusedtoperformrankinganptationforWebServices.Givenbelowareafewdefinitionswhichareimportanttopresenttheproposedsolution.Figure1.OverallarchitectureofproposedFigure1depictstheoverallpictureofrankingandadaptationofWebServicesusingAssociationRuleMiningbasedonSemanticFP-Growth.UserapplicationsasServiceConsumerssearchforWebServicesusingamiddlewareapplicationthatperformsdiscovery,rankingandadaptationandfinallyinvoketherequiredWebServices.Foreachinction,usersasServiceConsumersencapsulatetheirrequestsinourprescribedformforSemanticLogsandServiceProvidersmodelWebServicesusingprescribedspecificationsasperSemanticWebServices[8].EachoftherequestsfromuserapplicationsfordiscoveringandinvokingWebServicesaremodeledandstoredasSemanticLogsinarepository.SuchSemanticLogsarelateronretrievedandrepresentedintheformofSemanticFP-Treeandare

processedbyourproposedsemanticextensiontotheFP-Growthalgorithm.TheconstructedSemanticFP-TreeisthendiscretizedaftertranslatingsemanticaxiomsandgroundedintoanormalFP-TreefromwhichAssociationRulesamongdifferenteventsinthelogsarediscovered.ThediscoveredassociationrulesarethenusedduringtheprocessofrankingandadaptationofWebServicesselectionoutofthediscoveredsetofWebServicestoselectthebestone.OursolutionuniquelytakestheprocessofrankinganptationtothenextlevelbymakingtheinformationaboutWebServicesandpastinctionsformalizedandwell-structuredandthenusesassociationruleminingtechniquetoprocesstheinformation.Figure2showsaSemanticFP-TreethatisconstructedwithitemsasLogEvents,SC,SPorWS,usingthedefinitionsandalgorithmsmentionedinthissection.Logsareproducedduringtheprocessofdiscovery,ranking,adaptationandinvocationofWebServicesbyuserapplications.Logsrepresentthefoot-printofthewholeprocessofexecution.ThedescriptionoflogsishighlydependentuponWebServicedescriptions.ItcontainsasetofeventscalledLogEvents.Figure2.SemanticFPTreeofitemsinSemanticEvaluationandAssociationRulesarediscoveredandgeneratedafterprocessingandminingSemanticLogsusingourproposedapproachforSemanticextensionstoFP-Growth.Oncetheassociationrulesarediscovered,thediscoveredsetofWebServicesarematchedandranked.Wehaveuseddatasetsfrom[3][4]whichprovidedifferentparametersludingfunctionalandnon-functionalpropertiesofWebServices.TheexperimentswereperformedonInCore2CPU2.40GHz,4GBofRAM,Windows7.WeusedWeka z/ml/weka/)toperformAssociationRuleMiningondataderivedfromtheSemanticLogs.Weconductedanumberoftestsonthedatasetusedusingourproposedsolution.Westartedwithcomparisonana?vediscoveryengineforWebServicesthatdoesnotuseanyoptimizationorrankingtechniques.Wecomparedthebehaviorofbothapproachesandfoundoutthatthena?vediscoveryenginehastogothroughthedescriptionsofalltheWebServices,whereas,ourproposedapproachshortlistsandranksWebServicestofindoutthebestoneandhenceitrequirestoprocessasmallersetofWebServicedescriptions.Thena?vediscoveryenginehastoprocessthewholesearchspacewhichmakesitsprocessingtimeproportionaltothenumberofWebServicedescriptionsavailableirrespectiveofthenumberofWebServicesthatmaybeabletofulfilluserrequirements.Weusedanptedasignificantlyextensivetestdesigninordertomakestatisticallyfirmstatementsonthebehavioroftraditionalna?vediscoveryapproachaswellasourownproposedapproach.Weperformedseveralrepetitivetestrunsforsearchspacesforupto500availableWebServicesdescriptionsoutofwhichonlyafewoftheWebServicescouldmatchuserrequirements.Ourproposedsolutioncouldlimitthesearchspacebyperformingtheranking,andevenbetterthantheotherrankingapproach.Whereas,thetraditionalna?vediscoveryenginehadtosearchintoalmostallgivensearchspace.Thenextmetricusedfortheevaluationofourproposedapproachis‘precision’.PrecisionmeanstheratioofcorrectWebServicesoutofalltheWebServicesretrieved.Table1providesanoverviewofMeanAveragePrevision(MAP)calculatedfordifferenttestrunsi.e.,na?veapproachwithoutusinganyrankingtechniques,theotherrankingtechniqueandourproposedapproachforranking,ascase1,case2andcase3respectively.WehadlowerMAPforvalidationofrankedresultsbecausena?veapproachhastogothroughwholesearchspace.Whereas,rankingapproachescase2andcase3gottopre-filterWebServices.Ourproposedapproachpre-filteredWebServicesusingassociationrulesandthenperformdiscoveryandrankingonsmallersearchspace.WefurthernoticedahigherMAPforresults,usingourproposedsolutionandhavingtoperformdiscoveryandrankingonasmall,targetedaswellasrelevantsearchspace.Inmostofthecasesduringourexperiments,precisionwasfoundtobereasonablygood.Ourproposedapproachiseventuallybasedonourearlierwork[5][6]ontryingtoachieveasuitabletrade-offbetweentheaccuracyrequiredversustime-basedefficiencyofthematakingandrankingmechanismbypartiallyutilizingsemanticsthatkeepdatawell-expressedandwell-structuredandmakesiteasierfordataminingbasedapproachestouseitratherthanonlyfocusingonmodelingWebServicedescriptionswithoverlycomplexsemanticsortryingtoemploydataminingsolutiononunstructuredaswellasdisperseddata.Table1.ComparingMeaageCaseCaseCase TheusageofassociationruleminingwithSemanticLogshelpedusintwofoldmanner,i.e.,(1)semanticlogshelpedinprovidingwell-structuredandformalizeddatafromwhichitwaseasierforourtechniquetodeduceandcollectinformation,and(2)theassociationruleminingapproachhelpedinfindingoutpotentialbenefitsanddrawbacksofusingsomeWebServicesertainscenarioswhichhelpedusinpre-filteringWebServicestohaveasmallerandmoretargetedsearchspaceandhenceleadtomoreefficientandeffectiverankingtofindrequiredWebServices.WehavefoundoutthatsemanticannotationstoWebServicesareofhighnoveltyifusedreasonablywithproperlytunedandadaptedreasoningandminingprocess.Asanextstep,wewillinvestigateandbuildfurtherhybridtechniquesinvolvingsemanticannotationsanddataminingtoaddressmoreissuesforenhancedmonitoringandmanagementofWebServicesaswellasrelatedapplicationecution.

Inthispaper,weproposedauniqueapproachforrankingandadaptationofWebServicesusingAssociationRuleMiningbasedonourproposedSemanticLogsandSemanticextensionofFP-Growth.WeyzedexistingapproachesandfoundoutthatsuchapproachesarelimitedassuchapproacheseitherfocusonlyforsemanticallyformalizingdescriptionofWebServiceswithlimitedmechanismstoutilizesuchdescriptionsoruseheuristicbasedtechniquesonlimitedandsyntacticdataofWebServicesforrankingandadaptationofWebServices.SuchapproachesalsomerelytakeintoaccountpastinctionofServiceConsumersandServiceProviders.OurproposedapproachallowssemanticallyformalizedrepresentationoflogsduringWebServiceexecutionwhicharethenusedtoperformrankingandadaptationofthediscoveredWebServices.Evaluationshowsthetrade-offofpartiallyusingsemanticswithsemanticallyadaptedAssociationRuleMiningtechniqueshelpsinimprovingWebServicesselection.TheauthorswouldliketoacknowledgeNSERC,AITFandUniversityofCalgaryforsupportingthisresearch.WebServicesatW3C:W3C mendationsonWSDLandSOAP.AvailableatM.Bell"IntroductiontoServiceOrientedModeling",ServiceOrientedModeling:Serviceysis,Design,andArchitecture.(2008).Wiley&Sons,3.Y.Zhang,Z.Zheng,M.R.Lyu,"Wpress:AQoSawareSearchEngineforWebServices",inIEEEICWS2010,pages=8390,July2010,Miami,FL,USA.Y.Li,Y.Liu,L.Zhang,G.Li,B.Xie,andJ.Sun,“AnExploratoryStudyofWebServicesontheInte”,In2007IEEEICWS,SaltLakeCity,Utah,USA,2007,pp.380387.O.Shafiq,R.Alhajj,J.Rokne:LightweightSemantics&BayesianClassification,ahybridtechniqueforwebservicediscovery,inIEEEIRI,Aug2010,LasVegas,NV,USA.O.Shafiq,R.Alhajj,J.G.Rokne,"OntheSocialAspectsofalizedRankingforWebServices",In13thIEEEHPCC2011,September242011,Banff,AB,Canada.A.Segev,E.Toch,“ContextBasedMatchingandRankingofWebServicesforComposition”,inIEEETransactionsonServicesComputing,Vol.2,No.3,pp210222,Sept2009.D.Roman,H.Lausen,andU.Keller.D2v1.3.WebService ,OctomberD.Fensel,etal.:WhatiswrongwithWebServicesDiscovery.InproceedingsoftheW3CWorkshoponFrameworksforSemanticsinWebServices,Innsbruck,Austria,June2005.W.Rong,K.Liu,L.Liang,"alizedWebServiceRankingviaUserGroupCombiningAssociationRule",IEEEICWS2009,July610,2009,LosAngeles,CA,USA.E.AlMasri,Q.H.Mahmoud:InvestigatingwebservicesonWorldWideWeb.InWWW2008,Apr2008,Beijing,.E.AlMasri,Q.H.Mahmoud,“QoSbasedDiscoveryandRankingofWebServices”,in16thIEEE Honolulu,Hawa,USA,August1316,2007.B.M.Fonseca,P.BGolgher,E.S.DeMoura,andN.Ziviani,Usingassociationrulestodiscoverysearchenginesrelatedqueries.InLAWEB'03,November2003,Santiago,Chile.FP-GrowthWebOmairShafiqReda，JonG.Rokne大學(xué)計(jì)算機(jī)科學(xué)系，加拿大塔省大學(xué)。加拿大艾伯塔。電子郵件：moshafiq@ucalgary.ca電子郵件：{alhajj,rokne}@ucalgary.ca 自動(dòng)排名在自動(dòng)化Web服務(wù)執(zhí)行過(guò)程中至關(guān)重要。通常，使用Web服務(wù)的功能性和非功能性信息WebWebFP-TreeWebWeb1Web(2)Web可能的相關(guān)性，然后將其用于Web服務(wù)的自動(dòng)排名和調(diào)整。FP-GrowthI.Web[1]WebWebWebWebWebWeb了解WebWeb2]Web服務(wù)的動(dòng)態(tài)調(diào)用需要對(duì)通過(guò)WebWebWebWebWebWebWebWebWeb息（即基于WSDL的Web服務(wù)描述）并不能提供足夠的信息來(lái)從可用的Web服務(wù)中發(fā)現(xiàn)所需的Web（Web）的混合方法來(lái)解決這一困境，并使用此信息來(lái)執(zhí)行Web服務(wù)的發(fā)現(xiàn)和排名。7[10][11][12]13]在網(wǎng)絡(luò)服務(wù)的自動(dòng)排名和適應(yīng)領(lǐng)域。此WebWebWebWebWebWeb(NFP)，WebWeb的方法來(lái)利用此類語(yǔ)義形式化和結(jié)構(gòu)良好的方法。數(shù)據(jù)。因此，此類方法仍未充分發(fā)揮執(zhí)行Web高度豐富且形式化的Web服務(wù)語(yǔ)義將提供大量有關(guān)Web服務(wù)的信息。FP-GrowthWeb服務(wù)排名和適應(yīng)。首先，它建議在排名過(guò)程中考慮用戶和Web服務(wù)提供商過(guò)去的交互，并建議對(duì)用戶和Web服務(wù)提供商之間過(guò)去交互的日志進(jìn)行語(yǔ)義形式化。其次，它使用輕量級(jí)語(yǔ)義來(lái)形式化日志，包括Web服務(wù)的功能和非功能方面以及它們過(guò)去的交互。第三，它提供了一種增強(qiáng)的關(guān)聯(lián)圖1.所提出解決方案的總體架構(gòu)圖1描述了使用基于語(yǔ)義FP-Growth的關(guān)聯(lián)規(guī)則挖掘?qū)eb服務(wù)進(jìn)行排序和適應(yīng)的總體情況。作為服務(wù)使用者的用戶應(yīng)用程序使用中間件應(yīng)用程序搜索Web服務(wù)，該中間件應(yīng)用程序執(zhí)行發(fā)現(xiàn)、排名和適應(yīng)，并最終調(diào)用所需的Web服務(wù)。對(duì)于每次交互，作為服務(wù)消費(fèi)者的用戶將他們的請(qǐng)求封裝