Book summary “Programming Collective Intelligence”: summary

Introduction

You face a massive challenge when moving beyond traditional databases to mine user-contributed web data for behavioral insights. Standard applications store and retrieve information, but modern users expect systems that learn from behavior, predict preferences, and automate discovery. Toby Segaran provides a guide to building intelligent Python applications using machine learning, recommendation systems, and optimization techniques.

You can build smarter applications that harness web data and user behavior by combining machine learning algorithms, statistical models, and open APIs.

The book outlines a progression from simple collaborative filtering to advanced classification and genetic programming. You will explore how algorithms make recommendations, rank search results, and categorize documents.

• How do you match users with items using similarity metrics?
• How do search engines calculate authority and rank web text?
• How can optimization algorithms solve complex combinatorial problems?
• How do classifiers categorize text and discover hidden themes?

1. Making Recommendations and Discovering Groups

Collaborative filtering algorithms match users and items using similarity metrics like Euclidean distance and Pearson correlation, while unsupervised clustering groups unstructured data.

As available options grow beyond the scope of a small circle of friends, automated collaborative filtering evaluates similarity metrics across user preference profiles and computes weighted averages to recommend unseen items. David Goldberg designed the Tapestry system at Xerox PARC in 1992, using document annotations to filter information for other users.

Collaborative Filtering

Similarity between users or items can be quantified using metrics like Euclidean distance and Pearson correlation, with Pearson correcting for systematic grade inflation. Euclidean distance measures direct proximity in preference space but remains sensitive to consistent harshness or leniency in ratings. Pearson correlation measures how well two sets of data fit on a straight line, successfully correcting for grade inflation when one reviewer consistently gives higher scores than another. The range of the Pearson correlation coefficient spans from 1 to -1.

Movie critics like Jack Matthews and Lisa Rose have distinct overall rating scales, yet their relative preferences align along a best-fit line captured by the Pearson score.

Generating personalized recommendations requires computing a weighted average of other users' rankings scaled by their similarity scores, normalized by the sum of similarities. To prevent reviewers who have not seen many items or reviewers with anomalous tastes from skewing results, each rating is multiplied by the corresponding user similarity score, summed across all reviewers, and divided by the sum of similarities for those who rated the specific item. Toby generates personalized movie recommendations for titles such as The Night Listener and Lady in the Water by weighting movie critic ratings with their Pearson correlation scores.

You implement this mechanism with specific steps:

• Loop through every other person in the preferences dictionary and ignore self-comparisons.
• Calculate the similarity between the target person and the other user, ignoring scores of zero or lower.
• Loop through every item rated by the other user that the target person has not yet seen or rated zero.
• Multiply the other user's rating by their similarity score and accumulate these products into totals.
• Accumulate the similarity scores for each item into a similarity sum dictionary.
• Normalize the list by dividing each accumulated total score by its corresponding total similarity sum.
• Sort the final rankings in descending order and return the top items.

By transforming the preference matrix to swap people and items, recommendation algorithms can be directly applied to find similar products or recommend specific users for items. Inverting a nested dictionary so that items serve as outer keys and people serve as inner values allows the exact same similarity and recommendation functions to match products to products or locate target audiences for marketing. An online retailer identifies books similar to Programming Python by evaluating which shoppers liked particular titles, or predicts which users might purchase clearance items.

You transform the matrix through concrete actions:

• Create an empty result dictionary.
• Iterate through every person in the original preference dictionary.
• Iterate through every item rated by the current person.
• Ensure the item key exists in the result dictionary with an empty sub-dictionary.
• Assign the person's rating into the inverted structure under result[item][person].
• Return the transformed result dictionary.

Item-based collaborative filtering precomputes similarities between items in advance, enabling rapid real-time recommendations for massive user bases where user-based comparisons become too slow. Because relationships between items change much less frequently than comparisons between users, calculating item-to-item similarity datasets during low-traffic periods avoids runtime bottlenecks on high-traffic websites with millions of customers and products. Processing datasets like MovieLens containing 1,682 movies and 943 users becomes instantaneous for end-users once the item similarity matrix is pre-calculated. The MovieLens dataset requires a minimum rating threshold of 20 movies per user.

You compute item similarities programmatically:

• Create an empty result dictionary to store item similarities.
• Invert the user preference matrix to be item-centric using the transformation function.
• Iterate through every item in the inverted preference matrix, providing progress updates for large datasets.
• Find the top matching similar items for each item using distance or correlation metrics.
• Store the resulting similarity scores in the dictionary and return it.

Clustering Algorithms

Hierarchical clustering builds a hierarchy of groups by iteratively calculating distances between every pair and merging the two most similar groups until one remains. Starting with individual items as separate clusters, the algorithm computes pairwise distances, merges the closest pair by averaging their vectors, and caches distance calculations. The resulting tree is visualized using a dendrogram where branch lengths represent distance or error. Distance is calculated as 1.0 minus Pearson correlation, where 0.0 means a perfect match and higher values mean greater distance.

You execute hierarchical clustering through specific actions:

• Read input rows, column names, and row names from a tab-separated data file.
• Initialize each row as an individual bicluster object.
• Loop through every pair of clusters to compute and cache distance metrics using a distance function like Pearson correlation.
• Find the lowest pair distance, merge their vectors by taking the average, and create a new bicluster combining them.
• Repeat the merging process until only a single root cluster remains.

Blogs can be clustered by extracting text entries from RSS feeds, cleaning HTML, splitting words, and building word frequency vectors bounded by frequency percentages. Feeds are parsed using Universal Feed Parser to extract titles and summary descriptions. HTML tags are removed and text is split by non-alphabetical characters into lowercase words. Words appearing in too few or too many feeds are filtered out using upper and lower bound percentages. Blog data was collected for 120 top blogs, such as Gothamist with 3 mentions of kids and music, GigaOM with 6 mentions of china and 2 of yahoo, and Quick Online Tips.

You generate word vectors with exact routines:

• Parse the feed using feedparser.parse(url).
• Extract the entry summary or description.
• Remove HTML tags using regular expressions.
• Split words by all non-alpha characters and convert to lowercase.
• Count word occurrences across all feeds and filter by percentage bounds between 10 percent and 50 percent.
• Write out a tab-separated text file of word frequencies per blog.

The Tanimoto coefficient measures similarity between binary vectors by calculating the ratio of the intersection set to the union set. Useful for sparse datasets containing binary values like 1s and 0s indicating presence or absence, the Tanimoto coefficient computes overlap between items wanted or owned by users, returning a distance metric between 0.0 and 1.0. A distance value of 1.0 indicates nobody who wants the first item wants the second one, while 0.0 indicates exactly the same set of people want both items. Using data from Zebo where users list owned and wanted possessions, clustering items using the Tanimoto coefficient grouped ambitions like boats, planes, and islands, and soul-searchers like friends, love, and happiness.

You calculate the Tanimoto coefficient with these steps:

• Count total active items in vector one, vector two, and their intersection where both vectors are non-zero.
• Return 1.0 minus the ratio of the intersection count divided by the sum of both counts minus the intersection count.

K-means clustering partitions data into a predefined number of clusters by iteratively assigning items to randomly placed centroids and moving centroids to the average location of their assigned members. The algorithm is initialized with k randomly placed centroids within the variable ranges. In each iteration, every item is assigned to its nearest centroid based on a distance metric, and centroids are updated to the average of their assigned members until assignments stop changing. When run on the blog dataset with k equals 10, blogs like The Viral Garden, Copyblogger, Creating Passionate Users, Oilman, ProBlogger Blog Tips, and Seth's Blog grouped together. The k-means clustering loop has a maximum iteration limit set to 100.

You run K-means clustering through specific actions:

• Determine the minimum and maximum values for each column coordinate across all rows.
• Create k randomly placed centroids within those calculated ranges.
• Loop through every row and assign it to the closest centroid based on distance.
• Stop iterating if the current assignments match the assignments from the previous iteration.
• Recalculate each centroid's coordinates as the average of all rows assigned to it.

Multidimensional scaling projects high-dimensional datasets into a two-dimensional chart by iteratively adjusting point locations to minimize the error between target distances and projected distances. The algorithm initializes items randomly in a two-dimensional space, calculates target distances using a metric like Pearson correlation, and measures error terms against current projected distances. Points are pushed or pulled via a learning rate gradient until total error cannot be further reduced. The default learning rate used for updating coordinates is 0.01, and the scaling loop allows a maximum of 1000 iterations.

You perform multidimensional scaling with precise steps:

• Calculate real pairwise distances between every item using a distance function.
• Initialize random 2D coordinates for all items.
• Compute fake projected Euclidean distances between all point pairs in the 2D plane.
• Calculate error terms as percentage differences between fake distances and real distances, accumulating total error.
• Update each point's coordinates by moving it along the gradient proportional to the error and learning rate, stopping if total error increases.

2. Searching, Ranking, and Optimization

Search engines index web text and calculate authority using PageRank, while combinatorial problems are solved by stochastic optimization algorithms minimizing cost functions.

You can build a crawler that parses web pages breadth-first, extracts plain text from HTML, separates words, and stores term locations in an indexed SQLite database.

Static Wikipedia files hosted at kiwitobes.com/wiki were used as a test collection, crawling pages like Perl.html and Open_Directory_Project.html. The basic search engine design supports a maximum page collection size of 100,000. Five primary tables comprise the core database schema for the basic search engine index.

You perform crawler implementation steps:

• Initialize database connection and create tables for urllist, wordlist, wordlocation, link, and linkwords along with indices.
• Crawl a list of starting pages breadth-first up to a given depth, downloading HTML and extracting links.
• Extract text-only nodes recursively from Beautiful Soup objects, preserving paragraph structure.
• Split text into words using regular expressions that treat non-alphanumeric characters as separators and convert to lowercase.
• Store unique URLs and words in lookup tables, and insert word location indices into wordlocation.

Initial search engine relevance and ranking can be computed solely from page content using word frequency, word location, and word distance metrics. Searching for "functional programming" on a wiki dataset returns the correct article first using frequency scoring, and brings up specific language pages when location scoring prioritizes terms in opening sentences.

Search results can be ranked using the anchor text of inbound links, which often provides more accurate descriptions than the destination page itself. Images and pages with sparse text are successfully ranked because external developers provide descriptive link text pointing to them.

The PageRank algorithm computes the global importance of a web page based on the number and quality of inbound links pointing to it. In the Wikipedia dataset, the Main Page achieves the highest PageRank because every other page links to it. The damping factor of 0.85 represents the probability a user continues clicking links, while 0.15 is the minimum baseline value added in the PageRank formula. Twenty iterations are used to calculate stable PageRank values for small datasets.

A multilayer perceptron neural network can learn from user click behavior to improve search result rankings and generalize to unseen queries. After training on queries like "world bank" and "world river" where users selected specific URLs, the network correctly guesses the intent of a novel query for "bank" alone.

Optimization Methods

Stochastic optimization solves complex combinatorial problems by defining a cost function that numerically evaluates how bad a candidate solution is. Planning a group travel itinerary for family members arriving in New York from different cities involves balancing airfare prices, waiting times, and car rental penalties among 1012 (one trillion) possible flight combinations.

You execute optimization tasks through concrete practice items:

• Represent potential solutions as a list of numbers mapped to discrete choices like flight indices.
• Define a cost function that aggregates penalties such as price, wait time, and extra rental fees.
• Execute an optimization algorithm to search for the solution that minimizes this cost.

Hill climbing optimization improves upon random search by inspecting neighboring solutions and moving iteratively in the direction of steepest cost reduction. Applying hill climbing to flight schedules quickly finds a lower cost than random guessing by adjusting one person's flight at a time.

Simulated annealing avoids local minima by occasionally accepting worse solutions early in the search process according to a declining temperature schedule. Annealingoptimize successfully reduces overall wait times and costs for the group travel itinerary by exploring varied schedule adjustments. Default parameters include a starting temperature of 10000.0 and a cooling rate of 0.95.

Genetic algorithms optimize complex problems by evolving a population of candidate solutions through selection, elitism, mutation, and crossover. They are widely used across industries, from designing supersonic aircraft wings and antenna shapes to discovering drug candidate chemical libraries. Default settings use a population size of 50, a mutation probability of 0.2, an elite fraction of 0.2, and 100 maximum iterations.

Real flight search data from APIs can be integrated into optimization algorithms to find ideal travel schedules. You optimize flights for the Glass family using actual Kayak search data between cities like Boston (BOS), New York (LGA), and Dallas (DAL).

Resource allocation problems with expressed preferences can be solved using optimization by representing solutions as valid slot selections. You assign 10 students with first and second choices to 5 dorms, each having 2 available spaces, exploring 100000 possible solutions.

Network diagram layouts can be optimized to produce clean, readable visuals by minimizing the number of intersecting connection lines. You optimize network coordinates for a group of people including Charlie, Augustus, Veruca, Violet, Mike, Joe, Willy, and Miranda to reduce crossed lines from 12 down to 1.

3. Document Filtering and Decision Trees

Naive Bayesian and Fisher classifiers categorize text documents using feature probabilities, and CART decision trees construct human-interpretable models via entropy minimization.

Spam filters and text classifiers operate by extracting features from documents, where words serve as the primary indicators. By splitting text on non-alphanumeric characters, converting words to lowercase, and tracking their frequencies across different categories, a system learns which terms correlate with specific classifications.

Classifying incoming text or filtering out unsolicited commercial email messages by analyzing word frequency.

• Create a file called docclass.py and import re and math.
• Define a getwords function that uses a regular expression splitter to divide text by non-alpha characters, filters words by length, and returns a unique set dictionary.
• Create a classifier class storing feature-category counts (fc) and category document counts (cc).
• Implement training methods to increment feature and category counts based on ingested documents.

The minimum character length for extracted words is 2, while the maximum character length is 20.

By calculating conditional probabilities for words within categories and applying weighted smoothing to handle rare words, the classifier multiplies individual probabilities together. Combined with Bayes' Theorem, it allows the comparison of category scores to determine the most likely classification while supporting thresholds to prevent false positives.

Classifying the phrase quick money as bad while requiring a higher threshold ratio to avoid misclassifying good messages.

• Implement a weightedprob method in the classifier class to compute a weighted average between basic probability and an assumed probability.
• Create a naivebayes subclass featuring a docprob method that multiplies all feature probabilities together.
• Add a prob method combining document probability with category prior probability.
• Add setthreshold and classify methods to evaluate category scores against required margins before assigning a category.

The assumed initial probability for weighted probability calculations is 0.5, and 3.0 serves as an example threshold multiplier required for classifying messages as bad.

Unlike the naïve Bayes approach, the Fisher method computes the probability of a category given a feature under the assumption of equal category distribution. It multiplies these probabilities, takes the natural log, multiplies by -2, and feeds the resulting score into an inverse chi-square function to yield a rigorous probability score.

Scoring phrases like quick rabbit and quick money using fisherprob to yield precise floating-point metrics between 0 and 1.

• Create a fisherclassifier subclass inheriting from classifier.
• Implement a cprob method to calculate normalized category probability given a feature assuming equal category sizes.
• Implement a fisherprob method that multiplies feature probabilities, multiplies the natural log by -2, and calls invchi2.
• Implement an invchi2 method using exponential expansion to return a probability score.
• Add setminimum and classify methods to enforce lower bounds for category assignments.

The multiplier applied to the natural log of combined probabilities in the Fisher score is -2, and 0.6 is an example minimum cutoff bound set for the bad classification category.

Decision Trees

Decision trees produce a series of if-then statements that are fully interpretable. The algorithm measures disorder using Gini impurity or entropy, computes information gain for every attribute split, and recursively builds branches until information gain drops to zero or below.

Predicting whether web site users who sign up for a free trial will become paying customers based on referrer, location, FAQ reading, and pages viewed.

• Arrange the data in a list of rows, with each row being a list of columns, and the final column being the target value.
• Create a decisionnode class with instance variables col, value, results, tb, and fb.
• Use divideset to split rows into two sets based on numerical or nominal column criteria.
• Calculate split quality using uniquecounts and entropy or giniimpurity.
• Recursively call buildtree to find the best attribute and construct branches.

The Gini impurity for the entire example user dataset is 0.6328125, entropy is 1.5052408149441479, and entropy after dividing the user dataset on the Read FAQ column is 1.2987949406953985.

Overfitted trees create branches that decrease training set entropy slightly via arbitrary conditions. Pruning checks pairs of sibling leaf nodes and merges them back into a single node if the resulting increase in entropy stays below a specified threshold.

Testing pruning with a mingain parameter of 0.1 and 1.0 on the user signup decision tree.

• Traverse down the tree to nodes whose children are leaves.
• Create a combined list of results from both leaf nodes.
• Test the reduction in entropy when merging the leaves.
• If the change in entropy is less than mingain, delete the leaves and move results to the parent node.

The minimum gain threshold that leaves clean tree splits unaffected is 0.1, whereas 1.0 is a high minimum gain threshold that forces leaf merging.

Treating numbers as discrete categories fails because it ignores numerical distance. Using statistical variance allows the algorithm to pick splits that group higher values on one side and lower values on the other, lowering overall branch variance.

Modeling real estate prices using property attributes and Zillow data, where bathrooms splits the dataset.

• Extract the numerical outcome from the final column of each row.
• Calculate the mean value for the set.
• Sum the squared differences from the mean and divide by the total number of rows to get variance.

4. Advanced Classification and Evolving Intelligence

Kernel methods and support-vector machines separate complex classes using the kernel trick, and non-negative matrix factorization extracts hidden themes from data.

Standard linear classifiers fail when classes encircle each other or have curved boundaries. Instead of explicitly calculating transformations into hundreds of dimensions, the kernel trick replaces dot-products with a kernel function like the radial-basis function, which computes what the dot-product would be in the higher-dimensional space.

Classifying dating matches with curved age boundaries accurately by passing the data through nlclassify using the radial-basis function.

• Calculate the distance vector and apply the radial-basis function formula using rbf.
• Compute the offset value for the transformed dataset using getoffset.
• Classify new data points using nonlinear classification via nlclassify.

The 20 is the default gamma parameter value in rbf.

Standard linear average classifiers can be skewed by outlier points close to the boundary. Support-vector machines isolate support vectors near the margin to construct a robust dividing line. Because training an SVM is computationally intensive, third-party libraries like LIBSVM are used to manage training, cross-validation, and kernel application.

Using LIBSVM's python wrapper to train a radial-basis function model on the matchmaker dataset and predict match outcomes using svm_model and svm_parameter.

• Import the svm module from LIBSVM.
• Create a training problem instance using svm_problem with answers and inputs.
• Specify the kernel type and parameters using svm_parameter, then train the model with svm_model.
• Predict new classes using the predict method or cross-validate using cross_validation.

The 4 is the subset count used in cross_validation for the matchmaker dataset, and 500 is the total number of rows in the matchmaker dataset.

Social networking APIs can be integrated to construct real-world classification datasets by querying user profiles and friendship links. The Facebook API requires establishing a session through token creation, user login via browser, and session key retrieval.

Using the fbsession class in facebook.py to authenticate, fetch user friend IDs, retrieve profile info, and query facebook.friends.areFriends to build an SVM dataset.

• Initialize an fbsession to create a token, open the login page, and retrieve the session key.
• Send requests with hashed signatures using makehash and sendrequest.
• Retrieve friend IDs using getfriends and profile details using getinfo.
• Determine if pairs of users are friends using arefriends and assemble rows using makedataset.

The 20 is the minimum number of connections recommended for testing, and the block size increment used when querying friend pairs.

Matrix Factorization and Genetic Programming

Non-Negative Matrix Factorization extracts underlying themes or independent features from unlabelled datasets by decomposing a high-dimensional observation matrix into two smaller, non-negative matrices representing features and weights.

By multiplying a features matrix and a weights matrix, the original matrix is reconstructed. The non-negative constraint ensures all values are positive or zero, preventing features from cancelling each other out.

Applied to Yahoo! Finance and stock volumes, NMF successfully identified specific dates and stocks like Yahoo! or Google where volume spiked due to corporate earnings announcements or policy statements.

• Create a big matrix of numbers with rows as items and columns as properties
• Initialize weight and feature matrices with random values
• Iteratively calculate the cost using the difference function
• Update the feature and weight matrices using multiplicative update rules
• Extract the top weighted words per feature and top associated rows per weight

The 10 pc is the initial component count specified for factorize, 50 is the maximum number of iterations specified in the basic factorize loop, and 0.6 is the upper percentage limit of total articles used to filter out overly common words.

Stock trading volume is better suited for positive matrix factorization than closing prices because volume typically maintains a basal level that increases in response to outside influence.

Yahoo! stock volume showed a massive spike on July 19, 2006, the day it issued earnings guidance, while Google volume spiked on January 20, 2006, when it announced it would not give search engine usage data to the government.

• Download historical stock volume and price data in CSV format from Yahoo! Finance
• Extract the volume field from every CSV line for a list of ticker symbols
• Construct a matrix where rows are days and columns are trading volumes for specific stocks
• Execute the NMF factorize function specifying the number of features to search for

The 300 represents the shortest number of days recorded among the tested stocks, and 14,666,100 shares was the trading volume for Yahoo! on December 22, 2006.

Genetic programming automatically constructs optimal computer programs to solve specific tasks by evolving a population of programs represented as parse trees through selection, mutation, and crossover. Programs are encoded as trees containing function nodes, parameter nodes, and constant nodes to guarantee valid execution structure.

Genetic programming has been used to design antennas for NASA, photonic crystals, quantum computing systems, and automated chess and backgammon players.

• Define a tree representation using function wrapper, node, paramnode, and constnode classes
• Generate an initial population of random program trees using makerandomtree
• Evaluate program performance against a dataset using a score function
• Rank the population from best to worst using a fitness or rank function
• Apply elitism, mutation, and crossover to breed the next generation until a stopping criterion is reached

The 500 is the default maximum number of generations in the evolve function, 0.1 is the default mutation rate probability, and 0.4 is the default breeding rate probability.

Genetic programming relies on mutation and crossover to modify top-performing program trees. Mutation replaces a randomly selected subtree with a newly generated random tree based on a set probability.

Crossing over two randomly generated program trees for a mathematical formula produced a combined tree that was subsequently scored and evaluated for fitness.

• Traverse down the tree during mutation and check if a random number falls below the mutation probability
• Replace the subtree with a newly generated random tree when the mutation threshold is met
• Traverse two parent trees simultaneously during crossover
• Swap a selected branch from the first tree with a branch from the second tree based on the breeding probability

The 0.1 is the default probability that any given node will be modified during mutation, and 0.7 is the default probability threshold used during tree crossover.

Maintaining population diversity by mixing top solutions with moderately good or entirely new random programs prevents genetic programming from getting stuck in local maxima.

The evolve function utilizes logarithmic selection indices and probability parameters to allow weaker solutions and novel random trees into subsequent generations.

• Pass the population through a ranking function to score all programs
• Preserve the top two performing programs unaltered via elitism
• Select parent programs for breeding using a selection index weighted by a lower probability exponent
• Introduce completely new random programs into the population based on the new program probability threshold

The 0.05 is the default probability for introducing a completely new, random program, and 0.7 is the default parameter value controlling the decline rate in selecting lower-ranked programs.

10 Key Ideas

1. Collaborative filtering algorithms match users and items using similarity metrics like Euclidean distance and Pearson correlation, while unsupervised clustering groups unstructured data.
2. Item-based collaborative filtering precomputes similarities between items in advance, enabling rapid real-time recommendations for massive user bases where user-based comparisons become too slow.
3. Hierarchical clustering builds a hierarchy of groups by iteratively calculating distances between every pair and merging the two most similar groups until one remains.
4. The PageRank algorithm computes the global importance of a web page based on the number and quality of inbound links pointing to it.
5. Stochastic optimization solves complex combinatorial problems by defining a cost function that numerically evaluates how bad a candidate solution is.
6. Naive Bayesian and Fisher classifiers categorize text documents using feature probabilities, and CART decision trees construct human-interpretable models via entropy minimization.
7. Kernel methods and support-vector machines separate complex classes using the kernel trick, and non-negative matrix factorization extracts hidden themes from data.
8. Non-Negative Matrix Factorization extracts underlying themes or independent features from unlabelled datasets by decomposing a high-dimensional observation matrix into two smaller, non-negative matrices representing features and weights.
9. Genetic programming automatically constructs optimal computer programs to solve specific tasks by evolving a population of programs represented as parse trees through selection, mutation, and crossover.
10. Maintaining population diversity by mixing top solutions with moderately good or entirely new random programs prevents genetic programming from getting stuck in local maxima.