CS计算机代考程序代写 data structure database Java algorithm Algorithms

Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
4.3 MINIMUM SPANNING TREES
‣ introduction
‣ greedy algorithm
‣ edge-weighted graph API ‣ Kruskal’s algorithm
‣ Prim’s algorithm
‣ context

Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
4.3 MINIMUM SPANNING TREES
‣ introduction
‣ greedy algorithm
‣ edge-weighted graph API ‣ Kruskal’s algorithm
‣ Prim’s algorithm
‣ context

Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
KRUSKAL’S ALGORITHM DEMO

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
graph edges sorted by weight
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
4-5 0.35
1-2 0.36
4-7 0.37
0-4 0.38
6-2 0.40
3-6 0.52
6-0 0.58
6-4 0.93
5
1
7
0
3
2
4
6
an edge-weighted graph
4

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
in MST
0-7 0.16
5
1
7
0
3
2
4
6
does not create a cycle
5

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
does not create a cycle
0-7 0.16
2-3 0.17
1
7
0
in MST
5
3
2
4
6
6

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
does not create a cycle
1
7
0
3
2
in MST
0-7 0.16
2-3 0.17
1-7 0.19
5
4
6
7

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
5
1
7
0
3
2
in MST
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
4
6
does not create a cycle
8

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
1
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
5
3
2
7
in MST
0
4
6
does not create a cycle
9

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
5
1
7
0
creates a cycle
3
2
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
not in MST
4
6
10

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
creates a cycle
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
5
1
7
0
3
2
4
not in MST
6
11

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
creates a cycle
3
2
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
5
1
7
0
4
6
not in MST
12

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
1
7
0
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
4-5 0.35
5
3
2
4
6
in MST
does not create a cycle
13

Kruskal’s algorithm demo
C・onsider edges in ascending order of weight.
Add next edge to tree T unless doing so would create a cycle.
5
1
7
0
3
2
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
4-5 0.35
1-2 0.36
4-7 0.37
0-4 0.38
4
6
creates a cycle
not in MST
16

Kruskal’s algorithm: visualization
19

Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
PRIM’S ALGORITHM DEMO
‣ Prim’s algorithm
‣ lazy implementation
‣ eager implementation

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
5
1
7
0
3
2
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
4-5 0.35
1-2 0.36
4-7 0.37
0-4 0.38
6-2 0.40
3-6 0.52
6-0 0.58
6-4 0.93
4
6
an edge-weighted graph
23

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
5
1
7
0
3
2
4
6
24

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
min weight edge with exactly one endpoint in T
edges with exactly one endpoint in T (sorted by weight)
0-7 0.16
0-2 0.26
0-4 0.38
6-0 0.58
1
3
2
5
in MST
7
0
4
6
25

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
5
1
7
0
3
2
4
6
MST edges
0-7
26

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
min weight edge with exactly one endpoint in T
edges with exactly one endpoint in T (sorted by weight)
1-7 0.19
0-2 0.26
5-7 0.28
2-7 0.34
4-7 0.37
0-4 0.38
6-0 0.58
1
3
5
in MST
72 0
4
6
MST edges
0-7
27

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
5
1
7
0
3
2
4
6
MST edges
0-7 1-7
28

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
min weight edge with exactly one endpoint in T
edges with exactly one endpoint in T (sorted by weight)
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
1-2 0.36
4-7 0.37
0-4 0.38
6-0 0.58
1
3
5
in MST
72 0
4
6
MST edges
0-7 1-7
29

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
5
1
7
0
3
2
4
6
MST edges
0-7 1-7 0-2
30

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
min weight edge with exactly one endpoint in T
edges with exactly one endpoint in T (sorted by weight)
2-3 0.17
5-7 0.28
1-3 0.29
1-5 0.32
4-7 0.37
0-4 0.38
6-2 0.40
6-0 0.58
1
3
5
in MST
72 0
4
6
MST edges
0-7 1-7 0-2
31

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges. min weight edge with
edges with exactly one endpoint in T (sorted by weight)
5-7 0.28
1-5 0.32
4-7 0.37
0-4 0.38
6-2 0.40
3-6 0.52
6-0 0.58
exactly one endpoint in T
5
1
3
72 0
in MST
4
6
MST edges
0-7 1-7 0-2 2-3
33

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges. min weight edge with
edges with exactly one endpoint in T (sorted by weight)
4-5 0.35
4-7 0.37
0-4 0.38
6-2 0.40
3-6 0.52
6-0 0.58
exactly one endpoint in T
5
1
3
72 0
in MST
4
6
MST edges
0-7 1-7 0-2 2-3 5-7
35

Prim’s algorithm demo
・Start with vertex 0 and greedily grow tree T.
・Add to T the min weight edge with exactly one endpoint in T.
Repeat until V – 1 edges.
min weight edge with exactly one endpoint in T
edges with exactly one endpoint in T (sorted by weight)
6-2 0.40
3-6 0.52
6-0 0.58
6-4 0.93
1
3
2
5
in MST
7
4
6
0
MST edges
0-7 1-7 0-2 2-3 5-7 4-5
37

Prim’s algorithm: visualization
39

Prim’s algorithm: implementation challenge
Challenge. Find the min weight edge with exactly one endpoint in T. H・ow difficult?
・E ・V
・log E ・log* E
l
1-7 is min weight edge with exactly one endpoint in T
priority queue of crossing edges
1-7 0.19
0-2 0.26
5-7 0.28
2-7 0.34
4-7 0.37
0-4 0.38
6-0 0.58
40

Prim’s algorithm: implementation challenge
Challenge. Find the min weight edge with exactly one endpoint in T.
H・ow difficult? ・E
try all edges
・V ・log E
・log* E l
1-7 is min weight edge with exactly one endpoint in T
priority queue of crossing edges
1-7 0.19
0-2 0.26
5-7 0.28
2-7 0.34
4-7 0.37
0-4 0.38
6-0 0.58
40

Prim’s algorithm: implementation challenge
Challenge. Find the min weight edge with exactly one endpoint in T.
H・ow difficult? ・E
try all edges
use a priority queue!
・V ・log E
・log* E l
1-7 is min weight edge with exactly one endpoint in T
priority queue of crossing edges
1-7 0.19
0-2 0.26
5-7 0.28
2-7 0.34
4-7 0.37
0-4 0.38
6-0 0.58
40

Prim’s algorithm: lazy implementation
Challenge. Find the min weight edge with exactly one endpoint in T. 
41

Prim’s algorithm: lazy implementation
Challenge. Find the min weight edge with exactly one endpoint in T. 
L・azy solution. Maintain a PQ of edges with (at least) one endpoint in T. ・Key = edge; priority = weight of edge.
・Delete-min to determine next edge e = v–w to add to T.
Disregard if both endpoints v and w are marked (both in T).
1-7 is min weight edge with exactly one endpoint in T
priority queue of crossing edges
1-7 0.19
0-2 0.26
5-7 0.28
2-7 0.34
4-7 0.37
0-4 0.38
6-0 0.58
41

Prim’s algorithm: lazy implementation
Challenge. Find the min weight edge with exactly one endpoint in T. 
L・azy solution. Maintain a PQ of edges with (at least) one endpoint in T. ・Key = edge; priority = weight of edge.
・Delete-min to determine next edge e = v–w to add to T. ・Disregard if both endpoints v and w are marked (both in T).
Otherwise, let w be the unmarked vertex (not in T ):
– add to PQ any edge incident to w (assuming other endpoint not in T)
– addetoTandmarkw
1-7 is min weight edge with exactly one endpoint in T
priority queue of crossing edges
1-7 0.19
0-2 0.26
5-7 0.28
2-7 0.34
4-7 0.37
0-4 0.38
6-0 0.58
41

Lazy implementation of Prim’s algorithm
Prim(graph G)
PQ = empty priority queue of edges color all vertices grey
Visit(0)
while(|A| < n - 1) (u,v) = PQ.DeleteMin() if u or v is grey A = A [ (u, v) if u is grey Visit(u) else // v is grey Visit(v) Visit(vertex u) color u black for all edges (u,v) if v is grey PQ.insert((u,v)) 42 Lazy Prim's algorithm: running time Proposition. Lazy Prim's algorithm computes the MST in time proportional  to E log E and extra space proportional to E (in the worst case).  43 Lazy Prim's algorithm: running time Proposition. Lazy Prim's algorithm computes the MST in time proportional  to E log E and extra space proportional to E (in the worst case).  Pf. operation frequency binary heap delete min E log E insert E log E 43 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T. 5 1 7 0 3 2 4 6 44 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T.   Observation. For each vertex v, need only min weight edge connecting v to T. 5 1 7 0 3 2 4 6 44 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T.   O・bservation. For each vertex v, need only min weight edge connecting v to T. MST includes at most one edge connecting v to T. Why? 5 1 7 0 3 2 4 6 44 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T.   O・bservation. For each vertex v, need only min weight edge connecting v to T. ・MST includes at most one edge connecting v to T. Why? If MST includes such an edge, it can take cheapest such edge. Why? 5 1 7 0 3 2 4 6 44 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T. 45 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T.   pq has at most one entry per vertex Eager solution. Maintain a PQ of vertices connected by an edge to T,    where priority of vertex v = weight of min weight edge connecting v to T. 0 1 1-7 0.19 2 0-2 0.26 3 1-3 0.29 4 0-4 0.38 5 5-7 0.28 6 6-0 0.58 7 0-7 0.16 red: on PQ black: on MST 45 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T.     Eager solution. Maintain a PQ of vertices connected by an edge to T,  w・here priority of vertex v = weight of min weight edge connecting v to T. Delete min vertex v and add its associated edge e = v–w to T. 0 1 1-7 0.19 2 0-2 0.26 3 1-3 0.29 4 0-4 0.38 5 5-7 0.28 6 6-0 0.58 7 0-7 0.16 red: on PQ pq has at most one entry per vertex black: on MST 45 Prim's algorithm: eager implementation Challenge. Find min weight edge with exactly one endpoint in T.   ・Delete min vertex v and add its associated edge e = v–w to T. Update PQ by considering all edges e = v–x incident to v – ignore if x is already in T – addxtoPQifnotalreadyonit – decrease priority of x if v–x becomes min weight edge connecting x to T 0 1 1-7 0.19 2 0-2 0.26 3 1-3 0.29 4 0-4 0.38 5 5-7 0.28 6 6-0 0.58 7 0-7 0.16   Eager solution. Maintain a PQ of vertices connected by an edge to T,  w・here priority of vertex v = weight of min weight edge connecting v to T. pq has at most one entry per vertex black: on MST 45 red: on PQ Eager implementation of Prim’s algorithm Prim(graph G) PQ = empty priority queue of edges cost = array of size n edge = array of size n color all vertices grey Visit(0) while(PQ not empty) u = PQ.DeleteMin() A = A [ edge[u] Visit(u) Visit(vertex u) color u black for all edges (u,v) if v is grey color v red PQ.insert((u,v)) cost[v] = w(u,v) edge[v] = (u,v) elseif (v is red) and (w(u,v) < dist[v]) PQ.DecreaseKey(v, w(u,v)) cost[v] = w(u,v) edge[v] = (u,v) 46 Prim's algorithm: which priority queue? Depends on PQ implementation: V insert, V delete-min, E decrease-key. 47 Prim's algorithm: which priority queue? Depends on PQ implementation: V insert, V delete-min, E decrease-key. 47 Prim's algorithm: which priority queue? Depends on PQ implementation: V insert, V delete-min, E decrease-key. PQ implementation unordered array 1 V 1                   insert delete-min decrease-key total V2 B・ottom line. Array implementation optimal for dense graphs. 47 Prim's algorithm: which priority queue? Depends on PQ implementation: V insert, V delete-min, E decrease-key. PQ implementation unordered array 1 V 1 binary heap log V log V log V                   insert delete-min decrease-key total V2 E log V B・ottom line. ・Array implementation optimal for dense graphs. Binary heap much faster for sparse graphs. 47 Prim's algorithm: which priority queue? Depends on PQ implementation: V insert, V delete-min, E decrease-key. PQ implementation unordered array 1 V 1 binary heap log V log V log V d-way heap logd V d logd V logd V                   insert delete-min decrease-key total V2 E log V E logE/V V B・ottom line. ・Array implementation optimal for dense graphs. ・Binary heap much faster for sparse graphs. 4-way heap worth the trouble in performance-critical situations. 47 Prim's algorithm: which priority queue? Depends on PQ implementation: V insert, V delete-min, E decrease-key.                   B・ottom line. ・Array implementation optimal for dense graphs. ・Binary heap much faster for sparse graphs. ・4-way heap worth the trouble in performance-critical situations. PQ implementation insert delete-min decrease-key total V2 E log V E logE/V V E + V log V † amortized 1 V 1 log V log V log V logd V d logd V logd V unordered array binary heap d-way heap Fibonacci heap 1 † log V † 1 † Fibonacci heap best in theory, but not worth implementing. 47 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it. How difficult? ・E + V ・V ・log V ・log* V ・1 add edge to tree adding edge to tree would create a cycle 48 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it. How difficult? ・E + V ・V run DFS from v, check if w is reachable  (T has at most V – 1 edges) ・log V ・・log* V 1 add edge to tree adding edge to tree would create a cycle 48 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it. How difficult? ・E + V ・V run DFS from v, check if w is reachable  (T has at most V – 1 edges) ・log V ・・log* V 1 use the union-find data structure ! add edge to tree adding edge to tree would create a cycle 48 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it.  Efficient solution. Use the union-find data structure. 49 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it.  Efficient solution. Use the union-find data structure. ・Maintain a set for each connected component in T. 49 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it.  Efficient solution. Use the union-find data structure. ・Maintain a set for each connected component in T. ・If v and w are in same set, then adding v–w would create a cycle. vw Case 1: adding v–w creates a cycle 49 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it.  Efficient solution. Use the union-find data structure. ・Maintain a set for each connected component in T. ・If v and w are in same set, then adding v–w would create a cycle. ・To add v–w to T, merge sets containing v and w. vw w v Case 1: adding v–w creates a cycle Case 2: add v–w to T and merge sets containing v and w 49 Kruskal's algorithm: implementation challenge Challenge. Would adding edge v–w to tree T create a cycle? If not, add it.  Efficient solution. Use the union-find data structure. ・Maintain a set for each connected component in T. ・If v and w are in same set, then adding v–w would create a cycle. ・To add v–w to T, merge sets containing v and w. vw w v Case 1: adding v–w creates a cycle Case 2: add v–w to T and merge sets containing v and w 49 Kruskal's algorithm: Java implementation public class KruskalMST { private Queue mst = new Queue();
public KruskalMST(EdgeWeightedGraph G)
{
MinPQ pq = new MinPQ(G.edges());
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V()-1) { } } public Iterable edges()
{ return mst; }
}
Edge e = pq.delMin();
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w))
{
uf.union(v, w);
mst.enqueue(e);
}
build priority queue (or sort)
greedily add edges to MST
edge v–w does not create cycle
merge sets
add edge to MST
50

Kruskal’s algorithm: running time
Proposition. Kruskal’s algorithm computes MST in time proportional to  E log E (in the worst case).
51

Kruskal’s algorithm: running time
Proposition. Kruskal’s algorithm computes MST in time proportional to  E log E (in the worst case).
 
Pf.
                     
operation
frequency
time per op
build pq
1
E
delete-min
E
log E
union
V
log* V †
connected
E
log* V †
† amortized bound using weighted quick union with path compression
recall: log* V ≤ 5 in this universe
Remark. If edges are already sorted, order of growth is E log* V.
51

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year worst case discovered by
53

Does a linear-time MST algorithm exist?
year
deterministic compare-based MST algorithms
worst case discovered by
Yao
1975
E log log V
53

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
worst case discovered by
Yao Cheriton-Tarjan
year
1975
E log log V
1976
E log log V
53

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
worst case discovered by
Yao Cheriton-Tarjan Fredman-Tarjan
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
53

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan
53

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
1997
E α(V) log α(V)
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
53

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
E log log V
1976
E log log V
1984
Elog*V, E+VlogV
1986
E log (log* V)
1997
E α(V) log α(V)
2000
E α(V)
worst case
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle
53

Does a linear-time MST algorithm exist?
deterministic compare-based MST algorithms
year
1975
1976
1984
1986
1997
2000
2002
worst case
E log log V
E log log V
E log* V, E + V log V E log (log* V)
E α(V) log α(V)
E α(V) optimal
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle Pettie-Ramachandran
53

Does a linear-time MST algorithm exist?
year
1975
1976
1984
1986
1997
2000
2002
20xx
worst case
E log log V
E log log V
E log* V, E + V log V E log (log* V)
E α(V) log α(V)
E α(V) optimal
E
discovered by
Yao Cheriton-Tarjan Fredman-Tarjan Gabow-Galil-Spencer-Tarjan Chazelle
Chazelle Pettie-Ramachandran
???
deterministic compare-based MST algorithms
53

Euclidean MST
Given N points in the plane, find MST connecting them, where the distances between point pairs are their Euclidean distances.
54

Euclidean MST
Given N points in the plane, find MST connecting them, where the distances between point pairs are their Euclidean distances.
 
 
                   
Brute force. Compute ~ N 2 / 2 distances and run Prim’s algorithm.
54

Scientific application: clustering
k-clustering. Divide a set of objects classify into k coherent groups. Distance function. Numeric value specifying “closeness” of two objects.
 
Goal. Divide into clusters so that objects in different clusters are far apart.  
 
 
 
 
 
 
Applications.
outbreak of cholera deaths in London in 1850s (Nina Mishra)
・Routing in mobile ad hoc networks.
・Document categorization for web search.
・Similarity searching in medical image databases.
・Skycat: cluster 109 sky objects into stars, quasars, galaxies.
55

Single-link clustering
k-clustering. Divide a set of objects classify into k coherent groups. Distance function. Numeric value specifying “closeness” of two objects.
Single link. Distance between two clusters equals the distance  between the two closest objects (one in each cluster).
Single-link clustering. Given an integer k, find a k-clustering that maximizes the distance between two closest clusters.
distance between two clusters
distance between  two closest clusters
4-clustering
56

Single-link clustering algorithm
“Well-known” algorithm in science literature for single-link clustering:
・Form V clusters of one object each.
・Find the closest pair of objects such that each object is in a different ・cluster, and merge the two clusters.
Repeat until there are exactly k clusters.  
Observation. This is Kruskal’s algorithm.  (stopping when k connected components)
57

Dendrogram of cancers in human
Tumors in similar tissues cluster together.
gene 1
gene n
Reference: Botstein & Brown group
gene expressed gene not expressed
58

Related Posts