Text Classification, Clustering, and Web Search

11.1 Bernoulli Naive Bayes Smoothing and Worked Numerical

11.1.1 Mathematical Formulation

A single zero can wipe out a whole document score. That risk is the reason smoothing exists, and it is the thread that ties this section together.

Think of the two models with two everyday pictures. A multinomial Naive Bayes model is a bag of marbles where each draw is one word slot and repeats count. Pulling five Chinese marbles out of eight draws means something different from pulling one. A Bernoulli Naive Bayes model is a checklist where each word gets a tick for present or a cross for absent. The checklist never asks how many times a word rang the bell, only whether it rang at all. Remember the detective updating a hunch as clues arrive: the prior is the opening hunch, each word is a fresh clue, and absence of a clue is also a clue under the checklist view. The bag picture breaks for Bernoulli because repeats are thrown away; the checklist picture breaks for multinomial because absence carries no weight there.

The smoothed multinomial estimate is built in three moves. Start from the raw share of slots:

$$P(w\mid c)=\frac{N_{c,w}}{N_c}$$

Add one fake hit to every word so no numerator is zero:

$$P(w\mid c)=\frac{N_{c,w}+\alpha }{\text{smoothed total}}$$

Balance the books by adding the same fake mass to the denominator once per vocabulary entry. Summing the numerator over all $D$ words adds $\alpha D$ in total, so the denominator must grow by the same amount for chances over the vocabulary to still sum to one:

$$P(w\mid c)=\frac{N_{c,w}+\alpha }{N_c+\alpha D}$$

A concrete anchor used here was the word Chinese with five hits out of eight word slots, so $N_{c,w}/N_c=5/8$ before smoothing, and $(5+1)/(8+D)$ after smoothing with $\alpha =1$. The loop behind the denominator runs over every entry of the vocabulary while counting tokens. That loop is what puts the distinct-word count into the denominator and balances the extra $\alpha$ added on top.

With smoothing value $\alpha$, the Bernoulli estimate is:

$$P(w\mid c)=\frac{N_{c,w}+\alpha }{N_c+2\alpha }$$

With $\alpha =1$ this becomes $(N_{c,w}+1)/(N_c+2)$. The constant $2$ counts the two instances of the attribute: a word either shows up or does not show up. A three-class problem still uses two, because the two counts presence against absence of the token itself. Texts often write the same idea as $(N_{c,w}+1)/(N_c+2)$ directly; here we keep $\alpha$ visible so the link to the multinomial form stays plain. The two formulas share one shape, add fake counts on top and balance them below, but they count different things, slots against documents, and they balance with different constants, $D$ against two.

Scoring a fresh document uses the posterior chance of each class, written $P(c\mid d)$. The posterior stays in proportion to the prior times the occurrence chance for words in the query times the non-occurrence chance for the rest:

$$P(c\mid d)\propto P(c)\prod _{w\in V}P(w\mid c{)}^{b_w}(1-P(w\mid c){)}^{1-b_w}$$

Here $V$ is the vocabulary set and $b_w$ marks presence ($1$) or absence ($0$) of word $w$ in document $d$. When $b_w=1$ the factor picks $P(w\mid c)$; when $b_w=0$ it picks $1-P(w\mid c)$. Words in the query use their occurrence chance. Words missing from the query use the non-occurrence chance $1-P(w\mid c)$. The product form rests on an independence bet: each word trait is treated as standing apart from the rest, so separate chances may multiply. In practice the computation runs in log space as a sum of log chances, which keeps small products away from underflow and turns the winning class into the largest log score. Non-occurrence words count as real proof, which is the sharp split from the multinomial form where absent words drop out of the product.

Picture a bar chart with one bar per vocabulary word for a fixed class. Bar height is $P(w\mid c)$. The horizontal axis lists words, the vertical axis runs from zero to one. Smoothing lifts every zero bar a little off the floor and shaves a little off the tall bars so the total still sums to one. The takeaway in one line: smoothing trades a little sharpness on seen words for safety on unseen words. The same chart under the Bernoulli view has paired bars per word, present against absent, and the pair always sums to one.

11.1.2 Worked Examples

11.1.3 Student Questions and Answers

Body text bridges the two doubts. The first doubt mixed up two counts that sound alike: how many classes exist against how many faces one word has. The second doubt mixed up two stages that run back to back: table lookups against the final product.

Real use is close by. Short-message sentiment tools and spam filters often start from this checklist model because a single spam trigger word matters more than how many times it repeats in one short note. Longer news-topic engines lean multinomial because five mentions of Beijing carry more topic proof than one.

11.2 Rocchio Centroid Classification with TF-IDF

11.2.1 Mathematical Formulation

How do you sort documents when text has no numbers in it at all? The answer runs in three moves: turn words into weights, make long and short documents fair, then replace each class by its middle point.

Think of each class as a sports team photo. Each player is one document vector. The centroid is the spot where the team would balance if every player pulled with equal force. A new player joins the team whose balance point sits closest. The picture breaks when a team forms a ring instead of a huddle: the middle of a ring is empty air, and the average points at no one. That limit is why Rocchio suits round blobs and struggles with rings and chains.

$$\mu (c)=\frac{1}{|D_c|}\sum _{d\in D_c}v(d)$$

The spoken definition behind this line was centroid for the China class is D1 plus D2 plus D3 divided by three. Each slot of the centroid is the plain mean of that slot across members, with no extra fixing step on the centroid itself.

Raw text is unstructured data, so numbers must be built before any vector method can run. The chosen bridge was TF-IDF, the product of term frequency and inverse document frequency. Term frequency, written $\text{tf}(t,d)$, counts hits of term $t$ in document $d$. Inverse document frequency, written $\text{idf}(t)$, down-weighs terms spread across many documents. With $N$ documents in the whole store and $\text{df}(t)$ documents holding the term, the spoken form log of N by df renders as:

$$\text{idf}(t)=\log \frac{N}{\text{df}(t)}$$

The log base was left unstated in the session. Reference material uses base 10 for its worked idf table and notes that the exact base does not change the ranking order, since changing the base multiplies every idf by one shared constant. Numbers below use base 10, so $\log 4\approx 0.602$ and $\log 1=0$; any other base keeps every comparison in the same order. A constrained term-frequency variant one plus log TF also came up, rendered as $1+\log \text{tf}(t,d)$, with smoothing as its motive: it damps the tenth hit of a word so it counts less than the first hit. The session set that variant aside for ease and used raw counts, with library code left to do the full form in real runs.

The TF-IDF weight of term $t$ in document $d$ is then:

$$\text{tf-idf}(t,d)=\text{tf}(t,d)\times \text{idf}(t)$$

A word found everywhere adds no split power. When $\text{df}(t)=N$, the ratio is one and $\log 1=0$, so every entry for that word becomes zero.

Vectors then pass through normalization, which divides each vector by its own length so long and short documents meet on fair terms. With length $\Vert x\Vert =\sqrt{{\sum }_i{x}_i^2}$, the unit form is $x/\Vert x\Vert$. A document with two unit entries has length $\sqrt{1^2+1^2}=\sqrt{2}\approx 1.414$, so each entry becomes $1/\sqrt{2}\approx 0.71$. Converting all prices to the same currency is the matching everyday picture: after the fix, only direction matters, not document size.

The reason IDF for a test document still comes from training counts is that the training store defines the background rates. New words in a query borrow the document frequencies seen during training. A query never gets to vote on how rare its own words are.

Picture a scatter plot with one axis per word after fixing. Each document is one arrow from the origin to the unit circle. Long and short originals now end on the same circle, so the gap between arrow tips measures topic angle, not length. Class blobs form caps on the circle and each centroid arrow points at the middle of its cap. The takeaway in one line: weighting picks the telling words, fixing puts all arrows on one circle, and the centroid marks the middle of each team.

11.2.2 Worked Examples

11.2.3 Student Questions and Answers

Body text links the next two doubts. Both ask what may be borrowed and what may be cut: background rates are borrowed, shared constants are cut.

Real runs hand the full TF-IDF form to library code, which adds log damping and smoothing without hand cuts. News-topic routing is a classic home for this pipeline: a stream of fresh articles meets stable class middles for sport, business, and world news.

11.3 Second Rocchio Example and Exam Technique

11.3.1 Worked Examples

A second Rocchio pass shows the hand-safe path: TF only, no fixing, plain Euclidean gaps. The point is exam craft as much as geometry.

Steps run in order. Build one count row per line over a fixed shared word set. Average the two dog rows for the dog centroid and the two cat rows for the cat centroid. Score the query against each centroid with plain Euclidean distance, the square root of summed squared gaps, and hand the query to the nearer middle point.

Picture two middle points on a flat sheet with the query dot between them. The dog point sits toward the cute-fluffy corner, the cat point toward the white-kitten corner, and the query dot falls inside the cat half of the sheet. The boundary is the line of points at equal gap from both middles. The takeaway in one line: middles plus nearest-gap rule is the whole classifier.

Hand Rocchio of this size also lives in support ticket routing: a fresh ticket meets the middle of each queue by word counts and joins the nearer queue.

11.3.2 Student Questions and Answers

11.4 K-Nearest Neighbour Classification of Text

11.4.1 Mathematical Formulation

Why train at all when you can just ask the neighbours? That question opens this method, which stores almost everything and decides at test time.

Think of a new family moving onto a street. To guess which school their kids will join, ask the three nearest houses, not the town average. If two of the three nearest send kids to the north school, bet north. The street picture breaks when streets mix: one odd house in a mixed block can tip a small vote, which is why the size of the voting crowd matters.

Training holds two duties: process and store the vectors, and fix $K$. Testing holds the costly duty: score the query against the store and assign the majority label. That test-time cost is the known price, accepted because the method often beats Naive Bayes and Rocchio on real collections with odd shapes. Small training stores and cases where sample counts sit far below feature counts still suit Naive Bayes well, while larger stores favour neighbour voting.

Distance usually means Euclidean distance between query $q$ and document $d$ over shared slots $i$:

$$d(q,d)=\sqrt{\sum _i(q_i-d_i{)}^2}$$

Each slot gap is squared, squared gaps add, and the root brings the total back to length units. When a problem leaves the measure open, Manhattan distance, the sum of absolute gaps ${\sum }_i|q_i-d_i|$, is the lighter hand choice. Manhattan skips squares and roots, so hand arithmetic stays short. For length-fixed vectors the same choice can be read as a cosine score; for raw TF rows the gap forms above are the working tools.

Picture the China blobs from the last section, now with no middle points drawn. The query dot sits inside a yes patch with D1 and D2 close by and D4 far off in its own corner. Circles around the query with radius to the first, second, and third neighbour each catch a voting crowd. The takeaway in one line: patches plus local votes replace middles.

Side-by-side contrast helps here. Rocchio keeps one middle per class and scores $|C|$ gaps per query, which is fast but stiff. KNN keeps every row and scores $|D|$ gaps per query, which is slow but bendy. Naive Bayes keeps chances per word and scores products, which is fast and strong on small stores. Pick middles for speed on round topics, votes for shape on big stores, chances for small stores.

11.4.2 Worked Examples

11.4.3 Student Questions and Answers

Ticket triage at scale is a natural home: a fresh ticket meets thousands of old tickets and takes the label of its closest past cases, even when each queue holds several writing styles.

11.5 Judging Classifiers

11.5.1 Mathematical Formulation

A classifier that brags about one number is hiding the rest of the story. This section builds the full scorecard: one table, four cells, and the scores that read it.

Think of airport screening. True positives are banned items caught, true negatives are safe bags waved through, false positives are safe bags pulled aside, and false negatives are banned items that slip through. Catching everything means pulling many safe bags aside; waving everyone through means missing threats. The trade between alarms and misses is the whole game.

Accuracy is the share of all calls that came out right:

$$\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}$$

Accuracy can mislead on skewed data, so precision and recall split the story. Precision asks how many predicted yes calls were truly yes: of all bags pulled aside, how many held threats. Recall asks how many actual yes cases got caught: of all threats in the stream, how many were stopped. With the cell names above:

$$\text{Precision}=\frac{TP}{TP+FP},\text{Recall}=\frac{TP}{TP+FN}$$

Take a tiny table: TP 8, FP 2, FN 4, TN 86. Accuracy is $(8+86)/100=0.94$. Precision is $8/(8+2)=0.8$. Recall is $8/(8+4)\approx 0.667$. The 0.94 headline looks strong while recall shows one third of threats slip through. That split is why skewed tasks quote precision and recall, not accuracy alone.

Pushing one of the pair usually hurts the other, which is the classic trade-off. A strict caller raises precision but drops recall; a lax caller raises recall but drops precision. Their harmonic mean, called the F1 score, blends them into one number:

$$F_1=\frac{2\cdot \text{Precision}\cdot \text{Recall}}{\text{Precision}+\text{Recall}}$$

The harmonic mean punishes lopsided pairs more than a plain average. With precision 0.8 and recall 0.667, F1 is $2\times 0.8\times 0.667/(0.8+0.667)\approx 0.727$, below the plain average 0.733 and far below accuracy 0.94. Equal weights sit inside this form; tasks that prize catches over false alarms weight recall more, and tasks that prize clean alarms weight precision more.

A receiver operating curve watches the trade across all thresholds. It plots true positive rate against false positive rate:

$$\text{TPR}=\frac{TP}{TP+FN},\text{FPR}=\frac{FP}{FP+TN}$$

True positive rate is recall under another name: threats caught. False positive rate is safe bags pulled aside per safe bag in the stream. Each threshold gives one dot; sweeping the threshold draws the curve from the lax corner to the strict corner.

Picture the unit square. The horizontal axis runs from zero to one false-alarm rate, the vertical axis from zero to one catch rate. A random ranker traces the diagonal: catching 30 percent of threats costs 30 percent false alarms. Good rankers bow the curve toward the top-left corner, catching most threats at tiny false-alarm cost, and the area under the curve grows as the bow strengthens. The aim is to push that area as high as it can go, with the top-left corner as the ideal. Area 0.5 reads random; area near 1.0 reads near perfect.

11.5.2 Student Questions and Answers

Spam triage uses precision to protect the inbox from false blocks, while outbreak screening uses recall to catch every case for follow-up. Both quote the same four cells and read different corners of them.

11.6 Clustering Foundations

11.6.1 Core Ideas

Labels cost money; raw text is free. Clustering is what you do when the answer tags never arrive.

Clustering groups data with no class labels to learn from, which is the unsupervised setting (learning without answer tags). No gold answer sheet exists to check against, so groups must be read out of the data itself. Text without tags is a natural fit: large stores often arrive with no ground truth at all. Supervised sorting from earlier sections asked which shelf a tagged book joins; clustering walks into an untagged warehouse and decides how many piles exist and what belongs together.

The goal is easy to state. Points inside one group should sit close together, which is low intra-cluster distance (small gaps within a group) or high inner density. Groups should sit far apart, which is high inter-cluster distance (large gaps across groups) or high separation of densities. Whatever method runs, hitting both marks at once counts as success. Tight huddles far apart read well; loose clouds that bleed into each other read poorly.

The first hard question is how many groups, $K$, the data really holds. The elbow method is the book path: run the grouper for $K=1,2,3,4,5,6$ and beyond, plot the error on the side, and look for the bend where fresh gains flatten out. Picture error on the vertical axis against $K$ on the horizontal axis: the curve drops fast at first, then the slope flattens at the bend like an arm. That bend marks the near-best $K$. Small $K$ under-splits real groups; huge $K$ chops one real group into slivers for tiny gains. Other paths named were Jaccard similarity (overlap of sets as a score, shared members over all members) and normalized mutual information (shared information between two groupings, scaled to a fixed range). The price of the elbow path is reruns: the method must run again and again until successive errors barely move.

The second hard question is naming. Geometry may show three blobs, yet only a later check with domain knowledge tells whether three real groups exist. A patient example made the point: one blob could be stage one cases, a second blob stage two cases, and a tiny third blob patients sliding toward stage three. Or the tiny blob could belong inside stage two, leaving two groups. Or hidden splits could push the count to four. Method output plus metadata and expert review must agree before the count is trusted. Geometry proposes; experts dispose. Treating blob count as truth without that check is how treatment groups, fraud rings, or news topics get misread.

A hard grouping puts each point in exactly one group. Fifth-grade against sixth-grade pupils was the picture: no pupil sits in both grades at once. K-means gives hard groups. A soft grouping lets points belong on both sides. The picture was two commentators who are both cricketers and politicians at once. Expectation maximization (a fit-and-reassign loop that softens membership) gives soft groups by scoring fractional membership per point and retuning centres by expected pull. Remember the grade pupils for hard borders and the double-role commentators for soft shares; the same person can be mostly one role with a real foot in the other.

Picture three blobs on a sheet: two big clouds and one tiny patch between them. The tiny patch could be its own group, a bridge, or noise. Error-against-$K$ bends near three, but the naming choice still needs metadata. The takeaway in one line: geometry counts shapes while people confirm meanings.

11.6.2 Student Questions and Answers

News engines group fresh stories without tags so readers can browse events, and inboxes group threads the same way. Both start untagged and earn trust only after human checks.

11.7 K-Means Algorithm Step by Step

11.7.1 Mathematical Formulation

Averages can sort data on their own if you let them move. That moving-average loop is the whole method.

$${\mu }_k=\frac{1}{|C_k|}\sum _{x\in C_k}x$$

Here $C_k$ is group $k$, $|C_k|$ counts its members, and the sum adds vectors slot by slot. A small number sketch fixed the mean idea. With $A=(1,2)$, $B=(3,5)$, and $C=(4,6)$ in one group, the centroid is:

$${\mu }_1=\left(\frac{1+3+4}{3},\frac{2+5+6}{3}\right)=\left(\frac{8}{3},\frac{13}{3}\right)\approx (2.67,4.33)$$

Each slot adds its member values and divides by the member count of three. First slot: $1+3+4=8$, over 3 gives 2.67. Second slot: $2+5+6=13$, over 3 gives 4.33.

Picture points on a sheet with red and blue flags for centroids. Round one draws borders halfway between flags and colours each point by its nearer flag. Flags then jump to the middle of their new colour crowds, borders tilt, and colours update. The takeaway in one line: flags pull points, points pull flags, until neither moves.

11.7.2 Worked Examples

11.7.3 Student Questions and Answers

Body text bridges the two doubts. The first doubt fixes the direction of the assignment; the second fixes what the halving meant.

Store layouts use the same loop: nightly baskets meet $K$ middles and each basket joins its nearest buying pattern.

11.8 Initial Centroids and Cluster Quality Scores

11.8.1 Core Ideas

Good middles are not handed over with the data. Bad starts can trap the whole run, and no answer sheet exists to cry foul.

Picture one dataset run twice. With lucky seeds the run settled into the expected three groups by the sixth round. The same data with unlucky seeds still looked wrong at the fifth round: one true group had split in two while two true groups had merged into one, with no known count of further rounds to repair it. More rounds cannot promise escape because each round deepens the current valley. The fix must come from better starts, not longer walks.

Three workarounds were laid out. First, rerun many times from fresh random seeds, a brute-force path with an open bill since the settling point stays unknown. Keep the tightest run by score. Second, run a hierarchical grouping first (a tree-building grouper, bottom-up merging or top-down splitting) and read its dendrogram (the merge tree). A high tree cut reads fewer groups, such as one branch against the rest for two groups. A lower cut across three branches reads three groups. The cut sets the seed count with proof behind it, and branch middles seed the flat run. Third, seed more centres than the elbow count: if the bend says five, open with six, seven, or ten, watch for over-splitting or under-splitting, and trim back to the count the splits support. Extra seeds catch small true groups that one-per-guess starts miss; empty or twin seeds then merge away. No single foolproof path exists, so each problem earns its own fix.

Judging a finished grouping without answer tags leans on the centroids as stand-in truth. The sum of squared errors, shortened to SSE, adds each point's gap to its nearest centroid across the whole store. Per-group subtotals add into one grand total:

$$\text{SSE}=\sum _k\sum _{x\in C_k}\Vert x-{\mu }_k{\Vert }^2$$

Here $C_k$ is group $k$ and ${\mu }_k$ its centroid. The inner sum scores one group; the outer sum adds groups. Squaring punishes far strays more than near wobbles, so tight huddles score low. Smaller totals mean tighter groups, so runs compete downward. The residual sum of squares follows the same sum-of-squared-gaps idea over the vectors and likewise aims low. The two read as one and the same in practice. A numeric anchor was given: a five-group run scoring $0.7$ beats a three-group run scoring $0.8$, so five groups would be kept. The same score also picks $K$: plot SSE against $K$ and read the bend where extra groups buy little extra tightness, matching the elbow path from the foundations section.

Picture SSE against $K$ falling fast then flat. At $K=1$ the total is huge, at $K=3$ much lower, at $K=5$ lower still at 0.7 against 0.8 at three. Past the bend the curve crawls because new middles split true groups for crumbs. The takeaway in one line: starts pick the valley, SSE scores the valley floor, and the bend prices extra middles.

11.8.2 Student Questions and Answers

Ad platforms use the same habit: many seed sets overnight, one SSE contest in the morning, and the tightest audience map goes live.

11.9 Other Clustering Families and Picking the Right Tool

11.9.1 Core Ideas

One shape bet cannot fit every dataset. This section tours the other bets and the rule for matching tool to setting.

Many groupers exist beyond K-means, and each leans on its own shape bet. K-means expects neighbours to clump in blobs around means under Euclidean gaps. A K-medoids grouper swaps the mean for the medoid (the most central actual member), with partitioning around medoids, shortened to PAM, as the named routine. Medoids resist strays because the centre must be a real member, not a pulled mean; the price is higher cost on big stores. Hierarchical groupers expect tree-shaped merges and offer four gap readings: minimum gap, maximum gap, average gap, or centre-to-centre gap, each giving its own variant. Minimum gap chains neighbours dot-to-dot and can snake; maximum gap keeps groups tight and round; average and centre readings sit between. DBSCAN (a density grouper that grows groups from thick patches) expects thick patches of neighbours and names three roles: core point (a point with enough neighbours in reach), border point (a reachable point too thin to grow from), and noise point (a point left out). Reachable core points keep joining until the thick patch ends, so rings and trails group by linkage, not roundness.

The four-circle picture showed the density bet at work. Dots chained dot-to-dot across each ring, so each ring read as one group even though no round blob existed, giving four groups in all. K-means would plant middles in the empty centres and slice rings into wedges; the density rule instead walks each ring and keeps it whole. Further families were named in quick tour form: OPTICS (a density ordering method that ranks points by reachability for many thresholds at once), minimum spanning tree grouping (a graph-link method that cuts long links), spectral grouping (a graph-cut method that slices weakly joined sheets), and node-link science methods Louvain, Leiden, and WalkTrap plus Newman-style community reading. In the WalkTrap picture a random walker treads some paths far more often than others, and the heavily trodden node sets become groups. Walkers linger inside tight knots and rarely cross thin bridges, so tread counts expose knots.

Matching tool to setting was the closing moral. Peak-hour ride grouping over a trip network calls for a network method, since raw closeness misses the link structure: two stops may sit near on the map yet share no direct route. Shopping-pattern mining over buyer similarity calls for gap-based methods such as hierarchical grouping or K-means: baskets with shared items sit near in count space and blobs mean taste groups. A Gaussian mixture model (a soft grouper that fits overlapping bell shapes with an expectation maximization loop) came up from the floor as the soft option: it scores each point's chance under each group and tunes centres by expected likelihood, which helps when groups overlap. That soft scoring has been used in software-testing data analysis, where failing runs blend causes instead of sitting in one hard box.

Picture a choice grid: rows are data shapes, columns are tools, and only the matching cells light up. Blobs light K-means and medoids; trees light hierarchical cuts; rings light density walks; graphs light Louvain, Leiden, and WalkTrap; overlaps light mixtures. The takeaway in one line: name the shape first, then lift the tool.

11.9.2 Student Questions and Answers

Body text bridges the two doubts. The first doubt asks whether background tools matter; the second asks when softness pays.

11.10 Why Web Search Is Harder Than Classical Retrieval

11.10.1 Core Ideas

A tidy library and the open web both answer queries, but only one of them fights spam, money, and endless change at once. This block follows Chapter 19 of Introduction to Information Retrieval by Manning and co-authors, the same book source as the rest of the block.

That heterogeneity (mixed origins, mixed motives, mixed trust) breaks the tidy-collection bet. One index must hold peer papers, shop fronts, rants, and traps side by side and still rank with a straight face. No single style, length, or quality rule fits all corners.

A gene query showed the mix. The query BRCA1, a gene widely studied for breast cancer, pulls peer-reviewed papers, recorded patents on the gene, pharmacy adverts, and casual explainers into one result list. One short string returns science, commerce, and chatter side by side. The engine cannot wish the adverts away; it must rank proof above pitch without pretending the pitch is absent.

Four puzzles follow for any engine builder. How does one index a store that huge. How does one attach a trust score to each page. How does one cope with a collection that never sits still. How does one handle repeats and near-repeats. An index here means the stored page collection behind the engine, like the word index at the back of a book: look up a word and jump straight to its pages instead of scanning the whole book. Remember the back-of-book jump the next time crawl size feels abstract: without the jump, every query scans billions of pages.

Money pressure is the last twist. Search owners need brand income, yet brand weight must not bend ranked results. The first-generation paid engine GoTo, dated 1996 in the session, ranked results purely by advertiser bids, which put revenue first and relevance second. GoTo ranked purely by bid money. The second-generation answer, Google, split the page strictly: ranked results on one side from search merit, adverts on a separate side ordered by money but never mixed into the ranked list. Google keeps ranked results apart from paid adverts. The open policy question is how much brand bend, if any, a results list may carry, with zero bend as the ideal. Trust dies fast once users sense bids inside the rankings.

Picture a market street against a library hall. The hall holds tagged shelves that rarely move; the street holds shouting stalls that open, copy each other, and vanish by night. The takeaway in one line: the web is a street, not a hall, so ranking must weigh trust and freshness alongside topic match.

11.10.2 Student Questions and Answers

Drug queries live this split daily: trial papers, patent filings, and pill adverts share one string while patients need proof ranked first.

11.11 Search Engine Parts and Differences from Classical Systems

11.11.1 Core Ideas

An engine is a line of workers, each handing a cleaner product to the next. Miss one worker and the line jams.

A full engine reads as a pipeline. Web documents feed a crawler (an automated fetcher that finds and pulls pages). Crawled pages feed an index (the store-and-organize stage). A user query then searches the index and returns ranked documents. Between the boxes sit parsers (text cleaners and splitters) and an indexer (the builder of the inverted index, the word-to-page map), plus a link graph (the page-to-page hyperlink map) and duplicate removal (the near-repeat filter). In short: crawl means find and fetch, index means store and organize, and search means rank and retrieve. The coming sessions continue with index size, duplicate deletion, ranking, crawling, and search challenges. Think of a kitchen line: foragers fetch, prep cooks clean and chop, the pantry maps every jar, and the head cook plates per order while tossing copied plates.

Classical and web systems split five ways. First, links: web pages carry hyperlinks to other pages, so reading one result opens doors to more results, while classical retrieval is flat and static with no such doors. Links spread trust and topics across pages, which later ranking turns into scores. Second, queries: web queries run into the billions and vary wildly, far past the neat statements of a closed store. Short, mixed, and multilingual strings are the norm. Third, users: web users number in the billions with mixed skill, unlike the trained searcher a classical system expects. Plain boxes beat query languages at this scale. Fourth, scale: the web holds hundreds of billions of documents, so every stage must stream and shard. Fifth, context and commerce: location, session trail, and personal profile steer web results, and adverts plus spam press in from the sides, while classical setups face neither force.

Context decides meanings. The query Python from a library terminal should surface programming books, while the same string from a forest-department post near the Amazon should surface the snake. Classical setups paid little heed to such signals; web engines live by them. Place, role, and trail flip the top hit without changing the string.

Picture the pipeline as five boxes with arrows: fetch, clean, map, link, rank. Side arrows feed context into rank and adverts into their own marked lane. The takeaway in one line: fetch wide, map tightly, rank with context, and fence the money lane.

11.11.2 Student Questions and Answers

Travel search shows the line daily: crawled listings, cleaned text, word maps, link scores, repeat filters, and location-aware ranks with marked sponsored slots apart.

11.12 Static Web Graph and User Behaviour

11.12.1 Core Ideas

Links turn pages into a map, and readers turn the map into habits. Ranking must read both.

A static web (fixed pages with fixed hyperlinks, leaving aside moving and script-built pages) draws neatly as a directed graph (nodes for pages, arrows for hyperlinks). With pages A, B, C, D in rank order, opening A may show a link to C, which draws an arrow A to C. Page B may point at A and at itself. Page C may point at B. Each arrow gives an out-link (an arrow leaving a page) to its source and an in-link (an arrow entering a page) to its target, with out-degree and in-degree counting each side. Self-links count on both sides of their page. Rank order here means crawl or label order, not quality order.

Reachability is not promised: some pages sit off the walked paths, so no chain of arrows ever lands on them. Connected components (tightly knit node sets) expose such splits, and triangle counts (three pages linking round in a loop) act as the working signal. More triangles mean a tighter patch. A clique (a fully connected set where every node links every other node) is the extreme: four nodes with all four triangles present score the maximum component value of one. Reading triangle loops on undirected graphs ignores arrow colours, but on directed graphs each arrow must face the right way round the loop, which is why only one directed triangle survived in the worked sketch. Direction is the whole test: three edges that fail to chase round the loop do not count.

Guessing need splits two ways. Context-free guessing reads the bare string only. Context-aware guessing reads geography, past sessions, and personal profile alongside the string. The query Jaguar may mean car, animal, or operating system until context breaks the tie. A string such as five plus four should wake a calculator, and a string such as one kilogram in pounds should wake a converter. Two ranking moves then apply. Restriction drops wrong-sense results outright and re-ranks what stays, as when Google.fr (the French Google domain) keeps French documents even for an English string. Ranking modulation keeps the shared pool yet reorders it per person and session, which is why two searchers may share page-one entries in a different order. Google.fr ranks French documents first for its users. Restriction filters the pool; modulation shuffles it.

Behaviour data backs simple designs. Searchers type short strings, about three words on average and rarely past four. They skip AND and OR operators even when the logic is known; at most a quoted phrase such as linked list or a plus sign binds words. They read only the first pages and almost never cross page two. They want a plain box plus results that fit their own setting on the first screen. Fancy query grammar sits unused while the first screen decides trust.

Classical scores still count, with a top-heavy twist. Precision, recall, and the F1 blend hold good on the web, but since eyes stop early, precision at one and precision at ten (precision scored over only the first one or ten results) are the working cuts. Precision at ten asks how many of the first ten hits satisfy the need; precision at one asks whether the very top hit does. New pressures join them: trust in pages, duplicate elimination, reliability, readability, and latency (answer speed). Classical flat stores never faced repeats or trust at web scale, so these weigh far more here. A fast, readable, trusted top ten beats a slow perfect list buried on page three.

Picture the graph as four dots with arrows A to C, B to A, B to self, and C to B, plus one directed triangle that chases round correctly while near-miss triples fail the direction test. Beside it picture a steep attention curve: most clicks on rank one, few by rank ten, almost none past page two. The takeaway in one line: link shape picks candidates, context orders them, and only the top survives readers.

11.12.2 Student Questions and Answers

Body text bridges the two doubts. The first doubt fixes the geometry rule; the second fixes the language-rule weight.

Local search shows the blend: map dots, direction-aware tightness, French-first modulation on Google.fr, and a top-ten readers actually see.

Exam Guidance Summary

Expect the grouping numerical only from K-means; hierarchical and density methods stay as background and will not be asked as hand problems. Read each classification ask word by word: TF only means skip IDF, TF-IDF means run both halves, and a free choice means Manhattan distance keeps hand arithmetic short. Write every premise on the page, including TF scope and whether fixing ran, since that line proves the idea is in place. Show table work row by row so partial marks can follow the trail. For Bernoulli smoothing, the denominator constant is two for token presence against absence, never the class count. For Rocchio and neighbour runs, IDF rates come from the training store. For web search, precision at one and precision at ten are the scoring cuts to quote, with trust, duplicate elimination, reliability, readability, and latency as the added pressures. For the curve, horizontal holds the false positive rate and vertical holds the true positive rate with the top-left corner as the target. For K-means, assign each point to the minimum gap and close only after two calm rounds in a row.

Key Industry Applications

News-topic routing runs Rocchio middles over TF-IDF rows to sort fresh articles into sport, business, and world desks. Ticket triage at scale runs neighbour votes over count rows so a fresh ticket takes the label of its closest past cases. Nightly basket maps run K-means middles over buying patterns to refresh audience groups. Short-message spam and sentiment filters start from Bernoulli checklists where one trigger word matters more than repeats. Peak-hour ride grouping over trip networks fits network tools such as Louvain, Leiden, and WalkTrap because raw map closeness misses route links. Shopping-pattern mining over buyer similarity fits gap tools such as K-means and hierarchical grouping. Soft membership scoring with Gaussian mixtures has served software-testing analysis where failing runs blend causes. Library code computes full TF-IDF with log damping and smoothing for all of the above. On the web, the early paid engine GoTo ranked results purely by advertiser bids, while Google split ranked results from paid adverts, keeping the ranked side on search merit. Google.fr re-ranks toward French documents for its users. Pharmacy adverts and patents share result lists with peer-reviewed papers for gene queries such as BRCA1, so proof must outrank pitch.