## 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.