Description
Assignment #1: K-Means
Implement the standard version of the K-Means algorithm as described in lecture. The initial
starting points for the K cluster means can be K randomly selected data points. You should
have an option to run the algorithm r times from r different randomly chosen initializations
(e.g., r = 10), where you then select the solution that gives the lowest sum of squares error
over the r runs. Run the algorithm for several different values of K and report the sum of
squares error for each of these models. Please include a 2-d plot of several different
iterations of your algorithm with the data points and clusters.
Assignment #2: Fuzzy C-Means
Implement the standard version of the fuzzy c-means (FCM) algorithm as described in
lecture. As shown in lecture, the update formulae for the centroids and membership weights
are as follows:
Where m > 1 is a “fuzzifier” parameter (just fix this value during the algorithm – you are
welcome to experiment by trying different values for different runs of FCM if you wish).
Begin by initializing the centroids randomly, then compute the weights, update the centroids,
recompute the weights, etc. As before, you should have an option to run the algorithm r
times from r different randomly chosen initializations (e.g., r = 10), where you then select
the solution that gives the lowest sum of squares error over the r runs. Run the algorithm for
several different values of K (where K is the number of clusters) and report the sum of
( )
( )
2
1
1
1
m
k
x
k ij m
k c m
i j x
k i j
w
w
w −
=
= =
−
−
x x
c
x
x c
x c
squares error for each of these models. Please include a 2-d plot of several different
iterations of your algorithm with the data points and clusters.
Report: Your report should include a short description of your experiments, along with the
plots and discussion paragraphs requested above and any other relevant information to help
shed light on your approach and results.
Here is what you need to turn in:
• Your report.
• Readable code.
How to turn it in (read carefully!):
• Send these items in electronic format to ark2@pdx.edu (our TA) by 6pm on the due
date. No hard copy please!
• The report should be in pdf format and the code should be in plain-text format.
• Put “[CS 545] PROGRAMMING #3: your_name” in the subject line.
If there are any questions, don’t hesitate to ask me or Nandadeep.