MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

MODULE 5
Advanced Data Mining Techniques
Web Mining | Text Mining

References: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)

PART A: WEB MINING

1. Introduction to Web Mining

Web Mining is the application of data mining techniques to discover patterns and knowledge from the
World Wide Web. It is classified into three major categories:

Category Data Source Goal

Web Content Mining Text, images, audio, video on Extract useful information from
web pages web page content
Web Structure Mining Hyperlinks between web pages Discover structure patterns from
hyperlinks
Web Usage Mining Web server logs, user sessions Understand user behavior and
navigation patterns

📌 Key Point: Web mining combines techniques from information retrieval, natural language
processing, and machine learning. (Han & Kamber, 2006)

2. Web Content Mining

Web Content Mining refers to the discovery of useful information from the content of Web documents
— text, images, video, audio, metadata — and structured records. (Dunham, 2003)

2.1 Key Concepts

• Data Sources: Web pages (HTML/XML), semi-structured/unstructured documents, multimedia
content
• Techniques Used: Natural Language Processing (NLP), Information Extraction, Classification,
Clustering
• Representation: Bag-of-words model, Vector Space Model (VSM)

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

2.2 Approaches to Web Content Mining

Agent-Based Approach
• Intelligent agents browse the web, gather and organize information
• Sub-types: Information agents, Learning agents, Filter agents

Database Approach
• Treats the Web as a loosely-structured database
• Aims to extract structured data from semi-structured web content
• Example: Wrapping and information extraction techniques

2.3 Information Extraction (IE) from Web

IE identifies and extracts predefined types of information from web content.
• Named Entity Recognition (NER): Extract names, dates, locations
• Wrapper Induction: Automate extraction from repetitive web page structures
• Schema Matching: Map web data to relational schema

📌 Key Point: Web content mining forms the backbone of search engine indexing and modern
recommendation systems.

3. Web Structure Mining

Web Structure Mining focuses on mining the graph structure of the hyperlinks of the Web. It uses the
link topology to derive useful knowledge about the importance and relationships of web pages. (Han &
Kamber, 2006)

3.1 PageRank Algorithm

Developed by Larry Page and Sergey Brin (Google founders), PageRank assigns a numerical weight to
each element of a hyperlinked set of documents to measure its relative importance.

Core Idea
• A page is important if many important pages link to it
• Based on the random surfer model: a user randomly follows hyperlinks
• PageRank is a probability distribution over all web pages

PageRank Formula

PR(A) = (1 - d) + d × Σ [ PR(Ti) / C(Ti) ]

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

Where:
PR(A) = PageRank of page A
d = Damping factor (typically 0.85)
T1...Tn = Pages that link to A
C(Ti) = Number of outgoing links from page Ti

Properties of PageRank
• Iterative computation: converges after sufficient iterations
• Dangling links: pages with no outlinks need special handling
• Rank sink problem: groups of pages with no outlinks can accumulate rank
• Damping factor d addresses the rank sink problem

3.2 HITS Algorithm (Hyperlink-Induced Topic Search)

Proposed by Jon Kleinberg, HITS is a link analysis algorithm used for ranking web pages. It identifies
two types of web pages:

Concept Definition Example

Hub A page with many links TO good A directory or portal page
authority pages
Authority A page with many links FROM A popular official resource
good hub pages

HITS Algorithm Steps

1. Submit query to a search engine; collect top-n results (root set)
2. Expand root set by adding pages that link to/from root set pages (base set)
3. Initialize hub and authority scores to 1 for each page
4. Iteratively update: Auth(p) = Σ Hub(q) for all q linking to p
5. Hub(p) = Σ Auth(q) for all q that p links to
6. Normalize scores and repeat until convergence

3.3 PageRank vs. HITS Comparison

Feature PageRank HITS
Query independence Query-independent (pre- Query-dependent (computed
computed) per query)
Scores Single rank score Two scores: Hub + Authority
Scope Entire Web graph Local subgraph per query
Speed Fast at query time Slower at query time
Stability More stable Topic drift possible

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

Used by Google Search Academic research, Teoma

📌 Key Point: HITS captures topic-specific relevance better than PageRank but is more
computationally expensive per query. (Pujari, 2008)

4. Web Usage Mining

Web Usage Mining is the process of extracting useful patterns from web log data representing user
navigation behavior. The goal is to understand user access patterns, personalize web services, and
improve site design. (Dunham, 2003)

4.1 Preprocessing in Web Usage Mining

Raw web server logs contain noise and must be cleaned and transformed before mining.

Step 1: Data Cleaning

• Remove irrelevant log entries (images, CSS, JS, failed requests with error codes)
• Filter out robot/crawler accesses using user-agent fields
• Remove duplicate log records

Step 2: User Identification

• Identify unique users from IP address + user-agent combinations
• Use cookies or login data for more accurate identification
• Challenges: NAT/proxy servers may share one IP among many users

Step 3: Session Identification

• Group page requests by user into sessions (single site visit)
• Timeout heuristic: if gap > 30 minutes, start a new session
• Navigation heuristic: backward navigation detection

Step 4: Path Completion

• Infer pages that were served from local cache (not in server log)
• Use site topology (site map) to fill in missing pages

4.2 Data Structures for Web Usage Mining

Structure Description Usage
User-Page Matrix Rows=Users, Cols=Pages, Collaborative filtering, clustering
Values=visit counts/time

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

Session-Transaction DB Each session as a set of pages Association rule mining

visited
Web Graph Pages as nodes, links as edges PageRank, HITS, path analysis
Click Stream Ordered sequence of user clicks Sequential pattern mining
with timestamps

4.3 Pattern Discovery in Web Usage Mining

Association Rule Mining
• Discover co-occurrence patterns: If user visits page A, they also visit page B
• Example: 80% of users who visit /products also visit /cart
• Algorithms: Apriori, FP-Growth applied to page-visit transactions

Sequential Pattern Mining

• Discover ordered sequences of page visits across time
• Example: Home → Products → Details → Cart → Checkout
• Algorithms: GSP (Generalized Sequential Patterns), PrefixSpan

Clustering in Web Usage Mining

• User Clustering: Group users with similar navigation behavior
• Page Clustering: Group pages frequently visited together
• Session Clustering: Identify common navigation sessions

Classification
• Predict user type (buyer/browser) based on navigation patterns
• Predict next page a user will visit
• Algorithms: Decision Trees, Neural Networks, Naive Bayes

4.4 Pattern Analysis

Pattern analysis involves filtering and interpreting discovered patterns to extract actionable knowledge.
• Statistical analysis: Support, confidence, lift for association rules
• Visualization: Cluster maps, sequence diagrams, navigation graphs
• Knowledge Query Mechanism (KQM): SQL-like querying of mined patterns
• Applications: Website restructuring, personalization, e-commerce recommendations

📌 Key Point: Web usage mining is the foundation of recommendation engines used by Amazon,
Netflix, and other e-commerce/media platforms. (Han & Kamber, 2006)

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

PART B: TEXT MINING

5. Introduction to Text Mining

Text Mining (also called Text Data Mining or Knowledge Discovery from Text) refers to the process of
extracting interesting and non-trivial patterns or knowledge from unstructured text documents.
(Dunham, 2003)

• Text documents are unstructured: no predefined schema

• Text data accounts for ~80% of enterprise information
• Combines: Information Retrieval (IR), NLP, Machine Learning, Statistics

5.1 Text Data vs. Structured Data

Aspect Structured Data Text Data
Format Tables with fixed schema Free-form prose, documents
Storage Relational databases Document repositories, web
Query SQL Keyword search, IR techniques
Mining Association, classification Topic modeling, text
classification
Ambiguity Low High (synonymy, polysemy)

6. Text Data Analysis and Information Retrieval

6.1 Document Representation

Bag of Words (BoW) Model
• Represent a document as a multiset of words, ignoring grammar and order
• Documents become vectors in a high-dimensional term space
• Term Frequency (TF): How often a word appears in a document

Term Frequency - Inverse Document Frequency (TF-IDF)

TF-IDF(t, d) = TF(t, d) × IDF(t)

TF(t, d) = (Count of term t in document d) / (Total terms in d)

IDF(t) = log [ N / df(t) ]
Where N = Total documents, df(t) = Documents containing term t

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining
Why TF-IDF?
• High TF-IDF: Term frequent in this document but rare across all documents → highly relevant
• Low TF-IDF: Term appears everywhere (stop words like 'the', 'is') → low relevance
• Balances term importance within a document against its commonality

6.2 Text Preprocessing Steps

7. Tokenization: Split text into individual tokens/words
8. Stop Word Removal: Remove common words (the, a, is, are)
9. Stemming: Reduce words to root form (running → run, cats → cat)
10. Lemmatization: Return dictionary base form (better → good)
11. POS Tagging: Assign Parts of Speech to each token
12. Feature Selection: Select most informative terms for the task

7. Basic Measures for Text Retrieval

Evaluation of text retrieval systems uses the following standard metrics. (Pujari, 2008)

Measure Formula Meaning

Recall TP / (TP + FN) Fraction of relevant docs
actually retrieved
Precision TP / (TP + FP) Fraction of retrieved docs that
are relevant
F-Measure 2PR / (P + R) Harmonic mean of Precision
and Recall
Accuracy (TP + TN) / Total Overall correctness of retrieval
Fallout FP / (FP + TN) Fraction of non-relevant docs
retrieved

7.1 Precision-Recall Tradeoff

• Increasing recall (retrieve more) often decreases precision
• The ideal system maximizes both: F1-Score balances them
• 11-point interpolated average precision: standard IR benchmark

📌 Key Point: In text retrieval, high recall is critical for legal or medical searches, while high precision
matters more for web search where many results exist.

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

8. Text Retrieval Methods

8.1 Boolean Retrieval Model

Documents are retrieved if they satisfy a Boolean expression of query terms.
• Query: 'Data AND Mining NOT Web'
• Pros: Simple, exact matching, easy to understand
• Cons: No ranking, no partial matching, poor for large collections

8.2 Vector Space Model (VSM)

Both documents and queries are represented as vectors in term space. Similarity is measured using
cosine similarity. (Han & Kamber, 2006)

Cosine Similarity(D, Q) = (D · Q) / (|D| × |Q|)

D = Document vector, Q = Query vector

Result range: 0 (no similarity) to 1 (identical)

• Advantages: Partial matching, ranked retrieval, handles synonymy better than Boolean
• Disadvantages: Ignores term order, polysemy problem, high dimensionality

8.3 Probabilistic Retrieval Model

• Estimates probability P(R|D,Q): probability document D is relevant given query Q
• Ranks documents by probability of relevance
• BM25 (Best Match 25): widely used probabilistic model in modern IR
• Requires prior relevance judgments for training

8.4 Language Models for IR

• Estimate probability that a query was generated by the document's language model
• Query likelihood model: P(Q | MD) — rank by probability of query given document model
• Smoothing techniques: Laplace, Jelinek-Mercer, Dirichlet

Model Key Idea Strength Weakness

Boolean Exact term matching Simple, deterministic No ranking
Vector Space Cosine similarity with Ranked, partial match No semantics
TF-IDF
Probabilistic Probability of relevance Theoretically sound Needs relevance data
Language Model Query generation Principled, flexible Computationally heavy
probability

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

9. Text Indexing Techniques

Indexing is the process of building data structures to enable fast text retrieval from large document
collections. (Dunham, 2003)

9.1 Inverted Index

The most common and fundamental indexing structure in information retrieval.

• Structure: For each term, store a list of documents containing that term (posting list)
• Components: Vocabulary (dictionary) + Posting lists
• Each posting entry: document ID, term frequency, position list

Term (Dictionary) Posting List (DocID: Frequency)

data → Doc1:3, Doc2:1, Doc5:2
mining → Doc1:2, Doc3:4, Doc4:1

9.2 Signature Files

• Each document is represented by a bit-signature derived from its words
• Bitwise OR of term signatures forms document signature
• Query matching: query signature AND doc signature = query signature (potential match)
• Pros: Compact storage; Cons: False positives possible

9.3 Suffix Arrays and Suffix Trees

• Suffix Array: Sorted array of all suffixes of a document collection
• Allows fast substring and phrase searches
• Suffix Tree: Compressed trie of all suffixes — O(n) construction, O(m) pattern search
• Used in: DNA sequence search, plagiarism detection, phrase indexing

9.4 Latent Semantic Indexing (LSI)

LSI addresses the vocabulary mismatch problem (synonymy and polysemy) using Singular Value
Decomposition (SVD).

• Represents documents and terms in a lower-dimensional latent semantic space

• Documents about similar topics cluster together even without shared words
• Query expansion automatically includes semantically related terms

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining
• Limitation: Computationally expensive for very large corpora

📌 Key Point: LSI is the predecessor to modern neural word embeddings (Word2Vec, BERT). It
captures semantic relationships between terms. (Han & Kamber, 2006)

9.5 Comparison of Indexing Techniques

Index Type Best For Space Speed
Inverted Index General text retrieval Medium Very Fast
(most common)
Signature Files Large doc collections, Low Fast (FP risk)
approximate search
Suffix Array/Tree Substring/phrase High Very Fast
queries
LSI / SVD Semantic / concept- Medium Moderate
based search

10. Query Processing Techniques

Query processing transforms a user's query into a result set. It involves query parsing, expansion,
reformulation, and final ranking. (Pujari, 2008)

10.1 Query Types

• Keyword Query: Simple list of terms (most common in web search)
• Phrase Query: Exact phrase match using quotation marks ("data mining")
• Boolean Query: Uses AND, OR, NOT operators
• Proximity Query: Terms within a specified distance of each other
• Wildcard/Fuzzy Query: Pattern matching (data min*)

10.2 Query Parsing and Normalization

13. Tokenization of query string
14. Case folding (convert to lowercase)
15. Stop word removal
16. Stemming or lemmatization
17. Phrase detection and identification

10.3 Query Expansion

Query expansion adds additional terms to the original query to improve recall.

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

Methods of Query Expansion

• Relevance Feedback (Rocchio Algorithm): User marks relevant/non-relevant results; system
expands query toward relevant docs
• Pseudo Relevance Feedback: Top-k retrieved docs assumed relevant; terms from them used
to expand query
• Thesaurus-Based Expansion: Synonyms from WordNet or domain thesaurus added to query
• Statistical Co-occurrence: Terms frequently co-occurring with query terms are added

Rocchio Algorithm Formula

Q_new = α·Q_old + β·(1/|Dr|)·Σ Dr − γ·(1/|Dnr|)·Σ Dnr

α = Weight of original query | β = Weight of relevant docs | γ = Weight of non-relevant docs

10.4 Query Optimization

• Reorder query term evaluation to minimize cost (process rarest terms first)
• Skip pointers: Speed up posting list intersection
• Index compression: Reduce I/O cost during retrieval
• Caching: Cache results of frequent queries
• Tiered indexes: Search high-quality tier first, extend if needed

10.5 Ranking and Scoring

Retrieved documents must be ranked by relevance score for the user.

• Score = Σ TF-IDF(t, d) × IDF(t) for each query term t

• Zone scoring: Different document fields (title, body, URL) weighted differently
• BM25 scoring: State-of-the-art probabilistic ranking function
• Learning to Rank (LTR): Machine learning models trained on relevance judgments

10.6 Complete Query Processing Pipeline

# Stage Description
1 Query Input User types natural language or keyword query
2 Query Parsing Tokenize, normalize, identify phrases and operators
3 Query Expansion Add synonyms, related terms via thesaurus or feedback
4 Index Lookup Search inverted index for relevant posting lists
5 Candidate Retrieval Intersect/union posting lists per Boolean/VSM logic

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)
MODULE 5 — Advanced Data Mining Techniques | Web Mining & Text Mining

6 Scoring & Ranking Apply TF-IDF / BM25 / learning-to-rank model

7 Result Presentation Return top-k results with snippets/summaries

QUICK REVISION SUMMARY

Topic Key Algorithms / Concepts Key Formula / Model

Web Content Mining NER, Wrapper Induction, IE BoW, TF-IDF, VSM
Web Structure Mining PageRank, HITS PR(A) = (1-d) +
d·Σ[PR(Ti)/C(Ti)]
Web Usage Mining Apriori, GSP, K-Means Session identification, click
streams
Text Retrieval Boolean, VSM, Probabilistic Cosine Similarity, BM25
Text Indexing Inverted Index, LSI, Suffix Trees SVD for LSI
Query Processing Rocchio, Query Expansion Q_new = α·Q + β·Dr − γ·Dnr
Evaluation Precision, Recall, F-Measure F = 2PR/(P+R)

REFERENCES

18. Dunham M H. "Data Mining: Introductory and Advanced Topics", Pearson Education, New
Delhi, 2003.
19. Arun K Pujari, "Data Mining Techniques", Universities Press Private Limited, 2008.
20. Jaiwei Han and Micheline Kamber, "Data Mining: Concepts and Techniques", Elsevier, 2006.

— End of Module 5 Notes —

Data Mining — Study Notes | Ref: Dunham (2003) • Pujari (2008) • Han & Kamber (2006)