Information Retrieval (AD-603 (C)) Unit 5 Notes

How unit 5 is examined

This unit covers filtering, text classification and clustering, and the algorithms behind them; no topic was asked in the supplied papers, so all four are short.

Information filtering: organization and relevance feedback

Not asked since 2022

Definition. Information filtering removes irrelevant items from a stream of incoming documents and delivers only those matching a user's long-term profile.

Key points.

Filtering is push-style: the profile stays fixed while documents arrive, unlike search where the query changes over documents that stay fixed.
Documents are organized by matching them against user profiles stored as term vectors or categories.
Relevance feedback lets the user mark delivered items relevant or non-relevant, and the profile is updated from them.
The Rocchio update is $q_{new}=\alpha q_0+\beta\,\frac{1}{|D_r|}\sum_{d\in D_r} d-\gamma\,\frac{1}{|D_{nr}|}\sum_{d\in D_{nr}} d$.

Text Mining: text classification and clustering

Definition. Text mining extracts useful patterns and knowledge from unstructured text; classification assigns documents to predefined classes, while clustering groups them by similarity without predefined classes.

Key points.

Classification is supervised: it learns from labelled training documents, for example spam versus not spam.
Clustering is unsupervised: groups emerge from similarity alone, for example grouping news stories by topic.
Both represent documents as TF-IDF vectors and use distances such as cosine similarity.
Classification predicts a known label, whereas clustering discovers unknown structure.

Categorization algorithms: naive Bayes, decision trees and nearest neighbor

Definition. A categorization algorithm learns from labelled documents to assign a new document to one of the predefined classes.

Key points.

Naive Bayes chooses the class maximizing $P(c)\prod_i P(t_i\mid c)$, assuming terms are independent given the class.
A decision tree tests one term or attribute at each node, chosen by information gain, and each leaf gives a class.
Nearest neighbor (kNN) gives a document the majority class of its $k$ most similar training documents, with no training phase.
Naive Bayes is fast and simple, trees are easy to read, and kNN is flexible but slow at query time.

Clustering algorithms: agglomerative clustering, k-means, expectation maximization (EM)

Definition. Clustering algorithms partition documents into groups so that documents inside a group are similar and documents in different groups are dissimilar.

Key points.

Agglomerative clustering starts with each document as its own cluster and repeatedly merges the two closest clusters, giving a dendrogram.
K-means picks $k$ centroids, assigns every document to its nearest centroid, recomputes centroids as means, and repeats until assignments stop changing.
EM fits a mixture of probability distributions: the E-step computes each document's soft membership in every cluster, and the M-step re-estimates the parameters.
K-means is hard clustering; EM is soft clustering and generalizes k-means.

Last-minute revision

Filtering keeps a fixed profile and a changing document stream.
Rocchio moves the query towards relevant documents and away from non-relevant ones.
Classification is supervised; clustering is unsupervised.
Naive Bayes assumes terms are independent given the class.
Decision trees split on information gain.
kNN takes the majority class of the $k$ nearest documents.
Agglomerative clustering is bottom-up and produces a dendrogram.
K-means alternates assignment and centroid update until convergence.
EM alternates E-step (soft memberships) and M-step (parameters).

Memory hooks

Filtering is a fixed profile with a moving stream; search is the reverse.
"Naive" means terms are treated as independent.
kNN is lazy: no training, all work at query time.
E then M: Estimate memberships, Maximize parameters.

Coverage checklist

Information filtering: organization and relevance feedback (no past questions).
Text Mining- Text classification and clustering (no past questions).
Categorization algorithms, naive Bayes, decision trees and nearest neighbor (no past questions).
Clustering algorithms: agglomerative clustering, k-means, expectation maximization (EM) (no past questions).

Account

Information Retrieval (AD-603 (C)) - Unit 5 Short Notes

How unit 5 is examined

Information filtering: organization and relevance feedback

Text Mining: text classification and clustering

Categorization algorithms: naive Bayes, decision trees and nearest neighbor

Clustering algorithms: agglomerative clustering, k-means, expectation maximization (EM)

Last-minute revision

Memory hooks

Coverage checklist