代写Lloyd’s Algorithm, 也就是k-means算法。
Requirement
In finance, we often want to treat things as a group. The hope is that the
grouping will reveal patterns and reduce noise. For example, we know for a
fact that the returns of 7,000 stocks do not represent 7,000 orthogonal
factors. The number of factors driving stock returns is much, much smaller
than that, though the exact number of real factors is a point of some
controversy.
Techniques such as principal components analysis - which is frequently used to
attempt to extract the factors driving stock prices - are beyond the scope of
this class. You will spend some time working with PCA and other approaches
later in the math finance program. In this class, we want to focus on problems
that exercise your programming muscles.
Fortunately, there is a computationally interesting yet relatively simple
clustering technique that we can use to demonstrate the problem of grouping
things. It’s called Lloyd’s Algorithm or the K-means algorithm. The following
is a graphical demonstration of the standard Lloyd’s Algorithm at work.
While the above clustering problem is shown in two dimensions, any number of
dimensions can be used. We can compute distances in two dimensions, or any
number of dimensions.
If we were doing this with a time series of stock returns, each return would
represent a value in one dimension, and each time series would be a point in n
dimensions, where n is the number of returns in that series.
But we’re going to leave this bigger problem alone and focus on a much smaller
problem, a toy problem. As explained in class, though the solution of the toy
problem will be well known to us, it will not be easy to get a computer to
solve it.
The Toy Problem
Suppose a city 99 blocks wide by 99 blocks long. A person stands on every
corner, 10,000 people in all. In other words, there’s a person at {0,0}, a
person at {0,1}, and so on. There is a person at {99,99}, the top right corner
of the map, a person at {0,99}, the top left corner of the map, and a person
at {99,0}, the bottom right corner of the map. 10,000 people in all, evenly
distributed throughout our toy city. (By the way, this area is about twice the
size of Manhattan.)
The problem we want to solve is this: we want to group these people into
clusters of 20, or 500 clusters in all. The solution to this problem is a list
of the centers of these clusters, their geometric centroids.
This problem is called NP hard. It’s a highly combinatorial problem and brute
force solutions are going to fail miserably. For example, suppose we were
finding just two cluster centroids. There are 100 possible x coordinates and
100 possible y coordinates for each of two cluster centroids, or 100 x 100 x
100 x 100 = 100 million possible ways to place the centroids. But we are not
working with two centroids. We are working with 500. Clearly, a brute force
search just won’t work.
Intuitively, we know the solution: we would put one cluster centroid at the
center of every square with the following width and height in blocks.
However, to actually do this, we will use Lloyd’s algorithm. The solution will
not be exact. Lloyd’s Algorithm is a heuristic which will converge to
solutions that may not be globally optimal. However, it will get us pretty
close.
The Objectives
Any algorithm that can be graphically described in 4 slides (as above) is
going to be trivial to implement, so the solution - while it should be correct
- is not the main objective of this homework. The main objective of this
homework is to apply the themes and strategies that were explained to you in
the last lecture.- Your solution should be elegant in its object-oriented design and should lend itself to easy and thorough unit testing using Junit.
- This testing is part of the deliverables of your homework assignment.
- You should build your classes to be reusable. Though the problem is simple, there are definitely reusable components that are part of the solution.
- You should come up with a metric that allows you to measure the quality of the solution as well as the quality of the initial state. Your code should be readable and well documented.
The Twist
As you can see from the graphical representation of Lloyd’s Algorithm, it does
not group points in clusters of fixed size. But what if we want that? What if
we demand that each cluster has 20 people? The problem becomes much more
difficult. To see how much more difficult, you will present two solutions. One
solution will use the standard Lloyd’s approach - points seeking the nearest
cluster - while the second solution will use a modified approach - clusters
seeking the nearest 20 points.
In other words, in Lloyd’s Algorithm, you will iterate over every point - each
representing a person - and, for that point, will find the nearest cluster
centroid. In the modified approach, you will iterate over cluster centroids
and, for each, will find the nearest 20 points.
If you write your code correctly and use all of the principles of good object
oriented design, this modification should be easy and should not require
rewriting much of your code.
