Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Web mining and recommender systems

Web mining (content, structure, usage) finds patterns from the Web; recommender systems (content-based, collaborative, matrix factorization) predict items users will like and are evaluated by accuracy and ranking metrics.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Websites, e-commerce portals and social platforms use web mining to extract useful information from pages, links and user logs. Recommender systems use those mined signals to suggest products, movies or pages — engineers build and tune them to increase engagement and sales.

Key ideas

Start with definitions.

  • Web mining: the process of discovering useful information from the Web. It includes three subfields: web content mining, web structure mining, and web usage mining.

    • Web content mining finds information from page text, images and metadata (for example, extracting keywords, topics, or product attributes).
    • Web structure mining analyses the hyperlink graph of pages (pages as nodes, hyperlinks as directed edges) to compute link-based importance (for example, PageRank).
    • Web usage mining analyses user activity logs (server logs, clickstreams) to discover navigation patterns and sessions.
  • Recommender system: a system that predicts and ranks items a user would prefer, using user-item data and item features.

    • Content-based recommendation: match user profile (features from items the user liked) with item features; works well when item metadata exists.
    • Collaborative filtering (CF): uses patterns of user-item ratings or interactions. Two main types: user-based CF (users similar to you) and item-based CF (items similar to those you liked).
    • Matrix factorization: model the rating matrix R as product of low-rank matrices (R ≈ P·Q^T); learns latent user/item factors.
    • Hybrid recommendation: combine content-based and collaborative filtering (e.g., linear blends or model-based hybrids) to mitigate cold start and sparsity.
  • Important practical problems and terms:

    • Cold start: new user or new item has no history — hard to recommend.
    • Sparsity: rating matrices are mostly empty; affects CF performance.
    • Popularity bias: popular items get recommended more, reducing diversity.
    • Offline vs online evaluation: offline uses historical splits (prefer time-based splits for temporal/implicit data to avoid leakage); online uses A/B tests.
  • Web-structure basics and PageRank derivation (what to draw and label):

    • Draw three nodes labeled A, B, C. Draw directed arrows for hyperlinks: A→B, A→C, B→C, C→A (as in the worked example). Label each arrow with the link direction.
    • Define the stochastic link matrix P where P_{i,j} is the probability to go from page j to page i (column-stochastic). PageRank r satisfies r = d·P·r + (1−d)/N · 1, where d is the damping factor and N is number of pages. This is the stationary distribution of a random surfer who follows links with probability d and jumps uniformly with probability 1−d. Handle dangling nodes (pages with no outlinks) by replacing their column in P with 1/N so P remains column-stochastic.
  • Collaborative filtering formulas (concepts, assumptions):

    • Cosine similarity assumes vectors represent preferences and uses angle between them.
    • Pearson correlation centers by user mean and captures linear relation of rating deviations.
    • Prediction in neighbourhood CF is a weighted average of neighbor ratings (simple weighted or mean-centered).
  • Matrix factorization formulation: minimize regularized squared error over known ratings. Standard objective and gradient-descent updates are often asked to be derived. Often augmented with bias terms: r̂_{u,i} = μ + b_u + b_i + p_u·q_i^T.

Formulas

cosine(u,v) = (Σ_i r_{u,i}·r_{v,i}) / (sqrt(Σ_i r_{u,i}^2) · sqrt(Σ_i r_{v,i}^2)) — r_{u,i} is rating of user u on item i; unitless; applies when comparing two rating vectors over commonly rated items.

pearson(u,v) = (Σ_i (r_{u,i}-μ_u)·(r_{v,i}-μ_v)) / (sqrt(Σ_i (r_{u,i}-μ_u)^2) · sqrt(Σ_i (r_{v,i}-μ_v)^2)) — μ_u is mean rating of user u over common items; unitless; applies when centering is desired.

pred_weighted(u,i) = Σ_{v∈N(u)} s(u,v)·r_{v,i} / Σ_{v∈N(u)} |s(u,v)| — predicted rating by weighted average; r_{v,i} in rating scale (e.g., 1–5); applies in neighbourhood CF.

pred_centered(u,i) = μ_u + (Σ_{v∈N(u)} s(u,v)·(r_{v,i}-μ_v)) / Σ_{v∈N(u)} |s(u,v)| — mean-centered prediction; μ_u, μ_v are user means.

PageRank: r = d·P·r + (1−d)/N · 1 — r is N×1 PageRank vector summing to 1; d is damping factor (commonly 0.85); P is column-stochastic link matrix; applies for link-based importance.

Matrix factorization loss: L = Σ_{(u,i)∈K} (r_{u,i} - p_u·q_i^T)^2 + λ (Σ_u ||p_u||^2 + Σ_i ||q_i||^2) — where p_u and q_i are k-dim user/item factors; λ is regularization; K is set of observed ratings; units match rating scale.

RMSE = sqrt( (1/n) Σ (r_true - r_pred)^2 ) — error in rating units; lower is better.

MAE = (1/n) Σ |r_true - r_pred| — mean absolute error; rating units.

Precision@k = (relevant recommended items among top k) / k — unitless fraction; used for top-k evaluation.

Recall@k = (relevant recommended items among top k) / (total relevant items for user) — unitless fraction.

NDCG@k = DCG@k / IDCG@k with DCG@k = Σ_{i=1..k} (2^{rel_i}-1) / log2(i+1) — rel_i is graded relevance of i-th recommended item; NDCG is normalized to [0,1].

Worked examples

  1. PageRank small graph (numerical, step-by-step)
  • Graph: pages A, B, C with links A→B, A→C, B→C, C→A.
  • Out-degrees: out(A)=2, out(B)=1, out(C)=1. Set damping d=0.85, N=3.
  • Build column-stochastic P: column for A = [0, 1/2, 1/2]^T (probability to A,B,C from A); column for B = [0,0,1]^T; column for C = [1,0,0]^T. So P = [[0, 0, 1], [1/2, 0, 0], [1/2, 1, 0]].
  • Start r0 = [1/3,1/3,1/3]^T. Compute P·r0 = [1/3, 1/6, 1/2]^T approximately [0.3333, 0.1667, 0.5].
  • Apply PageRank formula: r1 = 0.85·P·r0 + 0.15/3·1 = 0.85·[0.3333,0.1667,0.5] + [0.05,0.05,0.05] = [0.3333,0.1917,0.4750].
  • After convergence (more iterations) page C has highest rank, then A, then B. (This single iteration already shows C becoming largest.)
  1. User-based collaborative filtering (trace)
  • Ratings table (rows users U1,U2,U3; columns I1,I2,I3): U1: 5,3,?
    U2: 4,2,1 U3: 1,5,4
  • We predict U1's rating for I3 using cosine similarity and simple weighted average.
  • Common rated items between U1 and U2 are I1,I2: vectors [5,3] and [4,2]. Cosine ≈ (20+6)/(sqrt(34)*sqrt(20)) ≈ 26/26.0768 ≈ 0.9971.
  • Between U1 and U3: [5,3] and [1,5] → cosine ≈ 20/(sqrt(34)*sqrt(26)) ≈ 20/29.732 ≈ 0.6727.
  • Neighbor ratings for I3: U2 gives 1, U3 gives 4.
  • Weighted prediction: (0.9971·1 + 0.6727·4) / (0.9971+0.6727) = (0.9971 + 2.6908) / 1.6698 = 3.6879 / 1.6698 ≈ 2.21.
  • So predicted rating for U1 on I3 ≈ 2.21 (on the same rating scale).
  • Note: using mean-centred Pearson would shift predictions and often give better results; this example uses simple cosine-weighted average for clarity.

Common mistakes

  • Confusing row-stochastic vs column-stochastic matrices in PageRank; remember P_{i,j} is prob from j→i in the standard column formulation.
  • Not normalizing similarities when summing weights (forget denominator Σ|s|).
  • Treating missing ratings as zeros in similarity or mean calculations — this biases results.
  • For matrix factorization, omitting the regularization term λ leads to overfitting; omitting bias terms (global/user/item) reduces accuracy.

For your exam

Kinds of questions:

  • Definitions and short notes: define web content/structure/usage mining; define collaborative filtering, cold start.
  • Derivations: derive the PageRank stationary equation from random-surfer model; show gradient updates for matrix factorization.
  • Numericals: compute PageRank on a tiny graph; compute similarity and a CF prediction on a small rating matrix.
  • Programs/pseudocode: write simple pseudocode for k-nearest-neighbour CF or power iteration for PageRank.
  • Diagrams: draw a small web graph and label links and out-degrees; show the transition matrix.

What full-marks answers include:

  • Precise definitions of bolded terms with assumptions stated (for example, for Pearson say you assume meaningful user mean); clear steps in derivations with algebra; for numericals, show each arithmetic step, units (rating scale), and final answer bolded.

Quick check

  1. Name the three subfields of web mining.
  2. In PageRank, what is the role of the damping factor d?
  3. When should you use Pearson correlation instead of cosine similarity in CF?

Answers: 1) Web content mining, web structure mining, web usage mining. 2) d is the probability the random surfer follows links (controls teleport probability 1−d and ensures uniqueness/convergence). 3) Use Pearson when you must account for differences in user rating scales (center by user mean).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?