[EM] cluster analysis

Forest Simmons fsimmons at pcc.edu
Wed Feb 25 21:11:12 PST 2004

```I can think of two general approaches to applying cluster analysis to
election methods:

(1) First construct a vector representing each candidate by (say)
averaging the ballot vectors together that give the highest rating or
ranking to the candidate.  If first place is shared, weight accordingly.

Then use cluster analysis to construct a tree of these candidate vectors.

Finally, the candidate at the median of the tree is the winning candidate.

[I will explain how to find the median of a tree below.]

(2) Apply cluster analysis directly to the ballot vectors. The ballot
vector at the median of the tree is then used to pick the winning
candidate.

How to find the "median of a tree (with weighted nodes):"

Start at any node.  Removal of an edge will separate the tree into two
components. While there is a component with more than half the total
weight, move along the edge toward that component.

If any two components both have exactly half the weight, then the median
is halfway along the edge connecting them.  In our applications, the two
nodes of that edge are tied.

Forest

```