Create Presentation
Download Presentation

Download Presentation
## 4 Exploiting Click Streams and Query Logs

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**4 Exploiting Click Streams and Query Logs**4.1 Motivation 4.2 Exploiting Click Streams 4.3 Clustering Query Logs 4.4 Exploiting Query Logs for Query Expansion Selected Topics in Web IR and Mining**query logs, bookmarks, etc. provide**• human assessments & endorsements • correlations among words & concepts • and among documents Problem: Exploit Collective Human Input for Collaborative Web Search - Beyond Relevance Feedback and Beyond Google - • href links are human endorsements PageRank, etc. • Opportunity: online analysis of human input & behavior • may compensate deficiencies of search engine Typical scenario for 3-keyword user query: a & b & c top 10 results: user clicks on ranks 2, 5, 7 top 10 results: user modifies query into a & b & c & d user modifies query into a & b & e user modifies query into a & b & NOT c top 10 results: user selects URL from bookmarks user jumps to portal user asks friend for tips Challenge: How can we use knowledge about the collective input of all users in a large community? Selected Topics in Web IR and Mining**DB schemas, instances &**• data usage in apps provide • human annotations • correlations among tables, attr‘s, etc. Problem 2: Exploit Collective Human Input for Automated Data(base Schema) Integration • „semantic“ data integration is hoping for ontologies • Opportunity: all existing DBs & apps already provide • a large set of subjective mini-ontologies Typical scenario for analyzing if A and B mean the same entity compare their attributes, relationships, etc. • consider attributes and relationships of all similar tables/docs in all known DBs • consider instances of A and B in comparison to instances of similar tables/docs in all known DBs • compare usage patterns of A and B in queries & apps in comparison to similar tables/docs of all known DBs Challenge: How can we use knowledge about the collective designs of all DB apps in a large community? Selected Topics in Web IR and Mining**4.2 Exploiting Click Streams**Simple idea: Modify HITS or Page-Rank algorithm by weighting edges with the relative frequency of users clicking on a link (as observed by DirectHit) More sophisticated approach (Chen et al.:2002): Consider link graph A and link-visit matrix V (Vij=1 if user i visits page j, 0 else) Define authority score vector: a = ATh + (1- )VTu hub score vector: h = Aa + (1- )VTu user importance vector: u = (1- )V(a+h) with a tunable parameter (=1: HITS, =0: DirectHit) claims to achieve higher precision than HITS, according to experimental results (with =0.6) for some Webqueries such as „daily news“: HITS top results: pricegrabber, gamespy, fileplanet, sportplanet, etc. Chen et al. method: news.com, bbc, cnn, google, lycos, etc. Selected Topics in Web IR and Mining**Link Analysis based on Implicit Links (1)**Apply simple data mining to browsing sessions of many users, where each session i is a sequence (pi1, pi2, ...) of visited pages: consider all pairs (pij, pij+1) of successively visited pages, compute their total frequency f, and selected those with f above some min-support threshold Construct implicit-link graph with the selected page pairs as edges and their normalized total frequencies f as edge weights. Apply edge-weighted Page-Rank for authority scoring, and linear combination of relevance and authority for overall scoring. Selected Topics in Web IR and Mining**not clear to me**if any method is really better Link Analysis based on Implicit Links (2) Experimental results (Xue et al.:2003): performed on 4-month server-side (UC Berkeley) click-stream log with some „data cleaning“: 300 000 sessions of 60 000 users visiting 170 000 pages with 200 000 explicit links 2-item frequent itemset mining yields 336 812 implicit links (incl. 22 122 explicit links) Results for query „vision“: implicit PR explicit PR weighted HITS DirectHit • vision group some paper Forsyth‘s book workshop on vision • Forsysth‘s book vision group vision group some student‘s resume • book 3rd edition student resume book 3rd edition special course • workshop on vision some talk slides Leung‘s publ. Forsyth‘s book • ... Selected Topics in Web IR and Mining**4.3 Clustering Query Logs**• Motivation: • statistically identify FAQs (for intranets and portals), • taking into account variations in query formulation • capture correlation between queries and subsequent clicks Model/Notation: a user session is a pair (q, D+) with a query q and D+ denoting the result docs on which the user clicked; len(q) is the number of keywords in q Selected Topics in Web IR and Mining**Similarity Measures between User Sessions**• tf*idf based similarity between query keywords only • edit distance based similarity: sim(p,q) = 1 – ed(p,q) / max(len(p),len(q)) Examples: Where does silk come from? Where does dew come from? How far away is the moon? How far away is the nearest star? • similarity based on common clicks: Example: atomic bomb, Manhattan project, Nagasaki, Hiroshima, nuclear weapon • similarity based on common clicks and document hierarchy: p=law of thermodynamics D+p = {/Science/Physics/Conservation Laws, ...} q=Newton law D+q = {/Science/Physics/Gravitation, ...} with • linear combinations of different similarity measures Selected Topics in Web IR and Mining**Digression: K-Means Clustering Method**• Idea: • determine k prototype vectors, one for each cluster • assign each data record to the most similar prototype vector • and compute new prototype vector • (e.g. by averaging over the vectors assigned to a prototype) • iterate until clusters are sufficiently stable randomly choose k prototype vectors while not yet sufficiently stable do for i:=1 to n do assign di to cluster cj for which is maximal od; for j:=1 to k do od; od; Selected Topics in Web IR and Mining**K-Means Clustering Method**• run-time is O(n) (assuming constant number of iterations) • a suitable number of clusters, k, can be determined experimentally • or based on the MDL principle or heuristic purity measures • the initial prototype vectors could be chosen by using another • – very efficient – clustering method • (e.g. bottom-up clustering on random sample of the data records). • for sim / dist any arbitrary metric can be used Selected Topics in Web IR and Mining**Example for K-Means Clustering**K=2 data records prototype vectors a b a b 5 5 c c 4 4 3 3 d d 2 2 e f e f 1 1 1 2 3 4 5 6 8 1 2 3 4 5 6 8 7 7 after 1st iteration after 2nd iteration Selected Topics in Web IR and Mining**Incremental DBSCAN Clustering Method**based on M. Ester et al.: A density-based algorithm for discovering clusters in large spatial databases with noise, KDD Conference, 1996 simplified version of the algorithm: for each data point d do { insert d into spatial index (e.g., R-tree); locate all points with distance to d < max_dist; if these points form a single cluster then add d to this cluster else { if there are at least min_points data points that do not yet belong to a cluster such that for all point pairs the distance < max_dist then construct a new cluster with these points }; }; average run-time is O(n * log n); data points that are added later can be easily assigned to a cluster; points that do not belong to any cluster are considered „noise“ Selected Topics in Web IR and Mining**Experimental Studies**performed on 20 000 queries against MS Encarta (an encyclopedia) • Observations: • with sim threshold 1.0 the total number of clusters • for the most popular 4500 queries (22%) • was 400 for keyword sim and 200 for common-click sim • combined keyword + common-click sim achieved best precision • with sim threshold 0.6 the precision was above 90% • (as intellectually assessed by „volunteers“) Selected Topics in Web IR and Mining**4.4 Exploiting Query Logs for Query Expansion**Given: user sessions of the form (q, D+), and let „dD+“ denote the event that d is clicked on We are interested in the correlation between words w in a query and w‘ in a clicked-on document: Estimate from query log: relative frequency of w‘ in d relative frequency of d being clicked on when w appears in query Expand query by adding top m words w‘ in desc. order of Selected Topics in Web IR and Mining**Simple Alternative: Local Context Analysisbased on**Pseudo-Relevance Feedback based on J. Xu and W.B. Croft: Improving the Effectiveness of Information Retrieval with Local Context Analysis, ACM TOIS Vol.18 No.1, 2000 Evaluate query q and extract from top k results: select top m words or noun phrases according to some tf*idf-style measure Expand q by adding the selected words or noun phrases (possibly with specific weights) Selected Topics in Web IR and Mining**on MS Encarta corpus,**with 4 Mio. query log entries and 40 000 doc. subset Experimental Evaluation Considers short queries and long phrase queries, e.g.: Michael Jordan Michael Jordan in NBA matches genome project Why is the genome project so crucial for humans? Manhattan project What is the result of Manhattan project on Word War II? Windows What are the features of Windows that Microsoft brings us? (Phrases are decomposed into N-grams that are in dictionary) Avg. precision [%] at different recall values: Short queries: Long queries: Recall q alone LC Query Log (n=100,m=30) (m=40) 10% 40.67 45.00 62.33 20% 27.00 32.67 44.33 30% 20.89 26.44 36.78 100% 8.03 13.13 17.07 Recall q alone LC Query Log (n=100,m=30) (m=40) 10% 46.67 41.67 57.67 20% 31.17 34.00 42.17 30% 25.67 27.11 34.89 100% 11.37 13.53 16.83 Selected Topics in Web IR and Mining**given:**a set of items I = {x1, ..., xm} a set D ={t1, ..., tn} of item sets (transactions) ti = {xi1, ..., xik} I Digression: Association Rules • wanted: • rules of the form X Y with X I and Y I such that • X is sufficiently often a subset of the item sets ti and • when X ti then most frequently Y ti holds, too. support (X Y) = P[XY] = relative frequency of item sets that contain X and Y confidence (X Y) = P[Y|X] = relative frequency of item sets that contain Y provided they contain X support is usually chosen in the range of 0.1 to 1 percent, confidence (aka. strength) in the range of 90 percent or higher Selected Topics in Web IR and Mining**Association Rules: Example**Market basket data („sales transactions“): t1 = {Bread, Coffee, Wine} t2 = {Coffee, Milk} t3 = {Coffee, Jelly} t4 = {Bread, Coffee, Milk} t5 = {Bread, Jelly} t6 = {Coffee, Jelly} t7 = {Bread, Jelly} t8 = {Bread, Coffee, Jelly, Wine} t9 = {Bread, Coffee, Jelly} support (Bread Jelly) = 4/9 support (Coffee Milk) = 2/9 support (Bread, Coffee Jelly) = 2/9 confidence (Bread Jelly) = 4/6 confidence (Coffee Milk) = 2/7 confidence (Bread, Coffee Jelly) = 2/4 Selected Topics in Web IR and Mining**Apriori Algorithm: Idea and Outline**• Idea and outline: • proceed in phases i=1, 2, ..., each making a single pass over D, • and generate rules X Y • with frequent item set X (sufficient support) and |X|=i in phase i; • use phase i-1 results to limit work in phase i: • antimonotonicity property (downward closedness): • for i-item-set X to be frequent, • each subset X‘ X with |X‘|=i-1 must be frequent, too • generate rules from frequent item sets; • test confidence of rules in final pass over D Worst-case time complexity is exponential in I and linear in D*I, but usual behavior is linear in D (detailed average-case analysis is very difficult) Selected Topics in Web IR and Mining**Apriori Algorithm: Pseudocode**procedure apriori (D, min-support): L1 = frequent 1-itemsets(D); for (k=2; Lk-1 ; k++) { Ck = apriori-gen (Lk-1, min-support); for each t D { // linear scan of D Ct = subsets of t that are in Ck; for each candidate c Ct {c.count++}; }; Lk = {c Ck | c.count min-support}; }; return L = k Lk; // returns all frequent item sets procedure apriori-gen (Lk-1, min-support): Ck = : for each itemset x1 Lk-1 { for each itemset x2 Lk-1 { if x1 and x2 have k-2 items in common and differ in 1 item // join { x = x1 x2; if there is a subset s x with s Lk-1 {disregard x;} // infreq. subset else add x to Ck; }; }; }; return Ck Selected Topics in Web IR and Mining**Algorithmic Extensions and Improvements**• hash-based counting (computed during very first pass): • map k-itemset candidates (e.g. for k=2) into hash table and • maintain one count per cell; drop candidates with low count early • remove transactions that don‘t contain frequent k-itemset • for phases k+1, ... • partition transactions D: • an itemset is frequent only if it is frequent in at least one partition • exploit parallelism for scanning D • randomized (approximative) algorithms: • find all frequent itemsets with high probability (using hashing etc.) • sampling on a randomly chosen subset of D • ... • mostly concerned about reducing disk I/O cost • (for TByte databases of large wholesalers or phone companies) Selected Topics in Web IR and Mining**quantified rules: consider quantitative attributes of item**in transactions • (e.g. wine between $20 and $50 cigars, or • age between 30 and 50 married, etc.) • constrained rules: consider constraints other than count thresholds, • e.g. count itemsets only if average or variance of price exceeds ... • generalized aggregation rules: rules referring to aggr. functions other • than count, e.g., sum(X.price) avg(Y.age) • multilevel association rules: considering item classes • (e.g. chips, peanuts, bretzels, etc. belonging to class snacks) • sequential patterns • (e.g. an itemset is a customer who purchases books in some order, • or a tourist visiting cities and places) • from strong rules to interesting rules: • consider also lift (aka. interest) of rule X Y: P[XY] / P[X]P[Y] • correlation rules • causal rules Extensions and Generalizations of Assocation Rules Selected Topics in Web IR and Mining**example for strong, but misleading association rule:**tea coffee with confidence 80% and support 20% but support of coffee alone is 90%, and of tea alone it is 25% tea and coffee have negative correlation ! Correlation Rules consider contingency table (assume n=100 transactions): T T C 20 70 90 {T, C} is a frequent and correlated item set C 5 5 10 25 75 correlation rules are monotone (upward closed): if the set X is correlated then every superset X‘ X is correlated, too. Selected Topics in Web IR and Mining**procedure corrset (D, min-support, support-fraction,**significance-level): for each x I compute count O(x); initialize candidates := ; significant := ; for each item pair x, y I with O(x) > min-support and O(y) > min-support { add (x,y) to candidates; }; while (candidates ) { notsignificant := ; for each itemset X candidates { construct contingency table T; if (percentage of cells in T with count > min-support is at least support-fraction) { // otherwise too few data for chi-square if (chi-square value for T significance-level) {add X to significant} else {add X to notsignificant}; }; //if }; //for candidates := itemsets with cardinality k such that every subset of cardinality k-1 is in notsignificant; // only interested in correlated itemsets of min. cardinality }; //while return significant Correlated Item Set Algorithm Selected Topics in Web IR and Mining**Frequent Itemset and Correlated ItemsetsApplied to Query**Logs Infer from user sessions of the form (q, D+) where q is a set of words association rules of the form: w1 and w2 => w3 Infer from user sessions of the form (q, D+) where q is a set of „signed“ (positive or negative) words correlation rules of the form: sign1 w1 and sign2 w2 => sign3 w3 where signi is either + or and indicates positive or negative correlation Expand new query with word set W by right-hand sides r of association rules L => r for which L W Selected Topics in Web IR and Mining**Literature**• Zheng Chen, Li Tao, Jidong Wang, Liu Wenyin, Wei-Ying Ma: • A Unified Framework for Web Link Analysis, WISE Conf., 2002 • Gui-Rong Xue, Hua-Jun Zeng, Zheng Chen, Wei-Ying Ma, • Hong-Jiang Zhang, Chao-Jun Lu: Implicit Link Analysis for • Small Web Search, SIGIR Conf., 2003 • Ji-Rong Wen, Jian-Yun Nie, Hong-Jiang Zhang: Query Clustering • Using User Logs, ACM TOIS Vol.20 No.1, 2002 • Hang Cui, Ji-Rong Wen, Jian-Yun Nie, Wei-Ying Ma: • Query Expansion by Mining User Logs, IEEE • Transactions on Knowledge and Data Engineering Vol.15 No.4, 2003 Selected Topics in Web IR and Mining