Lecture Notes in Artificial Intelligence 3169 EditedbyJ.G.CarbonellandJ.Siekmann Subseries of Lecture Notes in Computer Science BamshadMobasher SarabjotSinghAnand(Eds.) Intelligent Techniques for Web Personalization IJCAI 2003 Workshop, ITWP 2003 Acapulco, Mexico, August 11, 2003 Revised Selected Papers 1 3 SeriesEditors JaimeG.Carbonell,CarnegieMellonUniversity,Pittsburgh,PA,USA JörgSiekmann,UniversityofSaarland,Saarbrücken,Germany VolumeEditors BamshadMobasher DePaulUniversity,CenterforWebIntelligence SchoolofComputerScience,TelecommunicationandInformationSystems Chicago,Illinois,USA E-mail:[email protected] SarabjotSinghAnand UniversityofWarwick,DepartmentofComputerScience CoventryCV47AL,UK E-mail:[email protected] LibraryofCongressControlNumber:2005935451 CRSubjectClassification(1998):I.2.11,K.4.1,K.4.4,C.2,H.3.4-5,H.5.3,I.2 ISSN 0302-9743 ISBN-10 3-540-29846-0SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-29846-5SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springeronline.com ©Springer-VerlagBerlinHeidelberg2005 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11577935 06/3142 543210 Preface WebpersonalizationcanbedefinedasanysetofactionsthatcantailortheWeb experience to a particular user or set ofusers.The experience canbe something ascasualasbrowsingaWebsiteoras(economically)significantastradingstock orpurchasingacar.Theactionscanrangefromsimplymakingthepresentation more pleasing to anticipating the needs of a user and providing customized and relevant information. To achieve effective personalization, organizations must rely on all available data, including the usage and click-stream data (reflect- ing user behavior), the site content, the site structure, domain knowledge, user demographics and profiles. In addition, efficient and intelligent techniques are needed to mine these data for actionable knowledge, and to effectively use the discovered knowledge to enhance the users’ Web experience. These techniques mustaddressimportantchallengesemanating fromthe size andthe heterogene- ity of the data, and the dynamic nature of user interactions with the Web. E-commerce and Web information systems are rich sources of difficult prob- lems and challenges for AI researchers. These challenges include the scalability of the personalization solutions, data integration, and successful integration of techniquesfrommachinelearning,informationretrievalandfiltering,databases, agent architectures,knowledge representation,data mining, text mining, statis- tics, user modelling and human–computer interaction. Throughout the history of the Web, AI has continued to play an essential role in the development of Web-basedinformationsystems,andnowit is believedthatpersonalizationwill prove to be the “killer-app” for AI. The collection of papers in this volume include extended versions of some of thepaperspresentedattheITWP2003workshopaswellasanumberofinvited chapters by leading researchers in the field of intelligent techniques for web personalization. The first chapter in the book provides a broad overview of the topicandacomprehensivebibliographyofresearchintoWebpersonalizationthat hasbeencarriedoutinthe pastdecade.Therestofthe chaptersarearrangedin five parts eachaddressinga different aspectof the topic.PartI consists ofthree chapters focussed on user modelling. In the first of these chapters, Craig Miller describes the current state of our understanding of how users navigate the Web andthechallengesinmodellingthisbehavior.Further,thenecessarycapabilities of a working cognitive model of Web navigation by a user, an implementation of such a model and its evaluation are described. Next, Naren Ramakrishnan describeshisviewofpersonalizationbasedoncapturingtheinteractionalaspects underlying a user’s interaction with the Web in an attempt to model what it meansfora websiteto be personable.Thefinalchapterinthis partofthe book, by Bettina Berendt and Max Teltzrow, rather than modelling the user per se, discussesresultsfromauserstudy aimedatunderstandingtheprivacyconcerns of users and the effect of these concerns on current personalization strategies. They argue for improved communicationof privacy practice and benefits to the VI Preface users resulting from data disclosure and a better understanding of the effect of various types of data on the performance of the resulting personalization. The second part of the book consists of three chapters on recommender sys- tems. Inthe firstof these chapters Fabiana LorenziandFrancescoRicci provide a surveyofcase-basedapproachesto recommendationgenerationandproposea unifying frameworkto model case-basedrecommender systems.In the following chapter Lorraine McGinty and Barry Smyth describe a novel approach to item selection, known as adaptive selection, that balances similarity and diversity during a user interaction with a reactive recommender system. They show how adaptive selection can dramatically improve recommendation efficiency when compared with standard forms of critiquing. Finally, Robin Burke surveys the landscapeofpossiblehybridsystemsforpersonalization,describingseveralways in which base recommenders can be combined to form hybrid systems. The third part of the book consists of three chapters on enabling technolo- gies. The first of these, by Chuck Lam, introduces the use of associative neural networks for user-based as well as item-based collaborative filtering. It also dis- cusses the use of principal component analysis for dimensionality reduction. In the next chapter Tiffany Tang et al. propose the use of heuristics to limit the size of the candidate item set, hence improving the performance of traditional user-based collaborative filtering. Finally, Birgit Hay et al. propose a new al- gorithm for mining interesting Web navigational patterns that can be used for personalizing future interactions. The fourth part of the book consists of three chapters on personalizedinfor- mation access. The first of these chapters, by Kevin Keenoy and Mark Levene, surveys the current state of the art in personalized Web search. Apostolos Kri- tikopoulos and Martha Sideri follow this with a chapter describing an approach to personalizingsearchengine results usingWeb communities.Finally Tingshao Shu et al. present an approach to predicting a user’s current information needs using the content of pages visited and actions performed. The final part of the book consists of four chapters on systems and appli- cations. The first chapter in this part, by Barry Smyth et al., describes the application of personalized navigation to mobile portals to improve usability. Next, Magdalini Eirinaki et al. present their system for personalization based on content structures and user behavior. Arif Tumer et al. then present a pri- vacy framework for user agents to negotiate the level of disclosure of personal information on behalf of the user with Web services. Finally, Samir Aknine et al. present a multi-agent system for protecting Web surfers from racist content. August 2005 Bamshad Mobasher Sarabjot Singh Anand Table of Contents Intelligent Techniques for Web Personalization Sarabjot Singh Anand, Bamshad Mobasher ........................ 1 User Modelling Modeling Web Navigation: Methods and Challenges Craig S. Miller ................................................ 37 The Traits of the Personable Naren Ramakrishnan ........................................... 53 Addressing Users’ Privacy Concerns for Improving Personalization Quality: Towards an Integration of User Studies and Algorithm Evaluation Bettina Berendt, Maximilian Teltzrow ............................ 69 Recommender Systems Case-Based Recommender Systems: A Unifying View Fabiana Lorenzi, Francesco Ricci ................................ 89 Improving the Performance of Recommender Systems That Use Critiquing Lorraine McGinty, Barry Smyth ................................. 114 Hybrid Systems for PersonalizedRecommendations Robin Burke .................................................. 133 Enabling Technologies Collaborative Filtering Using Associative Neural Memory Chuck P. Lam ................................................. 153 Scaling Down Candidate Sets Based on the Temporal Feature of Items for Improved Hybrid Recommendations Tiffany Ya Tang, Pinata Winoto, Keith C.C. Chan ................ 169 Discovering Interesting Navigations on a Web Site Using SAMI Birgit Hay, Geert Wets, Koen Vanhoof ........................... 187 VIII Table of Contents Personalized Information Access Personalisationof Web Search Kevin Keenoy, Mark Levene..................................... 201 The Compass Filter: Search Engine Result PersonalizationUsing Web Communities Apostolos Kritikopoulos, Martha Sideri ........................... 229 Predicting Web Information Content Tingshao Zhu, Russ Greiner, Gerald Ha¨ubl, Bob Price.............. 241 Systems and Applications Mobile Portal Personalization:Tools and Techniques Barry Smyth, Kevin McCarthy, James Reilly ...................... 255 IKUM: An Integrated Web PersonalizationPlatform Based on Content Structures and User Behavior Magdalini Eirinaki, Joannis Vlachakis, Sarabjot Singh Anand ....... 272 A Semantic-Based User Privacy Protection Framework for Web Services Arif Tumer, Asuman Dogac, I. Hakki Toroslu ..................... 289 Web Personalisationfor Users Protection: A Multi-agent Method Samir Aknine, Aur´elien Slodzian, Ghislain Quenum ................ 306 Author Index................................................... 325 Intelligent Techniques for Web Personalization SarabjotSinghAnand1andBamshadMobasher2 1 DepartmentofComputerScience,UniversityofWarwick,CoventryCV47AL,UK [email protected] 2 CenterforWebIntelligence,SchoolofComputerScience,Telecommunications andInformationSystems,DePaulUniversity,Chicago,Illinois,USA [email protected] Abstract. Inthischapterweprovideacomprehensiveoverviewofthetopicof Intelligent Techniques for Web Personalization. Web Personalization isviewed asanapplicationofdataminingandmachinelearningtechniquestobuildmod- els of user behaviour that can be applied to the task of predicting user needs andadaptingfutureinteractionswiththeultimategoalofimprovedusersatisfac- tion. Thischapter survey’s thestate-of-the-art inWebpersonalization. Westart byprovidingadescriptionofthepersonalizationprocessandaclassificationof the current approaches toWeb personalization. We discuss the various sources ofdataavailabletopersonalizationsystems,themodellingapproachesemployed andthecurrentapproachestoevaluatingthesesystems.Anumberofchallenges facedbyresearchersdevelopingthesesystemsaredescribedasaresolutionsto thesechallengesproposedinliterature.Thechapterconcludeswithadiscussion ontheopenchallengesthatmustbeaddressedbytheresearchcommunityifthis technologyistomakeapositiveimpactonusersatisfactionwiththeWeb. 1 Introduction The term information overload is almost synonymous with the Internet, referring to thesheervolumeofinformationthatexistsinelectronicformatontheInternetandthe inabilityofhumanstoconsumeit.Thefreedomtoexpressoneselfthroughpublishing contenttotheWeb hasanumberofadvantages,however,thetask oftheconsumerof thiscontentismademoredifficultnotonlydueto theneedto assess the relevanceof theinformationtothetaskathandbutalsoduetotheneedtoassessthereliabilityand trustworthinessoftheinformationavailable. Informationretrievaltechnologieshave maturedin the last decade and search en- ginesdoa goodjobofindexingcontentavailableonthe Internetandmakingitavail- abletousers,iftheuserknowsexactlywhatheislookingforbutoften,searchengines themselves can return more information than the user could possibly process. Also, mostwidelyusedsearchenginesuseonlythecontentofWebdocumentsandtheirlink structurestoassesstherelevanceofthedocumenttotheuser’squery.Hence,nomatter whotheuserofthesearchengineis,ifthesamequeryisprovidedasinputtothesearch engine,theresultsreturnedwillbeexactlythesame. The need to provide users with information tailored to their needs led to the de- velopment of various information filtering techniques that built profiles of users and B.MobasherandS.S.Anand(Eds.):ITWP2003,LNAI3169,pp.1–36,2005. (cid:1)c Springer-VerlagBerlinHeidelberg2005 2 S.S.AnandandB.Mobasher attemptedto filter largedatastreams, presentingthe userwith onlythoseitemsthatit believestobeofinteresttotheuser. Thegoalofpersonalizationistoprovideuserswithwhattheywantorneedwithout requiring them to ask for it explicitly [1]. This does not in any way imply a fully- automatedprocess,insteaditencompassesscenarioswheretheuserisnotabletofully express exactly what the are looking for but in interacting with an intelligent system canleadthemtoitemsofinterest. IntelligentTechniquesforWebPersonalizationisaboutleveragingallavailablein- formationaboutusersofthe Web todeliverapersonalexperience.The“intelligence” ofthesetechniquesisatvariouslevelsrangingfromthegenerationofuseful,actionable knowledgethroughtotheinferencesmadeusingthisknowledgeandavailabledomain knowledgeatthetimeofgeneratingthepersonalizedexperiencefortheuser.Assuch, thisprocessofpersonalizationcanbeviewedasanapplicationofdataminingandhence requiringsupportfor all the phases of a typicaldata mining cycle [2] includingdata collection, pre-processing,pattern discovery and evaluation, in an off-line mode, and finallythedeploymentoftheknowledgeinreal-timetomediatebetweentheuserand theWeb. In this chapter we provide an overview of the topic of Intelligent Techniques for WebPersonalization.InSection 2wedescribetheprocessofpersonalizationinterms of an application of a data mining to the Web. Section 3 providesa classification of approachesto Web personalizationwhile in Section 4 we describe the data available forminingintheWeb domain,specificallyforthegenerationofusermodels.Section 5 describes the varioustechniques used in generating a personalized Web experience forusershighlightingtheadvantagesanddisadvantagesassociatedwitheachapproach. IssuesassociatedwithcurrentapproachestoWebpersonalizationarediscussedinSec- tion 6.Theimportantissue ofevaluatingWeb personalizationisdiscussedinSection 7.FinallythechapterconcludesinSection 8withadiscussiononthecurrentstateand futuredirectionofresearchinWebpersonalization. 2 The PersonalizationProcess Personalization aims to provideusers with what they need without requiring them to askforitexplicitly.Thismeansthatapersonalizationsystemmustsomehowinferwhat theuserrequiresbasedoneitherpreviousorcurrentinteractionswiththeuser.Thisin itselfassumesthatthesystemsomehowobtainsinformationontheuserandinferswhat hisneedsarebasedonthisinformation. In the contextof this book,we focuson personalizationof the Web or more gen- erally,anyrepositoryof objects(items) browseableeither throughnavigationoflinks betweentheobjectsorthroughsearch.Hence,thedomainweaddressincludesIntranets andtheInternetaswellasproduct/servicecatalogues.Moreformally,we assumethat we are given a universe of n items, I = {ij : 1 ≤ j ≤ n}, and a set of m users, U ={uk :1≤k ≤m},thathaveshownaninterest,inthepast,inasubsetoftheuni- verseofitems.Additionally,eachuser,uk,maybedescribedasat-dimensionalvector (ak1,ak2,....,akt) andeachitem, ij, byans-dimensionalvector(bj1,bj2,....,bjs). Further domainknowledgeabouttheitems,forexample,intheformofanontology,mayalso IntelligentTechniquesforWebPersonalization 3 be available. We will assume the existence of a functionru : I → [0,1]∪ ⊥ where k ij =⊥signifiesthattheitemij hasnotbeenratedbytheuser,uk 1 thatassignsarat- ingtoeachiteminI.LetIk(u) bethesetofitemscurrentlyunratedbytheuseruk,i.e. Ik(u) = {ij : ij ∈ I ∧ruk(ij) =⊥}.SimilarlyletIk(r) bethesetofitemsratedbythe useruk,i.e.Ik(r) =I −Ik(u). Thegoalofpersonalizationistorecommenditems,ij,toa userua,referredtoas theactiveuser,whereij ∈Ia(u)thatwouldbeofinteresttotheuser. Centraltoanysystemcapableofachievingthiswouldbeauser-centricdatamodel. Thisdatamaybecollectedimplicitlyorexplicitlybutineithercasemustbeattributable toaspecificuser.Whilethisseemsobvious,ontheWebitisnotalwaysstraightforward to associate, especiallyimplicitly collected data with a user. For example,serverlogs providearichalbeitnoisysourceofdatafromwhichimplicitmeasuresofuserinterest maybederived.DuetothestatelessnatureoftheWeb,anumberofheuristicsmustbe usedalongwithtechnologiessuchascookiestoidentifyreturnvisitorsandattributea sequenceofbehaviourstoasingleuservisit/transaction [3]. Once the data has been cleansed and stored within a user-centric model, analysis of the data can be carried outwith the aim of buildinga user modelthat can be used for predictingfutureinterests of the user. The exactrepresentationof this user model differs based on the approach taken to achieve personalization and the granularity of the information available. The task of learning the model would therefore differ in complexity based on the expressivenessof the user profile representation chosen and the data available. For example, the profile may be represented as vector of 2-tuples u(kn)(< i1,ruk(i1) >,< i2,ruk(i2) >,< i3,ruk(i3) > .... < in,ruk(in) >) where ij’s∈Iandru istheratingfunctionforuseruk.Inthepresenceofadomainontology, k theuserprofilemayactuallyreflectthestructureofthedomain [4],[5],[6].Recently, there has been a lot of research interest in generating aggregate usage profiles rather thanindividualuserprofiles [7],thatrepresentgroupbehaviourasopposedtothebe- haviourofasingleuser.Thedistinctionbetweenindividualandaggregateprofilesfor personalizationis akin to the distinction between lazy and eager learning in machine learning. Thenextstageoftheprocessistheevaluationoftheprofiles/knowledgegenerated. Theaimofthisstageistoevaluatehoweffectivethediscoveredknowledgeisinpredict- inguserinterest.Commonmetricsusedduringthisphasearecoverage,meanabsolute errorandROCsensitivity.SeeSection 7foramoredetaileddiscussiononevaluation metrics. Thedeploymentstagefollowsevaluation,wheretheknowledgegeneratedandeval- uatedwithintheprevioustwostagesoftheprocessisdeployedtogeneraterecommen- dationsinreal-timeastheusersnavigatetheWebsite.Thekeychallengeatthisstage isscalabilitywithrespecttothenumberofconcurrentusersusingthesystem. An essential, though often overlooked, part of the personalization process is the monitoringofthepersonalization.Anandetal.suggestthatthesuccessoftheperson- 1Note that a while we assume a continuous scale for rating, a number of recommender sys- temsuseadiscretescale.However,ourformalisationincorporatesthiscaseasasimplelinear transformationcanbeperformedonthescaletothe[0,1]interval.