Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Problem Statement
• Problem: The Department of Elementary and Secondary
Education (DESE) in MA classifies Grade 10 mathematics
questions into 4 types:
Algebra (A)
Geometry (G)
Number and Quantity (N)
Probability and Statistics (P)
Does this classification make sense? Can we come up with a
new cluster that is ”better” than DESE’s?
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Problem Statement
• Problem: The Department of Elementary and Secondary
Education (DESE) in MA classifies Grade 10 mathematics
questions into 4 types:
Algebra (A)
Geometry (G)
Number and Quantity (N)
Probability and Statistics (P)
Does this classification make sense? Can we come up with a
new cluster that is ”better” than DESE’s?
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Evaluation Plan
• Data: N = 70000 students, Q
a
= 32 multiple choice
questions - imagine a matrix of size N by 32.
• Evaluation: Randomly pick 6 questions as holdout sample
Q
h
. Let DESE’s cluster be {C
i
}
4
i=1
and our cluster be {C
0
j
}
m
j=1
.
For each student s, compute:
True average score in 6 hold out sample: ¯y
s
=
1
|Q
h
|
P
Q
d
sq
Baseline: ¯y
0
s
=
1
|Q
h
|
P
Q
h
P
4
i=1
a
si
q∈C
i
Our Prediction: ˜y
s
=
1
|Q
h
|
P
Q
h
P
m
j=1
a
sj
0
q∈c
0
j
Finally, we compare the MSE:
MSE
1
= (¯y
s
− ¯y
0
s
)
2
MSE
2
= (¯y
s
− ˜y
0
s
)
2
if MSE
2
< MSE
1
, we win!
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Evaluation Plan
• Data: N = 70000 students, Q
a
= 32 multiple choice
questions - imagine a matrix of size N by 32.
• Evaluation: Randomly pick 6 questions as holdout sample
Q
h
. Let DESE’s cluster be {C
i
}
4
i=1
and our cluster be {C
0
j
}
m
j=1
.
For each student s, compute:
True average score in 6 hold out sample: ¯y
s
=
1
|Q
h
|
P
Q
d
sq
Baseline: ¯y
0
s
=
1
|Q
h
|
P
Q
h
P
4
i=1
a
si
q∈C
i
Our Prediction: ˜y
s
=
1
|Q
h
|
P
Q
h
P
m
j=1
a
sj
0
q∈c
0
j
Finally, we compare the MSE:
MSE
1
= (¯y
s
− ¯y
0
s
)
2
MSE
2
= (¯y
s
− ˜y
0
s
)
2
if MSE
2
< MSE
1
, we win!
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Evaluation Plan
• Data: N = 70000 students, Q
a
= 32 multiple choice
questions - imagine a matrix of size N by 32.
• Evaluation: Randomly pick 6 questions as holdout sample
Q
h
. Let DESE’s cluster be {C
i
}
4
i=1
and our cluster be {C
0
j
}
m
j=1
.
For each student s, compute:
True average score in 6 hold out sample: ¯y
s
=
1
|Q
h
|
P
Q
d
sq
Baseline: ¯y
0
s
=
1
|Q
h
|
P
Q
h
P
4
i=1
a
si
q∈C
i
Our Prediction: ˜y
s
=
1
|Q
h
|
P
Q
h
P
m
j=1
a
sj
0
q∈c
0
j
Finally, we compare the MSE:
MSE
1
= (¯y
s
− ¯y
0
s
)
2
MSE
2
= (¯y
s
− ˜y
0
s
)
2
if MSE
2
< MSE
1
, we win!
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Why Spectral Clustering Algorithm?
Doesn’t Make any Strong Assumption of The Data
Figure: Kmeans Nightmare
Works for High Dimension - just imagine plot 26 points in
a 70, 000 dimension
Easy to Implement
Intriguing Visualizations - everybody likes graphs
It draws a beautiful connection between graph theory,
linear algebra, and ML.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Why Spectral Clustering Algorithm?
Doesn’t Make any Strong Assumption of The Data
Figure: Kmeans Nightmare
Works for High Dimension - just imagine plot 26 points in
a 70, 000 dimension
Easy to Implement
Intriguing Visualizations - everybody likes graphs
It draws a beautiful connection between graph theory,
linear algebra, and ML.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Why Spectral Clustering Algorithm?
Doesn’t Make any Strong Assumption of The Data
Figure: Kmeans Nightmare
Works for High Dimension - just imagine plot 26 points in
a 70, 000 dimension
Easy to Implement
Intriguing Visualizations - everybody likes graphs
It draws a beautiful connection between graph theory,
linear algebra, and ML.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Why Spectral Clustering Algorithm?
Doesn’t Make any Strong Assumption of The Data
Figure: Kmeans Nightmare
Works for High Dimension - just imagine plot 26 points in
a 70, 000 dimension
Easy to Implement
Intriguing Visualizations - everybody likes graphs
It draws a beautiful connection between graph theory,
linear algebra, and ML.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Why Spectral Clustering Algorithm?
Doesn’t Make any Strong Assumption of The Data
Figure: Kmeans Nightmare
Works for High Dimension - just imagine plot 26 points in
a 70, 000 dimension
Easy to Implement
Intriguing Visualizations - everybody likes graphs
It draws a beautiful connection between graph theory,
linear algebra, and ML.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Notationless Graph Theory 101
1 2
3 4
1
1
1
10
Degree Matrix:
D =
1 0 0 0
0 12 0 0
0 0 2 0
0 0 0 11
Weighted Adjacency Matrix:
W =
0 1 0 0
1 0 1 10
0 1 0 1
0 10 1 0
Laplacian Matrix:
L = D − W
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Notationless Graph Theory 101
1 2
3 4
1
1
1
10
Degree Matrix:
D =
1 0 0 0
0 12 0 0
0 0 2 0
0 0 0 11
Weighted Adjacency Matrix:
W =
0 1 0 0
1 0 1 10
0 1 0 1
0 10 1 0
Laplacian Matrix:
L = D − W
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Notationless Graph Theory 101
1 2
3 4
1
1
1
10
Degree Matrix:
D =
1 0 0 0
0 12 0 0
0 0 2 0
0 0 0 11
Weighted Adjacency Matrix:
W =
0 1 0 0
1 0 1 10
0 1 0 1
0 10 1 0
Laplacian Matrix:
L = D − W
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
One last Concept: Similarity Graphs/Matrix
Definition: Suppose we have data points x
1
, ··· , x
n
, and some
notion of similarity s
ij
≥ 0: connect x
i
and x
j
with edge weights
s
ij
. The adjacency matrix of this graph is called
similarity matrix.
Two Popular Types of Similarity Graphs
- neighborhood graph: we only connect vertices v
i
and v
j
if their similarity score is higher than some threshold
KNN Graph: connect each vertex v
i
with its K nearest
neighbors in terms of similarity scores.
We want to find a partition of the graph such that the edges
between different groups have very low weights and the edges
within a group have high weights.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
One last Concept: Similarity Graphs/Matrix
Definition: Suppose we have data points x
1
, ··· , x
n
, and some
notion of similarity s
ij
≥ 0: connect x
i
and x
j
with edge weights
s
ij
. The adjacency matrix of this graph is called
similarity matrix.
Two Popular Types of Similarity Graphs
- neighborhood graph: we only connect vertices v
i
and v
j
if their similarity score is higher than some threshold
KNN Graph: connect each vertex v
i
with its K nearest
neighbors in terms of similarity scores.
We want to find a partition of the graph such that the edges
between different groups have very low weights and the edges
within a group have high weights.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Unnormalized Spectral Clustering Algorithm
Algorithm 1 Unnormalized Spectral Clustering
Input : Similarity matrix S ∈ R
n×n
, number k of clusters to
construct.
Construct a similarity graph from S (e.g. KNN graph).
Let W be its weighted adjacency matrix.
Compute the unnormalized Laplacian L
Compute the first k eigenvectors u
1
, ··· , u
k
Let U ∈ R
n×k
be the matrix containing the vectors
u
1
, ··· , u
k
as columns
For i = 1 ···n, let y
i
∈ R
k
be the vector corresponding to
the i-th row of U
Cluster the points (y
i
)
i=1,··· ,n
in R
k
with the k-means
algorithm into clusters C
1
, ··· , C
k
Output: Clusters A
i
, ··· , A
k
with A
i
= {j | y
j
∈ C
i
}
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Back to Original Question
Main idea: we treat each of the 26 non-holdout question as a
node in a graph, we form edges between v
i
and v
j
with edge
weight s
ij
.
Two candidates of Similarity Scores
Correlation Matrix: Easy to implement
XGBoost Feature Importance Scores : be careful for
symmetry issues
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Back to Original Question
Main idea: we treat each of the 26 non-holdout question as a
node in a graph, we form edges between v
i
and v
j
with edge
weight s
ij
.
Two candidates of Similarity Scores
Correlation Matrix: Easy to implement
XGBoost Feature Importance Scores : be careful for
symmetry issues
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Back to Original Question
Main idea: we treat each of the 26 non-holdout question as a
node in a graph, we form edges between v
i
and v
j
with edge
weight s
ij
.
Two candidates of Similarity Scores
Correlation Matrix: Easy to implement
XGBoost Feature Importance Scores : be careful for
symmetry issues
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Conclusion: Some Implementation Advice
KNN graphs tend to perform better than graph in
practice.
Be careful about the assumptions similarity scores:
symmetric and positive
Use Cross-validation to find optimal k and . Don’t
disconnect the graph for small samples.
Give spectral clustering a try next time when you want to
use KMeans
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Conclusion: Some Implementation Advice
KNN graphs tend to perform better than graph in
practice.
Be careful about the assumptions similarity scores:
symmetric and positive
Use Cross-validation to find optimal k and . Don’t
disconnect the graph for small samples.
Give spectral clustering a try next time when you want to
use KMeans
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Properties of Graph Laplacian Matrix
Proposition
1. For every vector f ∈ R
n
, we have
f
T
Lf =
1
2
n
X
i,j=1
w
ij
(f
i
− f
j
)
2
2. L is symmetric and positive semidefinite.
3. The smallest eigenvalue of L is 0, the corresponding
eigenvector is all one vector
4. L has a non-negative, real-valued eigenvalues
0 = λ
1
≤ λ
2
≤ ··· ≤ λ
n
.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Properties of Graph Laplacian Matrix
Proposition
1. For every vector f ∈ R
n
, we have
f
T
Lf =
1
2
n
X
i,j=1
w
ij
(f
i
− f
j
)
2
2. L is symmetric and positive semidefinite.
3. The smallest eigenvalue of L is 0, the corresponding
eigenvector is all one vector
4. L has a non-negative, real-valued eigenvalues
0 = λ
1
≤ λ
2
≤ ··· ≤ λ
n
.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Properties of Graph Laplacian Matrix
Proposition
1. For every vector f ∈ R
n
, we have
f
T
Lf =
1
2
n
X
i,j=1
w
ij
(f
i
− f
j
)
2
2. L is symmetric and positive semidefinite.
3. The smallest eigenvalue of L is 0, the corresponding
eigenvector is all one vector
4. L has a non-negative, real-valued eigenvalues
0 = λ
1
≤ λ
2
≤ ··· ≤ λ
n
.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Properties of Graph Laplacian Matrix
Proposition
1. For every vector f ∈ R
n
, we have
f
T
Lf =
1
2
n
X
i,j=1
w
ij
(f
i
− f
j
)
2
2. L is symmetric and positive semidefinite.
3. The smallest eigenvalue of L is 0, the corresponding
eigenvector is all one vector
4. L has a non-negative, real-valued eigenvalues
0 = λ
1
≤ λ
2
≤ ··· ≤ λ
n
.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
RatioCut of View
Intuitively, suppose we want to form K clusters A
1
, ··· , A
k
, we
want to minimize
Cut(A
1
, ··· , A
k
) =
1
2
k
X
i=1
W (A
i
,
¯
A
i
)
However, the solution often separates one individual vertex
from the rest of the graph. Instead we can minimize
RatioCut(A
1
, ··· , A
k
) =
k
X
i=1
Cut(A
i
,
¯
A
i
)
|A
i
|
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
RatioCut of View
Intuitively, suppose we want to form K clusters A
1
, ··· , A
k
, we
want to minimize
Cut(A
1
, ··· , A
k
) =
1
2
k
X
i=1
W (A
i
,
¯
A
i
)
However, the solution often separates one individual vertex
from the rest of the graph. Instead we can minimize
RatioCut(A
1
, ··· , A
k
) =
k
X
i=1
Cut(A
i
,
¯
A
i
)
|A
i
|
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: when k = 2
We want to find the best subset A, such that
min
A⊂V
RatioCut(A,
¯
A)
Define
f
i
=
q
|
¯
A|
|A|
v
i
∈ A
−
q
|A|
|
¯
A|
v
i
∈
¯
A
We can show
f
T
Lf = |V |RatioCut(A,
¯
A)
P
n
i=1
f
i
= 0
kf k
2
= n
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: when k = 2
We want to find the best subset A, such that
min
A⊂V
RatioCut(A,
¯
A)
Define
f
i
=
q
|
¯
A|
|A|
v
i
∈ A
−
q
|A|
|
¯
A|
v
i
∈
¯
A
We can show
f
T
Lf = |V |RatioCut(A,
¯
A)
P
n
i=1
f
i
= 0
kf k
2
= n
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: when k = 2
We want to find the best subset A, such that
min
A⊂V
RatioCut(A,
¯
A)
Define
f
i
=
q
|
¯
A|
|A|
v
i
∈ A
−
q
|A|
|
¯
A|
v
i
∈
¯
A
We can show
f
T
Lf = |V |RatioCut(A,
¯
A)
P
n
i=1
f
i
= 0
kf k
2
= n
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: when k = 2, continue
Now, the previous optimization problem can be transformed to
min
A⊂V
f
T
Lf subject to f ⊥ , kf k =
√
n
However, this is discrete optimization problem as the entries of
the solution vector f are restricted. we want to relax it to
min
f ∈R
n
f
T
Lf subject to f ⊥ , kf k =
√
n
By Rayleigh-Rietz Theorem, the solution is the second smallest
eigenvalue of L.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: when k = 2, continue
Now, the previous optimization problem can be transformed to
min
A⊂V
f
T
Lf subject to f ⊥ , kf k =
√
n
However, this is discrete optimization problem as the entries of
the solution vector f are restricted. we want to relax it to
min
f ∈R
n
f
T
Lf subject to f ⊥ , kf k =
√
n
By Rayleigh-Rietz Theorem, the solution is the second smallest
eigenvalue of L.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: when k = 2, continue
Now, the previous optimization problem can be transformed to
min
A⊂V
f
T
Lf subject to f ⊥ , kf k =
√
n
However, this is discrete optimization problem as the entries of
the solution vector f are restricted. we want to relax it to
min
f ∈R
n
f
T
Lf subject to f ⊥ , kf k =
√
n
By Rayleigh-Rietz Theorem, the solution is the second smallest
eigenvalue of L.
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: larger k
Suppose we want to partition V into k sets A
1
, ··· , A
k
, we
define k indicator vectors h
j
= [h
1,j
, ··· , h
n,j
]
T
by
h
i,j
=
1
√
|A
j
|
v
i
∈ A
j
0 otherwise
Let H ∈ R
n×k
as the matrix containing these k indicator
vectors as columns. We can show:
H
T
H = I
h
T
i
Lh
i
=
Cut(A
i
,
¯
A
i
)
|A
i
|
h
T
i
Lh
i
= (H
T
LH)
ii
RatioCut(A
1
, ··· , A
k
) =
P
k
i=1
h
T
i
lh
i
= Tr(H
0
LH)
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: larger k
Suppose we want to partition V into k sets A
1
, ··· , A
k
, we
define k indicator vectors h
j
= [h
1,j
, ··· , h
n,j
]
T
by
h
i,j
=
1
√
|A
j
|
v
i
∈ A
j
0 otherwise
Let H ∈ R
n×k
as the matrix containing these k indicator
vectors as columns. We can show:
H
T
H = I
h
T
i
Lh
i
=
Cut(A
i
,
¯
A
i
)
|A
i
|
h
T
i
Lh
i
= (H
T
LH)
ii
RatioCut(A
1
, ··· , A
k
) =
P
k
i=1
h
T
i
lh
i
= Tr(H
0
LH)
Spectral
Clustering of
Mathematics
Exam
Questions
Jiguang Li
Outline
Introduction
Spectral
Clustering
Algorithm
Test Item
Clustering
Bonus: Why
the Algorithm
Works ?
Intuition: larger k, continue
We can rewrite our previous problem as
min
A
1
···A
k
Tr(H
T
LH)subject to H
T
H = I
We have to relax it for numerical solvability:
min
H∈R
n×k
Tr(H
T
LH)subject to H
T
H = I
By Rayleigh-Rietz, the solution is given by the first k
eigenvectors of L
