ECS124-L13

📗 -> 02/25/25: ECS124-L13

---

Resource

🎤 Vocab

❗ Unit and Larger Context

Clustering

Covered

Tree Creation
Tree & Kmeans

Tree Clustering

UPGMA - Page 28 on PDF above

1. Form n clusters each w/ a single element
2. Construct graph T by assigning node for each cluster
3. Set height of each node to h(v)=0
   1. Should have constructed a symmetric/triangular matrix
4. while (more than 1 cluster)

	find 2 closest clusters c1, c2 # track the min in graph
	# The above is O(n^2)
	cluster C merges c1 and c2
	# |C| = |C1| + |C2|
	for every C^o != C:

• O(n^2) book =>
• O(1) class =>

5. Add new node C to the tree
   1. h(c) = D(C1, C2)/2
6. Assigning label h(c) - h(c1) to edge (c, c1)
7. Assigning label h(c) - h(c2) to edge (c, c2)
   After this, we have a new “parent” node clustering the two elements, with height/edge weight constructed from distance to children

Neighbor Joining

NOT COMPREHENSIVE
Page 29 for full algo

1. Form n clusters each w\ a single element
2. Construct graph T by assigning node for each element/cluster
3. while (there is more than one cluster)
   1. Find 2 closest clusters c1, c2 not based on distance, but based on D(c1, c2) - u(c1) - u(c2)
      1. D(c1, c2) != D(c1, c2) - u(c1) - u(c2)
      2. Taking away distance between mice and everybody else, then taking away distance between people and everybody else
      3. General idea: Account for the possibility that they are on a completely different branch from everybody else
   2. n^2- computer all u(c) for all clusters
   3. n^2 - compare all c1, c2: D(c1, c2) - u(c1) - u(c2)
4. Merge c1, c2 into single cluster
5. Compute D:
6. Add new vertex C
7. Assign length h(C) = 1/2 * ( D(c1, c2) - u(c1) - u(c2) ) to edges (c, c1) and (c, c2)

	H	M	R	D	C
H		4	5	10	11
M			3	11	7
R				12	10
D					3
C

	H	M	R	D	C
H
u(h)
$u(c) = \frac{1}{n-2}\sum_{	C’	}D(C, C’)$

Work for the above:

• 4 - U(H) - U(M) = -6 - 4
• 4 - U(H) - U(R) = 0 - 4
• 4 - U(H) - U(D) = -10 - 12 -4
• 4 - U(H) - U(C) = -11 - 12 - 4

✒️ -> Scratch Notes

• Log as you go through entry

🧪 -> Refresh the Info

Did you generally find the overall content understandable or compelling or relevant or not, and why, or which aspects of the reading were most novel or challenging for you and which aspects were most familiar or straightforward?)

Did a specific aspect of the reading raise questions for you or relate to other ideas and findings you’ve encountered, or are there other related issues you wish had been covered?)

🔗 -> Links

Resources

• Put useful links here

Connections

• Link all related words