《电子商务 E-business》阅读文献：Collaborative user modeling with user-generated tags for social recommender systems

Expert Systems with Applications 38(2011)8488-8496 Contents lists available at Science Direct Expert Systems with Applications ELSEVIER journalhomepagewww.elsevier.com/locate/eswa Collaborative user modeling with user-generated tags for social recommender systems Heung-Nam Kim,, Abdulmajeed Alkhaldi, Abdulmotaleb El Saddik., Geun-Sik Jo KI b School of Computer and Information Engineering. Inha University, 253 Younghyun-dong. Nam-gu, Incheon 402-751. Republic of Korea College of Computer and Information Sciences, King Saud University, Riyadh, Saudi arabia ARTICLE INFO ABSTRACT With the popularity of social media services, the sheer amount of content is increasing exponentially on the Social Web that leads to attract considerable attention to recommender systems. Recommender sys tems provide users with recommendations of items suited to their needs To provide proper recommen Recommender dations to users, recommender systems require an accurate user model that can reflect a users ocial media characteristics, preferences and needs. In this study, by leveraging user-generated tags as preference indi cators, we propose a new collaborative approach to user modeling that can be exploited to recommender systems. Our approach first discovers relevant and irrelevant topics for users, and then dual user model with collaboration from other similar users. In order to evaluate the our model, we compare experimental results with a user model based on coll pproaches and a vector space model. The experimental results have shown the proposed model provides a better representation in user interests and achieves better recommendation results in terms of accuracy e 2011 Elsevier Ltd. All rights reserved. 1 Introduction best use of"word-of-mouth"recommendations(Breese, man,& Kadie, 1998: Resnick, lacovo, Suchak, Bergstorm Social media has been changing the way people find information, 1994). Although the field of CF research has a large number share knowledge and communicate with each other. This social mation filtering problems, generally a typical CF domain starts with phenomenon has transformed the masses, who were only informa- rating information that maps user-item pairs on a set of numerical models in CF can be represented by ratings given 101m山m5hm able is increasing exponentially with daily additions. In turn, it is tagging. Consequently, a user model can profit by those tags in addi ecoming increasingly more difficult for users to find the most tion to ratings. Therefore, in the last few years, a number of studies attractive content and users often struggle with a great challenge have tried to combine recommender systems with social tagging in in terms of information overload( Siersdorfer Sizov, 2009). a way that can be highly beneficial to both areas(Milicevic, Nanop- Recommender systems that have emerged in response to the oulos, Ivanovic, 2010). Such systems generate automated recom- challenge provide users with recommendations of items that they mendations just as traditional recommender systems, but retain the would like the most(Adomavicius Tuzhilin, 2005). To provide flexibility of tagging information(Sen, vig, Riedl, 2009). In point of roper recommendations to users, the systems require information combining CF with tagging, they can be regarded as a new type of that includes a users characteristics, preferences, and needs, typi- hybrid recommender systems that utilize human perceptive con- cally referred to as a User Model(Godoy Amandi, 2005). Therefore, tent contained in items. The reason is that a set of aggregated tags building an accurate model for users is crucial to the success of rec on an item is rich and compact enough to characterize and describe ommender systems One of the most successful technologies among the same main concepts of the item although tag usage of users de- recommender systems is Collaborative Filtering(CF)that makes the ends on a type of media items(.g articles, music, videos, and phe tos)they annotate( Bischoff, Firan, Nejdl, Paiu, 2008: Li, Guo, Zhao, 2008: Wetzker, Zimmermann, Bauckhage, Albayrak, 2010). orresponding author. Tel. +1 613 562 5800x6248: fax: +1 613 562 5664 In this study, we introduce a new method of building a user E-mail address: hnkimemcrlab ottawa ca(H-N. Kim). model that can represent a user's diverse preferences, and thus 0957-4174 front matter o 2011 Elsevier Ltd. All rights reserved oi:10.1016eswa201101.048

Collaborative user modeling with user-generated tags for social recommender systems Heung-Nam Kim a,⇑ , Abdulmajeed Alkhaldi a , Abdulmotaleb El Saddik a,c , Geun-Sik Jo b a School of Information Technology and Engineering, University of Ottawa, 800 King Edward, Ottawa, Ontario, Canada K1N 6N5 b School of Computer and Information Engineering, Inha University, 253 Younghyun-dong, Nam-gu, Incheon 402-751, Republic of Korea c College of Computer and Information Sciences, King Saud University, Riyadh, Saudi Arabia article info Keywords: User modeling Personalization Recommender systems Social tagging Social media filtering abstract With the popularity of social media services, the sheer amount of content is increasing exponentially on the Social Web that leads to attract considerable attention to recommender systems. Recommender sys￾tems provide users with recommendations of items suited to their needs. To provide proper recommen￾dations to users, recommender systems require an accurate user model that can reflect a user’s characteristics, preferences and needs. In this study, by leveraging user-generated tags as preference indi￾cators, we propose a new collaborative approach to user modeling that can be exploited to recommender systems. Our approach first discovers relevant and irrelevant topics for users, and then enriches an indi￾vidual user model with collaboration from other similar users. In order to evaluate the performance of our model, we compare experimental results with a user model based on collaborative filtering approaches and a vector space model. The experimental results have shown the proposed model provides a better representation in user interests and achieves better recommendation results in terms of accuracy and ranking. 2011 Elsevier Ltd. All rights reserved. 1. Introduction Social media has been changing the way people find information, share knowledge and communicate with each other. This social phenomenon has transformed the masses, who were only informa￾tion consumers via mass media, to be producers of information. However, as rich information is shared through social media sites, the huge amount of information that has not previously been avail￾able is increasing exponentially with daily additions. In turn, it is becoming increasingly more difficult for users to find the most attractive content and users often struggle with a great challenge in terms of information overload (Siersdorfer & Sizov, 2009). Recommender systems that have emerged in response to the challenge provide users with recommendations of items that they would like the most (Adomavicius & Tuzhilin, 2005). To provide proper recommendations to users, the systems require information that includes a user’s characteristics, preferences, and needs, typi￾cally referred to as a User Model (Godoy & Amandi, 2005). Therefore, building an accurate model for users is crucial to the success of rec￾ommender systems. One of the most successful technologies among recommender systems is Collaborative Filtering (CF) that makes the best use of ‘‘word-of-mouth’’ recommendations (Breese, Hecker￾man, & Kadie, 1998; Resnick, Iacovou, Suchak, Bergstorm, & Riedl, 1994). Although the field of CF research has a large number of infor￾mation filtering problems, generally a typical CF domain starts with rating information that maps user-item pairs on a set of numerical values. Thus, user models in CF can be represented by ratings given by users on a set of items. Besides ratings, a number of modern ser￾vices also allow the users to add tags to the items, known as social tagging. Consequently, a user model can profit by those tags in addi￾tion to ratings. Therefore, in the last few years, a number of studies have tried to combine recommender systems with social tagging in a way that can be highly beneficial to both areas (Milicevic, Nanop￾oulos, & Ivanovic, 2010). Such systems generate automated recom￾mendations just as traditional recommender systems, but retain the flexibility of tagging information (Sen, Vig, & Riedl, 2009). In point of combining CF with tagging, they can be regarded as a new type of hybrid recommender systems that utilize human perceptive con￾tent contained in items. The reason is that a set of aggregated tags on an item is rich and compact enough to characterize and describe the same main concepts of the item although tag usage of users de￾pends on a type of media items (e.g., articles, music, videos, and pho￾tos) they annotate (Bischoff, Firan, Nejdl, & Paiu, 2008; Li, Guo, & Zhao, 2008; Wetzker, Zimmermann, Bauckhage, & Albayrak, 2010). In this study, we introduce a new method of building a user model that can represent a user’s diverse preferences, and thus 0957-4174/$ - see front matter 2011 Elsevier Ltd. All rights reserved. doi:10.1016/j.eswa.2011.01.048 ⇑ Corresponding author. Tel.: +1 613 562 5800x6248; fax: +1 613 562 5664. E-mail address: hnkim@mcrlab.uottawa.ca (H.-N. Kim). Expert Systems with Applications 38 (2011) 8488–8496 Contents lists available at ScienceDirect Expert Systems with Applications journal homepage: www.elsevier.com/locate/eswa

8 89 of users from user-generated tags. Analogous to our d a set of patterns, i.e., topics of inter- scovered provic systems. modeling description mendations of our approa sions are pre 2. Related work captur thus to build be ploit various aspects of user-g magnola et al. (2008)p enriched user model by analy meaning of tags. By applying system, namely icITY, th ndation navigating and tag e filteri users. Li et al. (2008) hat predict users

can be exploited to recommender systems. To build an individual user model, we connect tags and ratings as a way to infer a user’s topics of interest, in which each topic is composed of tags. In addi￾tion, to provide the model with more diversity, valuable topics in terms of both likes and dislikes are enriched in collaboration with other similar users. For recommending items relevant to user needs, we seamlessly incorporate collaborative characteristics into a content-based filtering approach so that recommender systems exploit the benefits of each, and thus alleviate the cold start prob￾lem and the overspecialization issue. The cold start problem describes a new user joins a recommender system and has pre￾sented few opinions (e.g., rating and tagging). With these situa￾tions, the system is generally unable to make high quality recommendations (Schein, Popescul, Ungar, & Pennock, 2002). The cold start users should be encouraged to continuously provide their opinions because they do not have enough historical informa￾tion. However, inaccurate recommendations from a dearth of reli￾able information on the users lead them to undermine the credibility of the system, and thus may cause their deviation from the system. Considering this point, a differentiated strategy of building the user model is necessary to make compelling recom￾mendations for those users. On the other hand, overspecialization refers to situations where a user model exclusively relies on tags which are used by a user or labeled in his/her rated items. With those cases, it is hard to recommend novel items different from anything the user has previously rated (Adomavicius & Tuzhilin, 2005). The main contributions of this paper toward user modeling in recommender systems can be summarized as follows: (i) We pro￾pose a new method of building a collaborative user model by lever￾aging user-generated tags. And we present a detailed method of topic-driven enrichments in collaboration with similar users that makes an individual model abundant. (ii) We present how the col￾laborative model can be applied to a recommender system. A lo￾cally weighted naïve Bayes approach is employed to recommend a ranked list of items relevant to users’ needs. We show how well our approach effectively works in terms of improving the recom￾mendation quality and in dealing with cold start users. (iii) We present a new approach to identify two sets of similar neighbors by seamlessly combining rating information and tagging informa￾tion. In particular, we separate out the neighborhood with respect to relevant tags from the neighborhood with respect to irrelevant tags. We demonstrate how two separated neighborhoods offer an advantage over a single set of the neighborhood. The rest of this paper is organized as follows: in next section we provide recent studies applying social tagging to recommender systems. In Section 3, we present a collaborative approach to user modeling for enriching valuable tags. We then provide a detailed description of how the proposed model is used for item recom￾mendations in Section 4. In Section 5, we present the performance of our approach through experimental evaluations. Finally, conclu￾sions are presented and future work is discussed in Section 6. 2. Related work The popularity of the usage of user-generated tags allows us to capture valuable information for understanding user interests and thus to build better user models. There are several studies that ex￾ploit various aspects of user-generated tags to user modeling. Car￾magnola et al. (2008) proposed a new approach of constructing an enriched user model by analyzing users’ tagging behaviors and the meaning of tags. By applying the user model to a cultural heritage system, namely iCITY, the system supports personalized ways of navigating and tagging content, as well as recommend content to users. Li et al. (2008) presented a method of discovering common interests of users from user-generated tags. Analogous to our study, the authors discovered a set of patterns, i.e., topics of inter￾est, that frequently co-occurred in tags added by users, and thus clustered users and resources according to each topic discovered. A similar approach is presented by Au Yeung, Cibbins, and Shadbolt (2009) as well. The authors constructed a user’s model in the form of a set of frequent tag patterns representing multiple interests of the user. The concept of discovering frequent tag patterns and sub￾sequently grouping users according to tags in the patterns is close to our work. However, differing from these two studies, our work identifies and enriched further tag patterns of value to each user in collaboration with other similar users. More recently, in Wang, Clements, Wang, De Vries, and Reinders (2010), three types of per￾sonalization models in collaborative tagging systems are intro￾duced according to user tasks: a collaborative tagging model, a collaborative browsing model, and a collaborative item search model. Guy, Zwerdling, Ronen, Carmel, and Uziel (2010) aggre￾gated relationship information among users, tags, and items across various social media services within enterprise application envi￾ronment. From those aggregated relationships, a user model is rep￾resented that contains a set of related users and a set of related tags. Wetzker et al. (2010) proposed a user-centric tag model map￾ping individual tag vocabularies, known as personomies, on the corresponding folksonomies. They also presented how the model can be applied to tag recommendations and tag-based social search, rather than item recommendations. In recent years, social tagging has also attracted considerable attention to recommender systems. In fact, many researchers have proposed a new application for recommender systems supporting the suggestion of suitable tags in annotating items. However, since our study focus on the collaborative nature of user modeling with social tagging for item recommendations, we mainly review stud￾ies dealing with item recommendations. Some early work in using tags for recommender systems is presented by Ji, Yeon, Kim, and Jo (2007). The authors first determine similarities between users with user-generated tags and subsequently identify the latent tags for each user by using a CF approach. Tso-Sutter, Marinho, and Thieme (2008) proposed a generic method that allows tags to be incorpo￾rated into standard CF algorithms by reducing three-dimensional correlations (i.e., user-item-tag) to three two-dimensional correla￾tions and then applying a fusion method to re-associate these cor￾relations. In Nakamoto et al. (2008), Reasonable Tag-based CF (RCF) is proposed assuming that tags generated by a user are synony￾mous with the reasons why the user liked an item. In RCF, tags are first clustered into topics by using an expectation-maximiza￾tion (EM) algorithm. Afterwards, feature vectors of topics and items for each user, referred to as topic domain vectors, are created to find similar users and thus to recommend items in terms of topic domains. A Similar notion is previously described in De Gemmis, Lops, Semeraro, and Basile (2008) in which a user profile consists of two parts: profile_like and profile_dislike. The former contains features that help in finding relevant items whereas the latter helps in filtering out non-relevant items. A multivariate Poisson model for naïve Bayes is employed to estimate the posteriori prob￾ability and subsequently recommend a ranked list of items. There is the main difference between De Gemmis et al. (2008) and our work. Our work incorporates collaborative characteristics into a content-based recommendation that utilizes rating information and tagging information. On the other hand, De Gemmis et al. (2008) studied a typical content-based system that analyzes tex￾tual descriptions, such as summaries, reviews, and abstracts, in addition to ratings and user-generated tags. More recently, Siers￾dorfer and Sizov (2009) represented social tagging in the form of a vector space model that could apply to existing recommendation methods, i.e., content-based filtering and collaborative filtering. Sen and Vig (2009) introduced Tagommenders that predict users’ H.-N. Kim et al. / Expert Systems with Applications 38 (2011) 8488–8496 8489

8490 H.-N. Kim et aL/ Expert Systems with Applications 38(2011)8488-8496 preference for items by inferring the users' preference for tags. As shown in Fig. 1. from the ratings of items that have previously The authors extended content-based recommendation methods rated by a user, we classify the items into two portions: a seto&? in a way that learned relationships between tags and items sitive(relevant)items and a set of negative (irrelevant )items. based on inferred tag preferences and item ratings. In Zhen, Li, rating of a user for a certain item is greater than or equal to the and Yeung(2009), TagiCoFi is proposed integrating tagging infor- average rating Ru of the user, we then call this item a positive item ation into a model-based CF, particularly using relation regular- for him/her and a negative item otherwise. More formally, the set ized matrix factorization. Liang. Xu, Li, Nayak, and Tao (2010) of positive and negative items for user u are denoted as pos(u)and studied a user-based and an item-based CF combined with Neg(u) respectively such that Pos(u)=iEIRui> Ru. Neg(u)=i weighted tags, respectively. The authors considered all possible IRus Ru, and Pos(u)n Neg(u)=0. relationships between users, items and tags (i.e, user-item, tag- item and user-item similarities). 3. 1.2. Calculating weights of tags Similar to our motivation, the salient concept behind the above- In our study, we associate a weight of tags with a users rating. mentioned studies is that social tagging can be highly beneficial to rather than the well-known tf-idf weight. The calculation of the enhance the quality of recommender systems. Although the above- weight for tags is straightforward. First, the vector of rati mentioned studies give reasonable promise of improving the per- each user is normalized as rl= 1, and subsequently, the formance, our study is different from earlier work. Because users ized values are used for weights in terms of a user for a often use personal and self-reference tags, mostly helpful for them- mally, the weight of tag t annotated in item i for user u selves, we look into what a tagged item is about and how much a as wu(t), is computed by the user. To this end, in our study, we seamlessly integrate ratings wui(t)=Rui >,, r 2 (1) as explicit user interests and tags as implicit user interests. We then discover frequent topics and tags existing in a users set of both relevant and non-relevant items In addition rather than clus- Because a tag may appear in multiple items with different tering users according to the topics, we carry out topic-driven weights that quantify the interest of the tag for a certain user enrichments of a user model with collaboration from other users we compute the mean weight of the tag in the set of positive items so that the enriched model can reflect diverse topics not only rel- and negative items, respectively evant to user interests. but also irrelevant to user needs -(0x.增西ox则(0(2 3. Collaborative user modeling where P (t) is the set of positive items rated by user u containing In this section, we describe our approach to building a user tag t and lu(t) is the set of negative items rated by user u contain- model that is derived from the users ratings, as well as user-gen- ing tag t. Finally, the global weight of tag t for user u, denoted as uut. erated tags. Before going into further detail, the notation and def- can be illustrated by the following equation itions required for understanding our approach are introduced. Let U-1, U2,..., u be the set of all users, I=11, i2, (p+pm3)/2,ift∈m(t),t∈=(t) set of all items, and T-t1, tz,... tin be the set of all tags annotated Au ift∈F(t),tl(t) in items. Let r be a user-item rating matrix in which Rui represents ift∈s(t),t≠(t) the rating of user uE U on item iE L An element Rui either exists as numerical ordinal scale or is unknown. We denote unknown rat- ings by g. The matrix R can be decomposed into row vectors: 3. .3 DIscoverng topIcs each row vector represents the ratings of a particular user on each user. Because ew t tag patterns from a set of items rated by R=FI,., Ful with Fu=[Ru, 1,..., Ru n]. for every u E U. Therefore ry user has different tastes on items, a d ems. We also denote a set of items rated by a certain user u et used for the mining process should also be selected individually Iu=ie lVi: Rui+g. As for social tagging, a three-dimensional for each user. In the data mining research literature, frequent pat- tems)is projected onto a two-dimensional one lh ssign tags to terns are typically defined as patterns that occur at least as fre- quently as a predetermined threshold commonly referred to as a nly take tag-item relationships into account, informing how many this paper, we minimum support(Han, Pei, Yin, 2004). In our study, frequent imes a tag has been annotated in an item. We transform a bag- patterns are a set of tags that appear frequently together in either model of social tagging into a set-model indicating which tags oc- a set of a users positive items Pos(u)or a set of a user's negative cur and do not occur in a particular item. Formally, let Q be a tag ems Neg(u) As observed by previous studies(Bischoff et al, 2008: Li et al., item binary matrix in which Qi is set to 1 if item i has been anno- 2008), user-generated tags can cover the tated at least I times or more with tag t and 0 otherwise. ncepts of an ite and provide a higher-level abstraction on content of an item. Fur- thermore, according to a critical characteristic of social tagging, also 3. 1. Personal known as folksonomy, vocabularies that emerge organically from he tags can be considered to describe a particular topic for the item. n general, ratings or a user for Items renect now relevant or In this sense, if multiple tags are frequently annotated together with tags of an item are concise to the users understanding, and hence, a particular topic described apture content of the item(Li et al, 2008) It is worth examining hand, a set of tags appear frequently together in a user's set of neg- how we can connect the user's ratings and the tags assigned by ative items, the user might dislike a topic containing the tags Such other users in respect to the item. set of tags, i.e., a frequent tag pattern, can be discovered using exis ng frequent-pattern mining methods such as apriori scale of 1-5), each user would have his/ her own rating behavior. ative items, frequent tag patterns can also be divided

preference for items by inferring the users’ preference for tags. The authors extended content-based recommendation methods in a way that learned relationships between tags and items based on inferred tag preferences and item ratings. In Zhen, Li, and Yeung (2009), TagiCoFi is proposed integrating tagging infor￾mation into a model-based CF, particularly using relation regular￾ized matrix factorization. Liang, Xu, Li, Nayak, and Tao (2010) studied a user-based and an item-based CF combined with weighted tags, respectively. The authors considered all possible relationships between users, items and tags (i.e., user-item, tag￾item and user-item similarities). Similar to our motivation, the salient concept behind the above￾mentioned studies is that social tagging can be highly beneficial to enhance the quality of recommender systems. Although the above￾mentioned studies give reasonable promise of improving the per￾formance, our study is different from earlier work. Because users often use personal and self-reference tags, mostly helpful for them￾selves, we look into what a tagged item is about and how much a user prefers the item, rather than capturing what tags are used by the user. To this end, in our study, we seamlessly integrate ratings as explicit user interests and tags as implicit user interests. We then discover frequent topics and tags existing in a user’s set of both relevant and non-relevant items. In addition, rather than clus￾tering users according to the topics, we carry out topic-driven enrichments of a user model with collaboration from other users so that the enriched model can reflect diverse topics not only rel￾evant to user interests, but also irrelevant to user needs. 3. Collaborative user modeling In this section, we describe our approach to building a user model that is derived from the user’s ratings, as well as user-gen￾erated tags. Before going into further detail, the notation and def￾initions required for understanding our approach are introduced. Let U = u1, u2, ... , u|U| be the set of all users, I=i1, i2, ... , i|I| be the set of all items, and T = t1, t2, ... , t|T| be the set of all tags annotated in items. Let R be a user-item rating matrix in which Ru,i represents the rating of user u e U on item i e I. An element Ru,i either exists as numerical ordinal scale or is unknown. We denote unknown rat￾ings by £. The matrix R can be decomposed into row vectors: R ¼ ½~r1; ... ;~rjUj T with~ru ¼ ½Ru;1; ... ; Ru;jIj, for every u e U. Therefore, each row vector represents the ratings of a particular user on items. We also denote a set of items rated by a certain user u as Iu ¼ i 2 Ij8i : Ru;i – £. As for social tagging, a three-dimensional space between users, items, and tags (i.e., users assign tags to items) is projected onto a two-dimensional one. In this paper, we only take tag-item relationships into account, informing how many times a tag has been annotated in an item. We transform a bag￾model of social tagging into a set-model indicating which tags oc￾cur and do not occur in a particular item. Formally, let Q be a tag￾item binary matrix in which Qt,i is set to 1 if item i has been anno￾tated at least l times or more with tag t and 0 otherwise. 3.1. Personal user model from tags In general, ratings of a user for items reflect how relevant or interesting the items are to him/her. In addition, user-generated tags of an item are concise to the users understanding, and hence, capture content of the item (Li et al., 2008). It is worth examining how we can connect the user’s ratings and the tags assigned by other users in respect to the item. 3.1.1. Positive and negative items Although the rating scale is fixed as numerical values (e.g., a scale of 1–5), each user would have his/her own rating behavior. As shown in Fig. 1, from the ratings of items that have previously rated by a user, we classify the items into two portions: a set of po￾sitive (relevant) items and a set of negative (irrelevant) items. If a rating of a user for a certain item is greater than or equal to the average rating Ru of the user, we then call this item a positive item for him/her and a negative item otherwise. More formally, the set of positive and negative items for user u are denoted as Pos(u) and Neg(u), respectively such that PosðuÞ ¼ i 2 IjRu;i P Ru, NegðuÞ ¼ i 2 IjRu;i < Ru, and PosðuÞ \ NegðuÞ ¼ £. 3.1.2. Calculating weights of tags In our study, we associate a weight of tags with a user’s rating, rather than the well-known tf-idf weight. The calculation of the weight for tags is straightforward. First, the vector of ratings ~r for each user is normalized as k~rk ¼ 1, and subsequently, the normal￾ized values are used for weights in terms of a user for a tag. For￾mally, the weight of tag t annotated in item i for user u, denoted as wu,i(t), is computed by: wu;iðtÞ ¼ Ru;i ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi PjIj j¼1R2 u;j q ð1Þ Because a tag may appear in multiple items with different weights that quantify the interest of the tag for a certain user, we compute the mean weight of the tag in the set of positive items and negative items, respectively: lpos u;t ¼ 1 jI pos u ðtÞj X j2I pos u ðtÞ wu;jðtÞ; lneg u;t ¼ 1 jI neg u ðtÞj X j2I pos u ðtÞ wu;jðtÞ ð2Þ where I pos u ðtÞ is the set of positive items rated by user u containing tag t and I neg u ðtÞ is the set of negative items rated by user u contain￾ing tag t. Finally, the global weight of tag t for user u, denoted as lu,t, can be illustrated by the following equation: lu;t ¼ ðlpos u;t þ lneg u;t Þ=2; if t 2 I pos u ðtÞ;t 2 I neg u ðtÞ lpos u;t ; if t 2 I pos u ðtÞ;t R I neg u ðtÞ lneg u;t ; if t 2 I neg u ðtÞ;t R I pos u ðtÞ 8 >< >: ð3Þ 3.1.3. Discovering topics We discover frequent tag patterns from a set of items rated by each user. Because every user has different tastes on items, a data￾set used for the mining process should also be selected individually for each user. In the data mining research literature, frequent pat￾terns are typically defined as patterns that occur at least as fre￾quently as a predetermined threshold, commonly referred to as a minimum support (Han, Pei, & Yin, 2004). In our study, frequent patterns are a set of tags that appear frequently together in either a set of a user’s positive items Pos(u) or a set of a user’s negative items Neg(u). As observed by previous studies (Bischoff et al., 2008; Li et al., 2008), user-generated tags can cover the main concepts of an item and provide a higher-level abstraction on content of an item. Fur￾thermore, according to a critical characteristic of social tagging, also known as folksonomy, vocabularies that emerge organically from the tags can be considered to describe a particular topic for the item. In this sense, if multiple tags are frequently annotated together with each other in positive items of a user, the user would be interested in a particular topic described by the co-occurred tags. On the other hand, a set of tags appear frequently together in a user’s set of neg￾ative items, the user might dislike a topic containing the tags. Such set of tags, i.e., a frequent tag pattern, can be discovered using exist￾ing frequent-pattern mining methods such as Apriori (Agrawal & Srikant, 1994) and FP-growth (Han et al., 2004). Since a set of items rated by a user is divided into a set of positive items and a set of neg￾ative items, frequent tag patterns can also be divided into two por- 8490 H.-N. Kim et al. / Expert Systems with Applications 38 (2011) 8488–8496

H-N. Kim et aL/Expert Systems with Applications 38(2011)8488-8496 Negative items of User u Weights of Tag Positive Items of User u ★★★★★ tem3★★★ ★★tem7 a13 Tags m大2 Oau Tags o. 2 Hm6大大★ ★过m9k o iagn oa A [ TagL Item10★★ Fig. 1. Classification of positive items and negative items for a user according to his/her item ratings. tions according to the sets used for the mining process. We regard encounters serious limitations for finding a set of neighbors. In patterns discovered from the positive items as implicitly relevant practice, even when users are very active, the result of rated items topics, and patterns discovered from the negative items as implicitly is only a small proportion of the total number of items. Accord- irrelevant topics, defined as follows ingly, it is often the case that a pair of users has nothing in com- mon, and hence the similarity cannot be computed (Sarwar, Definition 1(Relevant topics). Let pattern p=, tz,..., tp be a set Karypis, Konstan, Reidl, 2001). Even when the computation of of tags such that p c T A relevant topic is defined as tag pattern p similarity is possible, it may not be very reliable, because insuffi- for which support of pattern p(ie, the ratio of items in the set cient information is processed. To that end, recent studies have Pos(u)that contains pattern p, written as Supu()) is greater than or determined similarities between users by using user-generated equal to the minimum support for us Bu tags instead of user ratings (i et al, 2007; Liang et al, 2010: Mar kines et al., 2009: Nakamoto et al., 2008: Siersdorfer Sizov 2009: Zhen et al, 2009). In this paper, we also identify the best neighbors Definition 2(Irrelevant topics). Analogous to a relevant topic, a based on tags labeled in items. However, differing from the previ- irrelevant topic is defined as a tag pattern for which the ratio of ous work, rating information is embedded into the tags when we items in the set Neg(u) that contains the pattern is greater than compute the similarities between users, rather than frequency- or equal to the minimum support for user u, Ou based weights for the tags. Moreover, as two users could like some According to the downward closure property of frequent pat- topics in common but could have a difference with respect to dis- terns, if a tag pattern is a frequent pattern, then all subsets of that likes, neighbors in terms of relevant topics are maintained to be pattern is also frequent patterns(Agrawal Srikant, 1994). As separated from neighbors in terms of irrelevant ones pointed out in Liet al. (2008) if all subsets of a certain pattern have In order to find k similar neighbors, the cosine similarity, which the same support value, then they are always annotated in the same quantifies the similarity of a pair of vectors according to their an- items among positive items(or negative items)of a user. In this gle, is employed to measure the similarity values between a target ase, the specific pattern may be more valuable to the userthan each user and every other user. Because a model of each user consists of individual pattern derived from the specific one. Inspired by Li et both relevant topics and irrelevant topics, we compute two simi- same as one another. We will henceforth use the term'topic'to refer and v in terms of relevant topics is measured by eg users, u by ToR, and Tolu the set of relevant topics and irrelevant topics, simpos Creme mn) ae Xkr (4) respectively. We present a formal description of a model for user r--LL x zeng--pr u as follows: IMu=(ToRu, Tolu), which is referred to as an initial mod el for him/her. To facilitate the following sections, we further define where ITu and ITp refer to the set of tags in relevant topics of user itive tag and a set of positive tags for user u is denoted as ITpo. and u with respect to irrelevant topics can also be calculated dr e some notations here. a tag occurring within the set ToRu is called a u and pectively. Analogously, the similarity between user u Analogously, a tag occurring within the set Tolu is called a negati tag and a set of negative tags for user u is denoted as ITweg 3. 2. Identifying tag-based neighborhood where Tu and IT refer to the set of tags in irrelevant topics of Before enriching a model for a certain user, we first need to user u and v, respectively form neighborhood of the user. The main goal of neig nation is to identify a set of users similar to a particular m The similarity value between a pair of users is in the range [0, 1] and the higher a users value, the more similar he/she is to a target monly referred to as neighbors. a typical collaborati user. Finally, for a given user E U, particular k users with the high-

tions according to the sets used for the mining process. We regard patterns discovered from the positive items as implicitly relevant topics, and patterns discovered from the negative items as implicitly irrelevant topics, defined as follows: Definition 1 (Relevant topics). Let pattern p = t1, t2, ... , t|p| be a set of tags such that p # T. A relevant topic is defined as tag pattern p for which support of pattern p (i.e., the ratio of items in the set Pos(u) that contains pattern p, written as Supu(p)) is greater than or equal to the minimum support for user u, hu. Definition 2 (Irrelevant topics). Analogous to a relevant topic, a irrelevant topic is defined as a tag pattern for which the ratio of items in the set Neg(u) that contains the pattern is greater than or equal to the minimum support for user u, hu. According to the downward closure property of frequent pat￾terns, if a tag pattern is a frequent pattern, then all subsets of that pattern is also frequent patterns (Agrawal & Srikant, 1994). As pointed out in Li et al. (2008), if all subsets of a certain pattern have the same support value, then they are always annotated in the same items among positive items (or negative items) of a user. In this case, the specific pattern may be more valuable to the user than each individual pattern derived from the specific one. Inspired by Li et al. (2008), we prune such subset patterns whose support values are the same as one another. We will henceforth use the term ‘topic’ to refer to the frequent tag patterns. Formally, for a given user u, we denote by ToRu and ToIu the set of relevant topics and irrelevant topics, respectively. We present a formal description of a model for user u as follows: IMu = hToRu, ToIui, which is referred to as an initial mod￾el for him/her. To facilitate the following sections, we further define some notations here. A tag occurring within the set ToRu is called a positive tag and a set of positive tags for user u is denoted as ITpos u . Analogously, a tag occurring within the set ToIu is called a negative tag and a set of negative tags for user u is denoted as ITneg u . 3.2. Identifying tag-based neighborhood Before enriching a model for a certain user, we first need to form neighborhood of the user. The main goal of neighborhood for￾mation is to identify a set of users similar to a particular user, com￾monly referred to as neighbors. A typical collaborative filtering encounters serious limitations for finding a set of neighbors. In practice, even when users are very active, the result of rated items is only a small proportion of the total number of items. Accord￾ingly, it is often the case that a pair of users has nothing in com￾mon, and hence the similarity cannot be computed (Sarwar, Karypis, Konstan, & Reidl, 2001). Even when the computation of similarity is possible, it may not be very reliable, because insuffi- cient information is processed. To that end, recent studies have determined similarities between users by using user-generated tags instead of user ratings (Ji et al., 2007; Liang et al., 2010; Mar￾kines et al., 2009; Nakamoto et al., 2008; Siersdorfer & Sizov, 2009; Zhen et al., 2009). In this paper, we also identify the best neighbors based on tags labeled in items. However, differing from the previ￾ous work, rating information is embedded into the tags when we compute the similarities between users, rather than frequency￾based weights for the tags. Moreover, as two users could like some topics in common but could have a difference with respect to dis￾likes, neighbors in terms of relevant topics are maintained to be separated from neighbors in terms of irrelevant ones. In order to find k similar neighbors, the cosine similarity, which quantifies the similarity of a pair of vectors according to their an￾gle, is employed to measure the similarity values between a target user and every other user. Because a model of each user consists of both relevant topics and irrelevant topics, we compute two simi￾larity values. Formally, the similarity between a pair of users, u and v in terms of relevant topics is measured by Eq. (4) simpos u;v ¼ P t2ðITpos u \ITpos v Þlpos u;v lpos u;t ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi P t2ITpos u lpos2 u;t q ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi P t2ITpos u lpos2 v;t q ð4Þ where ITpos u and ITpos v refer to the set of tags in relevant topics of user u and v, respectively. Analogously, the similarity between user u and v with respect to irrelevant topics can also be calculated as: simneg u;v ¼ P t2ðITneg u \ITneg v Þlneg u;v lneg u;t ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi P t2ITneg u lneg2 u;t q ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi P t2ITneg u lneg2 v;t q ð5Þ where ITneg u and ITneg v refer to the set of tags in irrelevant topics of user u and v, respectively. The similarity value between a pair of users is in the range [0, 1] and the higher a user’s value, the more similar he/she is to a target user. Finally, for a given user u e U, particular k users with the high￾Fig. 1. Classification of positive items and negative items for a user according to his/her item ratings. H.-N. Kim et al. / Expert Systems with Applications 38 (2011) 8488–8496 8491

H.-N. Kim et aL/ Expert Systems with Applications 38(2011)8488-8496 est similarity are identified as positive neighbors and negative neigh- only topic pz and p3 are used for enriching the model of user u if bors such that. they are not included in the set ToRu. Topics such as p2 and p3 are called enriched topics for user u, and tags such as t3 E P2 and Np (u)=arg max simp ta E p3 are called enriched tags for user u. Finally, a set of enriched topics is identified Nk(u)=arg max sim (6) neighbors of target user u. Note that some topics tha vEU\uN i froma other neighbor h such that simaLp> simp, for u+h If a particular 3.3. Enriching a user model topic is enriched many times from the neighbors, the target user is likely to be more interested in that topic. In an analogous fashion, Once we have identified the set of the nearest neighbors for a with respect to irrelevant topics, a set of enriched topics can be certain user u, his/her initial model IMu=(ToRu, Tol)described il determined from k negative neighbors Nk(u) of user u. Formally Section 3. is enriched rom the neighbors. The basic idea of EM,-(EToR. ETol where ETor, is the set of relevant topics en- to prefer similar tag patterns discovered within his her neighbors. ETolu is the set of irrelevant topics enriched from negative neigh- tive items of a user frequently contain tags "web2.0"and"semanticweb, "he/she may also be interested in rs such that ETolu n Tolu= o. For convenience we also define topics, such as"web2.0. ""semanticweb, "and"ontology, " that fre- any enriched tags occurring within either EToRu or ETolu as the quently appears in positive items of users similar to him/her. This ETo nlmp enriched tags from positive neighbors etp such that enrichment process is particularly effective to some users who do not contain topics sufficiently in their user model. ET such that ET nIT=0. Eventually, we represent user u As illustrated in Fig. 2, we elaborate on the general idea of to with the initial model IMu and the enriched model emu. We label driven enrichments in the foll the unified model the collaborative model for user u neighbor user V e npos(u) in descending order of similarity be- CMu(Mu. EMu) tween target user u and neighbors For each topic p; in ToRu, specific topics of pi in ToRy are identified. Given two topics Pi E ToRu and 4 Recommendation via probabilistic approach PjE ToRv, pi is said to a general topic of p; if and only if pi is a subset of pj. i.e.P. C Pr On the contrary, P, is called a specific topic of Pr For The final step is to generate recommendations such as a list of example, let pi=[t1 t2) be a relevant topic of user u such that top-N items that a user would like the most In our study, an item PiE ToRu, and ToR,=(p2, p3, p4. ps be the set of relevant topics of recommendation is treated classification problem that an and ps sftn that p2(, t2, t3), P3(t1,t2, ta). pa=(ti tz, ts, ts), item belongs to either a positive class Pos or a negative class of topic pi, they are said to the specific topics of pi whereas ps is adopt locally weighted naive Bayes( Frank, Hall, Pfahringer not the specific topic. In other words, pi is said to the general topic 2003) with the multinomial event model (McCallum Nigam, of topics p2, P3, and p4. Several specific topics occurring in the mod 1998)to recommend top-N items stochastically. To apply the el of neighbor v may be found. For efficient enrichment, we only naive Bayes classifier to the recommendation process of the target consider specific topics that have a higher support than that of a user u, for a given item i fIu, tags annotated in item i such that general topic. For example, assume that the support for Pl P2, P3, T-tETV: Q,. -l are used as feature variables. More formally, Sup(P2)=0.5. SupMp3)=0.47, and Supu(pa)=0.35). In this case, write ves model for computing and pa is 0.41, 0.5, 0.47, and 0.35, respectively (i.e. Supu(p1)=0.41. naive Ba sterior probability can Tagl 国图 neighbor v Tags ----- Enriched Topics Target User I Fig. 2. Enriching topics of a target user from similar neighbors

est similarity are identified as positive neighbors and negative neigh￾bors such that: Npos k ðuÞ ¼ arg max k v2Unfug simpos u;v ; Nneg k ðuÞ ¼ arg max k v2Unfug simneg u;v ð6Þ 3.3. Enriching a user model Once we have identified the set of the nearest neighbors for a certain user u, his/her initial model IMu = hToRu, ToIui described in Section 3.1 is enriched from the neighbors. The basic idea of enriching the model starts from assuming that the user is likely to prefer similar tag patterns discovered within his/her neighbors. For example, if positive items of a user frequently contain tags ‘‘web2.0’’ and ‘‘semanticweb,’’ he/she may also be interested in topics, such as ‘‘web2.0,’’ ‘‘semanticweb,’’ and ‘‘ontology,’’ that fre￾quently appears in positive items of users similar to him/her. This enrichment process is particularly effective to some users who do not contain topics sufficiently in their user model. As illustrated in Fig. 2, we elaborate on the general idea of topic￾driven enrichments in the following example: Firstly, we choose neighbor user _ 2 Npos k ðuÞ in descending order of similarity be￾tween target user u and neighbors. For each topic pi in ToRu, specific topics of pi in ToRv are identified. Given two topics pi e ToRu and pj e ToRv, pi is said to a general topic of pj if and only if pi is a subset of pj, i.e., pi  pj. On the contrary, pj is called a specific topic of pi. For example, let p1 = {t1, t2} be a relevant topic of user u such that p1 e ToRu, and ToRv = {p2, p3, p4, p5} be the set of relevant topics of user v such that p2 = {t1, t2, t3}, p3 = {t1, t2, t4}, p4 = {t1, t2, t3, t5}, and p5 = {t3, t4}. Since topic p2, p3, and p4 contain the entire tags of topic p1, they are said to the specific topics of p1 whereas p5 is not the specific topic. In other words, p1 is said to the general topic of topics p2, p3, and p4. Several specific topics occurring in the mod￾el of neighbor v may be found. For efficient enrichment, we only consider specific topics that have a higher support than that of a general topic. For example, assume that the support for p1, p2, p3, and p4 is 0.41, 0.5, 0.47, and 0.35, respectively (i.e., Supu(p1) = 0.41, Supv(p2) = 0.5, Supv(p3) = 0.47, and Supv(p4) = 0.35). In this case, only topic p2 and p3 are used for enriching the model of user u if they are not included in the set ToRu. Topics such as p2 and p3 are called enriched topics for user u, and tags such as t3 e p2 and t4 e p3 are called enriched tags for user u. Finally, a set of enriched topics is identified from k positive neighbors of target user u. Note that some topics that were previ￾ously enriched by a certain neighbor v are also identified from an￾other neighbor h such that simpos u;v P simpos u;h , for v – h. If a particular topic is enriched many times from the neighbors, the target user is likely to be more interested in that topic. In an analogous fashion, with respect to irrelevant topics, a set of enriched topics can be determined from k negative neighbors Nneg k ðuÞ of user u. Formally, the enriched model, for a given user u, is defined as a tuple EMu = hEToRu, EToIui where EToRu is the set of relevant topics en￾riched from positive neighbors such that EToRu \ ToRu ¼ £, and EToIu is the set of irrelevant topics enriched from negative neigh￾bors such that EToIu \ ToIu ¼ £. For convenience, we also define any enriched tags occurring within either EToRu or EToIu as the sets: a set of enriched tags from positive neighbors ETpos u such that ETpos u \ ITpos u ¼ £, and a set of enriched tags from negative neighbors ETneg u such that ETneg u \ ITneg u ¼ £. Eventually, we represent user u with the initial model IMu and the enriched model EMu. We label the unified model the collaborative model for user u: CMu = hIMu, EMui. 4. Recommendation via probabilistic approach The final step is to generate recommendations such as a list of top-N items that a user would like the most. In our study, an item recommendation is treated as a classification problem that an item belongs to either a positive class Pos or a negative class Neg depending on a collaborative model CMu. To this end, we adopt locally weighted naïve Bayes (Frank, Hall, & Pfahringer, 2003) with the multinomial event model (McCallum & Nigam, 1998) to recommend top-N items stochastically. To apply the naïve Bayes classifier to the recommendation process of the target user u, for a given item i R Iu, tags annotated in item i such that Ti = tj e T|" : Qj,i = 1 are used as feature variables. More formally, naïve Bayes model for computing a posterior probability can be written as: Fig. 2. Enriching topics of a target user from similar neighbors. 8492 H.-N. Kim et al. / Expert Systems with Applications 38 (2011) 8488–8496