讲义文案详解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大学计算机科学系，加拿大塔省大学。加拿大艾伯塔。电子邮件：moshafiq@ucalgary.ca电子邮件：{alhajj,rokne}@ucalgary.ca 自动排名在自动化Web服务执行过程中至关重要。通常，使用Web服务的功能性和非功能性信息WebWebFP-TreeWebWeb1Web(2)Web可能的相关性，然后将其用于Web服务的自动排名和调整。FP-GrowthI.Web[1]WebWebWebWebWebWeb了解WebWeb2]Web服务的动态调用需要对通过WebWebWebWebWebWebWebWebWeb息（即基于WSDL的Web服务描述）并不能提供足够的信息来从可用的Web服务中发现所需的Web（Web）的混合方法来解决这一困境，并使用此信息来执行Web服务的发现和排名。7[10][11][12]13]在网络服务的自动排名和适应领域。此WebWebWebWebWebWeb(NFP)，WebWeb的方法来利用此类语义形式化和结构良好的方法。数据。因此，此类方法仍未充分发挥执行Web高度丰富且形式化的Web服务语义将提供大量有关Web服务的信息。FP-GrowthWeb服务排名和适应。首先，它建议在排名过程中考虑用户和Web服务提供商过去的交互，并建议对用户和Web服务提供商之间过去交互的日志进行语义形式化。其次，它使用轻量级语义来形式化日志，包括Web服务的功能和非功能方面以及它们过去的交互。第三，它提供了一种增强的关联图1.所提出解决方案的总体架构图1描述了使用基于语义FP-Growth的关联规则挖掘对Web服务进行排序和适应的总体情况。作为服务使用者的用户应用程序使用中间件应用程序搜索Web服务，该中间件应用程序执行发现、排名和适应，并最终调用所需的Web服务。对于每次交互，作为服务消费者的用户将他们的请求封装