New version page

Leveraging Collaborative Tagging for Web Item Design

This preview shows page 1-2-3 out of 9 pages.

View Full Document
View Full Document

End of preview. Want to read all 9 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

Leveraging Collaborative Tagging for Web Item DesignMahashweta Das, Gautam Das∗Department of Computer Science & EngineeringUniversity of Texas at [email protected], [email protected] Hristidis†School of Computing & Information SciencesFlorida International [email protected]fiu.eduABSTRACTThe popularity of collaborative tagging sites has created newchallenges and opportunities for designers of web items, suchas electronics products, travel itineraries, popular blogs, etc.An increasing number of people are turning to online re-views and user-specified tags to choose from among com-peting items. This creates an opportunity for designers tobuild items that are likely to attract desirable tags whenpublished. In this paper, we consider a novel optimizationproblem: given a training dataset of existing items with theiruser-submitted tags, and a query set of desirable tags, de-sign the k best new items expected to attract the maximumnumber of desirable tags. We show that this problem is NP-Complete, even if simple Naive Bayes Classifiers are usedfor tag prediction. We present two principled algorithmsfor solving this problem: (a) an exact “two-tier” algorithm(based on top-k querying techniques), which performs muchbetter than the naive brute-force algorithm and works wellfor moderate problem instances, and (b) a novel polynomial-time approximation algorithm with provable error bound forlarger problem instances. We conduct detailed experimentson synthetic and real data crawled from the web to evaluatethe efficiency and quality of our proposed algorithms.Categories and Subject DescriptorsH.4 [Information Systems Applications]: MiscellaneousGeneral TermsAlgorithms, PerformanceKeywordscollaborative tagging, item design, naive bayes, optimization∗Partially supported by NSF grants 0812601, 0915834,1018865, a NHARP grant from the Texas Higher EducationCoordinating Board, and grants from Microsoft Researchand Nokia Research.†Partially supported by NSF grants IIS-0811922, IIS-0952347, HRD-0833093 and Google Research Award.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.KDD’11, August 21–24, 2011, San Diego, California, USA.Copyright 2011 ACM 978-1-4503-0813-7/11/08 ...$10.00.1. INTRODUCTIONMotivation: The widespread use and popularity of onlinecollaborative tagging sites has created new challenges andopportunities for designers of “web items” such as electron-ics products, travel itineraries, popular blogs, etc. Variouswebsites today (e.g., Flickr for photos, YouTube for videos,Amazon for different products) encourage users to activelyparticipate by assigning labels or “tags” to online resourceswith a purpose to promote their contents and allow users toshare, discover and organize them. An increasing numberof people are turning to online reviews and user-specifiedtags to choose from among competing items. For example,a cell phone that has been tagged lightweight by severalusers is likely to influence a prospective customer decisionin its favor. This creates an opportunity for designers tobuild items that are likely to attract desirable tags whenpublished. In addition to traditional marketplaces like elec-tronics, autos or apparel, tag desirability also extends toother diverse domains. For example, music websites such asLast.fm use social tags to guide their listeners in browsingthrough artists and music. An artist creating a new musicalpiece can leverage the tags that users have selected, in or-der to select the piece’s attributes (e.g. acoustic and audiofeatures) that will increase its chances of becoming popular.Similarly, a blogger can select a topic based on the tags thatother popular topics have received.Our paper investigates this novel tag maximization prob-lem, i.e., how to decide the attribute values of new itemsand to return the top-k “best” items that are likely to at-tract the maximum number of desirable tags. We providemore details as follows.Tag Maximization Problem: Assume we are given a setof items, each having a set of attributes and a set of user-submitted tags (e.g., cell phones on Amazon’s website, eachdescribed by a set of attributes, and associated user tags).From this training data, for each distinct tag, we assume aclassifier has been constructed for predicting the tag giventhe attributes. Tag prediction is a recent area of research(see Section 6 for discussion of related work), and the exis-tence of such classifiers is a key assumption in our work. Inaddition to the item’s explicitly specified attributes, otherimplicit factors also influence tagging behavior, such as theperceived utility and quality of an item to the user, thetagging behavior of the user’s friends, etc. However, pure“content-based” tag prediction approaches are often quiteeffective − e.g., in the context of laptops, attributes such assmaller dimensions and the absence of a built-in DVD drivemay attract tags such as portable.538Given a query consisting of a subset of tags that are con-sidered “desirable”, our task is to suggest a new item (i.e.,a combination of attribute values) such that the expectednumber of desirable tags for this potential item is maxi-mized. This can be extended to the top-k version, wherethe task is to suggest the k potential items with the highestexpected number of desirable tags.This information can assist web item designers in design-ing new items (or fine-tuning existing web content) to makethem more attractive to users. Moreover, designers can ex-plore the dataset in an interactive manner by picking andchoosing different sets of desirable tags to get insight on howto build new items that target different user populations −e.g., in the context of cell phones, tags such as lightweightand powerful target professionals, whereas tags such ascheap, cool target younger users.No velty, Technical Challenges and Approaches: Thedynamics of social tagging has been an active research areain recent years. However related literature primarily focuseson the problems of tag prediction, including cold-start rec-ommendation to facilitate web-based activities.


Loading Unlocking...
Login

Join to view Leveraging Collaborative Tagging for Web Item Design and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Leveraging Collaborative Tagging for Web Item Design and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?