Machine Learning

Introduction

Jeff Howbert Introduction to Machine Learning Winter 2014 1

 Machine learning

Broad definition:
Automated discovery of patterns in data by a
computer.

This is learning, because computer is given an

initial pattern-recognition model and some data,
and figures out how to make the model better.
This is machine, because computer learns
automatically, without intervention from humans
(other than selection of initial model and data).

Jeff Howbert Introduction to Machine Learning Winter 2014 2

 Why is machine learning
important?

 Data in many domains is huge

– Thousands to billions of data samples
– Hundreds to millions of attributes
– Impossible for human analysts to see patterns across
so much data
 Patterns in many domains are subtle, weak, buried in
noise, or involve complex interactions of attributes
– Often very difficult for human analysts to find
 In some domains discovery and use of patterns must
happen in real time, e.g. in streaming data
– Human analysts could never keep up

Jeff Howbert Introduction to Machine Learning Winter 2014 3

 Machine learning applications (1)

 Commercial
– Targeted marketing: understand purchasing
patterns of individuals or groups
 web-based advertising
– Recommender systems: help people find
items they will like
– Fraud detection
 Finance

– Predict movements in markets

– Portfolio risk management
Jeff Howbert Introduction to Machine Learning Winter 2014 4
 Machine learning applications (2)

 Natural language processing

– Speech recognition
– Machine translation
– Document classification and retrieval (books,
email, web pages)
– Sentiment analysis
 Computer vision

– Optical character recognition

– Face recognition
– Image classification and retrieval
Jeff Howbert Introduction to Machine Learning Winter 2014 5
 Machine learning applications (3)

 IT
– Network intrusion detection
– Spam filtering

 Robotics

 Manufacturing process control

 Social media

Jeff Howbert Introduction to Machine Learning Winter 2014 6

 Machine learning applications (4)

 Scientific
– Remote sensing networks:
atmosphere, ocean, fresh-water,
land-based, satellite
 weather and climate modeling
 environmental management

 resource management

– Biomedical: gene sequencing,

gene expression, epidemiology,
disease prediction
Jeff Howbert Introduction to Machine Learning Winter 2014 7
 Machine learning careers

 A.k.a. predictive analytics, business analytics, data

mining, data science, quantitative modeling
 Demand continues to outstrip supply
 Not necessary to have Ph.D.
 For every “analyst” position, there are several tightly
allied positions in software dev, engineering, databases,
cloud, etc.
 In demand with local employers
– Amazon, Google, Microsoft, Facebook, Zillow
– Fred Hutchinson Cancer Research Center, many labs
at University of Washington
– Many smaller companies, including startups
Jeff Howbert Introduction to Machine Learning Winter 2014 8
 Related and overlapping fields
 Machine learning is coalescence of ideas drawn from artificial
intelligence, pattern recognition, statistics, and data mining
 These days:
– Pattern recognition
pattern
and machine learning statistics
recognition
essentially the same
– Data mining is machine
machine
learning plus large-scale learning
data retrieval methods
– Machine learning is one artificial
data mining intelligence
of the hot research frontiers
in statistics

Jeff Howbert Introduction to Machine Learning Winter 2014 9

 Stages of knowledge extraction

Interpretation /
evaluation
Knowledge
Knowledge
Machine
learning

Transformation Patterns

Preprocessing
Transformed
data

Selection Preprocessed
data
Data Target
data

Jeff Howbert Introduction to Machine Learning Winter 2014 10

 Types of machine learning

 Supervised methods (“predictive”)

– Build a predictive model from examples of
data with known outcomes.
– Use model to predict outcomes for unknown
or future examples.

 Unsupervised methods (“descriptive”)

– Discover structure in data for which
outcomes are not known.

Jeff Howbert Introduction to Machine Learning Winter 2014 11

 Jeff Howbert
January 19, 2026 Introduction to Machine Learning Winter
122014 12
 Jeff Howbert
January 19, 2026 Introduction to Machine Learning Winter
132014 13
 Jeff Howbert
January 19, 2026 Introduction to Machine Learning Winter
142014 14
 Jeff Howbert
January 19, 2026 Introduction to Machine Learning Winter
152014 15
 Jeff Howbert
January 19, 2026 Introduction to Machine Learning Winter
162014 16
 Machine learning tasks

Supervised We will cover tasks

highlighted in red
– Classification
– Regression
– Recommender systems
– Reinforcement learning
Unsupervised
– Clustering
– Association analysis

 Ranking
 Anomaly detection
Jeff Howbert Introduction to Machine Learning Winter 2014 17
 Classification definition

 Given a collection of records (training set)

– Each record contains a set of attributes.
– Each record also has a discrete class label.
 Learn a model that predicts class label as a
function of the values of the attributes.
 Goal: model should assign class labels to
previously unseen records as accurately as
possible.
– A test set is used to determine the accuracy of the
model. Usually, the given data set is divided into
training and test sets, with training set used to build
the model and test set used to validate it.

Jeff Howbert Introduction to Machine Learning Winter 2014 18

 Classification illustrated
Refund Marital Taxable
cal cal us Status Income Cheat
i i o
gor gor i nu
a te a te ont ass No Single 75K ?
c c c cl
Tid Refund Marital Taxable Yes Married 50K ?
Status Income Cheat
No Married 150K ?
1 Yes Single 125K No Yes Divorced 90K ?
2 No Married 100K No No Single 40K ?
3 No Single 70K No Training No Married 80K ?
set
10

4 Yes Married 120K No

Test
5 No Divorced 95K Yes set
6 No Married 60K No
7 Yes Divorced 220K No
Learn
8 No Single 85K Yes
classifier Model
9 No Married 75K No
10 No Single 90K Yes
Predicted
10

classes

Jeff Howbert Introduction to Machine Learning Winter 2014 19

 Classification application 1

 Direct marketing
– Goal: Reduce cost of mailing by targeting a set of
customers likely to buy a new cell-phone product.
– Approach:
 Use the data for a similar product introduced before.
 We know which customers decided to buy and which
decided otherwise. This {buy, don’t buy} decision forms the
class label.
 Collect various demographic, lifestyle, and company-
interaction related information about all such customers.
– Type of business, where they stay, how much they earn, etc.
 Usethis information as input attributes to learn a classifier
model.
From [Berry & Linoff] Data Mining Techniques, 1997

Jeff Howbert Introduction to Machine Learning Winter 2014 20

 Classification application 2

 Customer attrition:
– Goal: To predict whether a customer is likely
to be lost to a competitor.
– Approach:
 Use detailed record of transactions with each of the
past and present customers, to find attributes.
– How often the customer calls, where he calls, what time-
of-the day he calls most, his financial status, marital
status, etc.
 Label the customers as loyal or disloyal.
 Find a model for loyalty.

From [Berry & Linoff] Data Mining Techniques, 1997

Jeff Howbert Introduction to Machine Learning Winter 2014 21

 Classification application 3

 Sky survey cataloging

– Goal: To predict whether a sky object is a star or a
galaxy (class), especially visually faint ones, based on
telescopic survey images from Palomar Observatory.
– 3000 images with 23,040 x 23,040 pixels per image.
– Approach:
 Segment the image.
 Measure image attributes (features) - 40 of them per object.
 Model the class based on these features.
 Success story: Found 16 new high red-shift quasars – very
distant objects, very difficult to identify.

From [Fayyad, [Link].] Advances in Knowledge Discovery and Data Mining, 1996

Jeff Howbert Introduction to Machine Learning Winter 2014 22

 Classification application 4
Classify galaxies according to stage of formation:
early, intermediate, or late
Early
Attributes:
• Image features
• Characteristics of light
Intermediate waves received
• etc.

Late

Data size:
• 72 million stars, 20 million galaxies
• Object catalog: 9 GB
• Image database: 150 GB
Courtesy: [Link]
Jeff Howbert Introduction to Machine Learning Winter 2014 23
 Classification application 5
C-Path: automated pathologic grading
of breast cancer specimens

 Started with 6642 high-level features

per image
 Features characterized both malignant
epithelium and surrounding stroma
 Algorithm simultaneously selected
small subset of features and learned to
discriminate 5-year survivors from non-
survivors
 Final model: 11 features, 89%
accuracy on predicting 5-year survival
Science Translational Medicine, 3, 108ra113, 2011

Jeff Howbert Introduction to Machine Learning Winter 2014 24

 Stages in a classification task

Tid Attrib1 Attrib2 Attrib3 Class Learning

No
1 Yes Large 125K
algorithm
2 No Medium 100K No

3 No Small 70K No
4 Yes Medium 120K No
Induction
5 No Large 95K Yes
6 No Medium 60K No

7 Yes Large 220K No Learn

8 No Small 85K Yes Model
9 No Medium 75K No
10 No Small 90K Yes
Model
10

Training Set
Apply
Tid Attrib1 Attrib2 Attrib3 Class Model
11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ? Deduction

14 No Small 95K ?

15 No Large 67K ?
10

Test Set

Jeff Howbert Introduction to Machine Learning Winter 2014 25

 Examples of classification tasks

 Two classes
– Predicting tumor cells as benign or malignant
– Classifying credit card transactions
as legitimate or fraudulent

 Multiple classes
– Classifying secondary structures of
protein as alpha-helix, beta-sheet,
or random coil
– Categorizing news stories as finance,
weather, entertainment, sports, etc

Jeff Howbert Introduction to Machine Learning Winter 2014 26

 Classification techniques

 Decision trees
 Rule-based methods
 Logistic regression
 Discriminant analysis
 k-Nearest neighbor (instance-based learning)
 Naïve Bayes
 Neural networks
 Support vector machines
 Bayesian belief networks

Jeff Howbert Introduction to Machine Learning Winter 2014 27

 Example of a decision tree

nal nal s
i i
om om atio l as splitting nodes
n n r c
Tid Refund Marital Taxable
Status Income Cheat

1 Yes Single 125K No Refund

Yes No
2 No Married 100K No
3 No Single 70K No NO MarSt
4 Yes Married 120K No
Single, Divorced Married
5 No Divorced 95K Yes
6 No Married 60K No TaxInc NO
7 Yes Divorced 220K No < 80K > 80K
8 No Single 85K Yes
NO YES
9 No Married 75K No
10 No Single 90K Yes
10

classification nodes

training data model: decision tree

Jeff Howbert Introduction to Machine Learning Winter 2014 28

 Another example of decision tree

nal nal
m
i
m
i
tio ass
no no r a cl MarSt Single,
Married Divorced
Tid Refund Marital Taxable
Status Income Cheat
NO Refund
1 Yes Single 125K No
Yes No
2 No Married 100K No
3 No Single 70K No NO TaxInc
4 Yes Married 120K No < 80K > 80K
5 No Divorced 95K Yes
NO YES
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No There can be more than one tree
10 No Single 90K Yes that fits the same data!
10

Jeff Howbert Introduction to Machine Learning Winter 2014 29

 Clustering definition

 Given:
– Set of data points
– Set of attributes on each data point
– A measure of similarity between data points
 Find clusters such that:
– Data points within a cluster are more similar to one
another
– Data points in separate clusters are less similar to
one another
 Similarity measures:
– Euclidean distance if attributes are continuous
– Other problem-specific measures

Jeff Howbert Introduction to Machine Learning Winter 2014 30

 Types of clustering

 Partitional
– Data points divided into finite number of
partitions (non-overlapping subsets)

 Hierarchical
– Data points arranged in tree structure that
expresses a continuum of similarities and
clustering

Jeff Howbert Introduction to Machine Learning Winter 2014 31

 Partitional clustering illustrated

Euclidean distance based clustering in 3D space

Intracluster
Intraclusterdistances
distances
are
areminimized
minimized

Assign to
clusters

Intercluster
Interclusterdistances
distances
are
aremaximized
maximized
Jeff Howbert Introduction to Machine Learning Winter 2014 32
 Hierarchical clustering illustrated

Driving distances between Italian cities

Jeff Howbert Introduction to Machine Learning Winter 2014 33

 Clustering application 1

 Market segmentation
– Goal: subdivide a market into distinct subsets of
customers, such that each subset is conceivably a
submarket which can be reached with a customized
marketing mix.
– Approach:
 Collect different attributes of customers based on their
geographical and lifestyle related information.
 Find clusters of similar customers.
 Measure the clustering quality by observing buying
patterns of customers in same cluster vs. those from
different clusters.

Jeff Howbert Introduction to Machine Learning Winter 2014 34

 Clustering application 2

 Document clustering
– Goal: Find groups of documents that are
similar to each other based on the important
terms appearing in them.
– Approach: Identify frequently occurring terms
in each document. Form a similarity measure
based on the frequencies of different terms.
Use it to cluster.
– Benefit: Information retrieval can utilize the
clusters to relate a new document or search
term to clustered documents.
Jeff Howbert Introduction to Machine Learning Winter 2014 35
 Document clustering example

 Items to cluster: 3204 articles of Los Angeles Times.

 Similarity measure: Number of words in common
between a pair of documents (after some word filtering).
Category Total Correctly
Articles Placed
Financial 555 364

Foreign 341 260

National 273 36

Metro 943 746

Sports 738 573

Entertainment 354 278

Jeff Howbert Introduction to Machine Learning Winter 2014 36

 Clustering application 3

 Image segmentation with mean-shift algorithm

 Allows clustering of pixels in combined (R, G, B)
plus (x, y) space

Jeff Howbert Introduction to Machine Learning Winter 2014 37

 Clustering application 4

 Genetic demography

Jeff Howbert Introduction to Machine Learning Winter 2014 38

 Types of clusters

 Well-separated clusters
 Center-based clusters
 Contiguous clusters
 Density-based clusters
 Property or conceptual
 Described by an objective function

Jeff Howbert Introduction to Machine Learning Winter 2014 39

 Clustering algorithms

 k-Means and its variants

 Hierarchical clustering

 Density-based clustering

Jeff Howbert Introduction to Machine Learning Winter 2014 40

 Association rule definition

 Given:
– set of records each of which contain some number of
items from a given collection
 Produce dependency rules which will predict occurrence
of an item based on occurrences of other items.

TID Items
1 Bread, Coke, Milk
Rules
RulesDiscovered:
Discovered:
2 Beer, Bread
{Milk}
{Milk}-->
-->{Coke}
{Coke}
3 Beer, Coke, Diaper, Milk {Diaper,
{Diaper,Milk}
Milk}-->
-->{Beer}
{Beer}
4 Beer, Bread, Diaper, Milk
5 Coke, Diaper, Milk

Jeff Howbert Introduction to Machine Learning Winter 2014 41

 Association rule application

 Supermarket shelf management

– Goal: Identify items that are bought together
by sufficiently many customers.
– Approach: Process the point-of-sale data
collected with barcode scanners to find
dependencies among items.
– A classic rule …
 If a customer buys diaper and milk, then he is very
likely to buy beer.
 So don’t be surprised if you find six-packs stacked

next to diapers!
Jeff Howbert Introduction to Machine Learning Winter 2014 42
 Mining Association Rules in Large
Databases

 Association rule mining

 Algorithms for scalable mining of (single-
dimensional Boolean) association rules in
transactional databases
 Mining various kinds of association/correlation
rules
 Constraint-based association mining
 Sequential pattern mining
 Applications/extensions of frequent pattern
mining
 Summary

44
Jeff Howbert Introduction to Machine Learning Winter 2014 44
 What Is Association Mining?
 Association rule mining:
– Finding frequent patterns, associations, correlations, or causal
structures among sets of items or objects in transaction
databases, relational databases, and other information
repositories.
– Frequent pattern: pattern (set of items, sequence, etc.) that
occurs frequently in a database [AIS93]
 Motivation: finding regularities in data
– What products were often purchased together? — Beer and
diapers?!
– What are the subsequent purchases after buying a PC?
– What kinds of DNA are sensitive to this new drug?
– Can we automatically classify web documents?

45

Jeff Howbert Introduction to Machine Learning Winter 2014 45

 Why Is Association Mining
Important?

 Foundation for many essential data mining tasks

– Association, correlation, causality
– Sequential patterns, temporal or cyclic association,
partial periodicity, spatial and multimedia association
– Associative classification, cluster analysis, iceberg
cube, fascicles (semantic data compression)
 Broad applications
– Basket data analysis, cross-marketing, catalog
design, sale campaign analysis
– Web log (click stream) analysis, DNA sequence
analysis, etc.

46

CS590D
Jeff Howbert Introduction to Machine Learning Winter 2014 46
 Basic Concepts: Association Rules

Transaction-id Items bought  Itemset X={x1, …, xk}

10 A, B, C  Find all the rules XY with min
confidence and support
20 A, C
– support, s, probability that
30 A, D a transaction contains
XY
40 B, E, F
– confidence, c, conditional
Customer
probability that a
Customer transaction having X also
buys both buys diaper contains Y.
Let min_support = 50%,
min_conf = 50%:
A  C (50%, 66.7%)
C  A (50%, 100%)
Customer 47
buys beer
Jeff Howbert Introduction to Machine Learning Winter 2014 47
Mining Association Rules: Example

Transaction-id Items bought

Min. support 50%
10 A, B, C
Min. confidence 50%
20 A, C Frequent pattern Support
30 A, D {A} 75%
40 B, E, F {B} 50%
{C} 50%
{A, C} 50%
For rule A  C:
support = support({A}{C}) = 50%
confidence = support({A}{C})/support({A}) =
66.6%
48

Jeff Howbert Introduction to Machine Learning Winter 2014 48

 Sequential pattern definition

 Given is a set of objects, with each object associated with its own timeline of events, find rules that predict strong sequential dependencies among
different events.

 Rules are formed by first discovering patterns. Event occurrences in the patterns are governed by timing constraints.

(A B) (C) (D E)

(A B) (C) (D E)
<= xg >ng <= ws

<= ms

Jeff Howbert Introduction to Machine Learning Winter 2014 49

 Sequential pattern applications

 Telecommunications alarm logs

(Inverter_Problem Excessive_Line_Current)
(Rectifier_Alarm) --> (Fire_Alarm)

 Point-of-sale transaction sequences

Computer Bookstore:
(Intro_To_Visual_C) (C++_Primer) -->
(Perl_for_dummies,Tcl_Tk)
Athletic Apparel Store:
(Shoes) (Racket, Racketball) --> (Sports_Jacket)

Jeff Howbert Introduction to Machine Learning Winter 2014 50

 Regression definition
 Given a collection of records (training set)
– Each record contains a set of attributes.
– Each record also has a continuous response variable.
 Learn a model that predicts response variable
as a function of the values of the attributes.
– Model can be linear or nonlinear.
 Goal: model should predict value of response
variable on previously unseen records as
accurately as possible.
– Usually, the given data set is divided into training and
test sets, with training set used to build the model and
test set used to test its accuracy.

Jeff Howbert Introduction to Machine Learning Winter 2014 51

 Regression application 1

 Estimate market value of homes

– Data from multiple sources
 Physical attributes
 Tax assessments

 Prior sale prices

– Data from home of

interest, plus homes
in same neighbor-
hood, city, state

Jeff Howbert Introduction to Machine Learning Winter 2014 52

 Regression applications 2
 Predict voting patterns in
elections.
 Predict sales volume
of new product based
on advertising
expenditure.
 Predict weather patterns
as a function of
temperature, humidity,
air pressure, etc.
 Time series
prediction of stock
market indices.
Jeff Howbert Introduction to Machine Learning Winter 2014 53
 Recommender system definition

DOMAIN: some field of activity where users buy,

view, consume, or otherwise experience items

PROCESS:
1. users provide ratings on items they have
experienced
2. Take all < user, item, rating > data and build a
predictive model
3. For a user who hasn’t experienced a particular
item, use model to predict how well they will
like it (i.e. predict rating)
Jeff Howbert Introduction to Machine Learning Winter 2014 54
 Recommender system application
1

[Link] product recommendations

Jeff Howbert Introduction to Machine Learning Winter 2014 55

 Recommender system application
2

Netflix viewing recommendations

Jeff Howbert Introduction to Machine Learning Winter 2014 56

 Recommender system application
3

 Social network recommendations of essentially every

category of interest known to mankind
– Friends
– Groups
– Activities
– Media (TV shows, movies, music, books)
– News stories
– Ad placements
 All based on connections in underlying social network
graph and the expressed ‘likes’ / ’dislikes’ of yourself and
your connections

Jeff Howbert Introduction to Machine Learning Winter 2014 57

 Anomaly detection
 Detect significant deviations from normal behavior

 Applications:
– Credit card fraud detection

– Network intrusion
detection

Typical network traffic at University level may reach over 100 million connections per
day
Jeff Howbert Introduction to Machine Learning Winter 2014 58
 Anomaly detection

Anomalies and outliers

are essentially
the same thing:

objects that are different from most other objects

The techniques used for detection are the same.

Jeff Howbert Introduction to Machine Learning Winter 2014 59

 Anomaly detection

 Historically, the field of statistics tried to find and

remove outliers as a way to improve analyses.

 There are now many fields where the outliers /

anomalies are the objects of greatest interest.
– The rare events may be the ones with the
greatest impact, and often in a negative way.

Jeff Howbert Introduction to Machine Learning Winter 2014 60

 Causes of anomalies

 Data from different class of object or underlying

mechanism
– disease vs. non-disease
– fraud vs. not fraud

 Natural variation
– tails on a Gaussian distribution

 Data measurement and collection errors

Jeff Howbert Introduction to Machine Learning Winter 2014 61

 Structure of anomalies

 Point anomalies

 Contextual anomalies

 Collective anomalies

Jeff Howbert Introduction to Machine Learning Winter 2014 62

 Applications of anomaly detection

 Network intrusion
 Insurance / credit card fraud
 Healthcare informatics / medical diagnostics
 Industrial damage detection
 Image processing / video surveillance
 Novel topic detection in text mining
…

Jeff Howbert Introduction to Machine Learning Winter 2014 63

 Techniques for anomaly detection

 Statistical

 Proximity-based

 Density-based

 Clustering-based

[ following slides illustrate these techniques for

unsupervised detection of point anomalies ]
Jeff Howbert Introduction to Machine Learning Winter 2014 64
 Challenges of machine learning

 Data often has poorly understood structure

– Best modeling approach rarely obvious at start
 Heterogeneous data types
– e.g. combination of text, images, and numeric data
 Frequent class imbalance
 Noisy or corrupted data
 Missing or incomplete data
 High dimensionality
 Scaling of algorithms to massive data sets
 Streaming (real-time) data
Jeff Howbert Introduction to Machine Learning Winter 2014 65