Click here to Skip to main content
Click here to Skip to main content
Go to top

K-Means Clustering Used in Intention Based Scoring Projects

, 3 Jan 2009
Rate this:
Please Sign up or sign in to vote.
The use of K-Means clustering for data mining purposes.

Introduction

Intention based scoring (IBS) is a scoring system, its goal is to provide a score that more accurately assesses a student’s ability to solve a composition problem, and therefore assess direct effects of the student's programming ability. This process is dubbed “intention based” because, firstly, the programs are inspected by inferring what goals the student is trying to achieve, and secondly, what plan component is being attempted when a program statement is not syntactically correct.

The three steps necessary to perform IBS were introduced by [1]: inspection of an on-line protocol, bug identification, and scoring.

The final goal of this project is to create an automated Intention Based Score for each programming assignment, and use K-Mean Clustering to identify which students belong to which group.

K-Means algorithm

The K-Means algorithm is an algorithm to cluster n objects based on attributes into k partitions, k < n. It is similar to the expectation-maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural clusters in the data. It assumes that the object attributes form a vector space. The objective it tries to achieve is to minimize total intra-cluster variance, or, the squared error function:

formula.png

where there are k clusters Si, i = 1, 2, ..., k, and µi is the centroid or mean point of all the points xj in Si. The K-Means clustering was invented in 1956. The most common form of the algorithm uses an iterative refinement heuristic known as Lloyd's algorithm. Lloyd's algorithm starts by partitioning the input points into k initial sets, either at random, or using some heuristic data. It then calculates the mean point, or centroid, of each set. It constructs a new partition by associating each point with the closest centroid. Then, the centroids are recalculated for the new clusters, and algorithm repeated by alternate application of these two steps until convergence, which is obtained when the points no longer switch clusters (or alternatively, the centroids are no longer changed).

Lloyd's algorithm and K-means are often used synonymously, but in reality, Lloyd's algorithm is a heuristic for solving the K-Means problem, as with certain combinations of starting points and centroids, Lloyd's algorithm can, in fact, converge to the wrong answer (i.e., a different and optimal answer to the minimization function above exists). Other variations exist, but Lloyd's algorithm has remained popular because it converges extremely quickly in practice. In fact, many have observed that the number of iterations is typically much less than the number of points. Recently, however, David Arthur and Sergei Vassilvitskii showed that there exist certain point sets on which K-Means takes super-polynomial time: 2Ω(√n) to converge approximate K-Means algorithms have been designed that make use of core sets: small subsets of the original data.

In terms of performance, the algorithm is not guaranteed to return a global optimum. The quality of the final solution depends largely on the initial set of clusters, and may, in practice, be much poorer than the global optimum. Since the algorithm is extremely fast, a common method is to run the algorithm several times and return the best clustering found. A drawback of the K-Means algorithm is that the number of clusters k is an input parameter. An inappropriate choice of k may yield poor results. The algorithm also assumes that the variance is an appropriate measure of cluster scatter.

algo.gif

The K-Means clustering algorithm was developed by J. MacQueen (1967) and then by J. A. Hartigan and M. A. Wong around 1975. Simply speaking, K-Means clustering is an algorithm to classify or to group your objects based on attributes/features, into K number of groups. K is a positive integer number. The grouping is done by minimizing the sum of squares of distances between data and the corresponding cluster centroid. Thus, the purpose of K-means clustering is to classify the data.

Pseudo code

Initialize the algorithm either heuristically or randomly. Iterate the following steps until convergence (stopping criteria met):

  1. For each data point x, compute its membership in clusters by choosing the nearest centroid.
  2. For each centroid, recompute its location according to members:
    var m = initialCentroids(x, K);
    var N = x.length;
    while (!stoppingCriteria) {
        var w = [][];
        // calculate membership in clusters
        for (var n = 1; n <= N; n++) {
        v = arg min (v0) dist(m[v0], x[n]);
        w[v].push(n);
    }
    // recompute the centroids
    for (var k = 1; k <= K; k++) {
        m[k] = avg(x in w[k]);
    }
}
return m;

For example, please see K-Means clustering tutorials.

Program

To cluster students, we set certain attributes inside an array for each student. For the purposes of this article, I have only used three variables for each student.

double[] Student = new double[] { Compiles, Errors, Time(Minutes), ETC…. };

In my sample, I used the following:

double[] StudentA = new double[] { 15, 32, 35.6 };
double[] StudentB = new double[] { 19, 54, 65.1 };
double[] StudentC = new double[] { 22, 95, 45.6 };

The number of attributes should all be equal; so, if a student does not have an assignment, the value will be zero. To add a collection of clusters, just add your data as:

double[,] data = { StudentA, StudentB, StudentC};
double[,] data = { { 15, 32, 35.6 }, { 19, 54, 65.1 }, {22,95,45.6 } };

To get the clusters for these three students, you set a K for the number of cluster you would want to partition them in to. For example, K=2:

clusters = KMeans.ClusterDataSet( K, data);

ClusterCollection clusters;
clusters = KMeans.ClusterDataSet(2, data);

The output of the ClusterDataSet function will be of type CollectionBase. This data is serialized so it can be converted to XML and so on as you wish. I have placed this in a DataGrid for viewing.

Other functions that can be used are:

//Test the Euclidean Distance calculation between two data points
double distance = KMeans.EuclideanDistance(StudentA, StudentB);
Response.Write("<br/>Euclidean Distance A and B:" + distance);

Euclidean distance or simply 'distance' examines the root of square differences between coordinates of a pair of objects.

//Test the Manhattan Distance calculation between two data points
double distances = KMeans.ManhattanDistance(StudentA, StudentB);
Response.Write("<br/>Manhattan Distance A and B:" + distances);

It is also known as Manhattan distance, boxcar distance, or absolute value distance. It represents the distance between points in a city road grid. It examines the absolute differences between coordinates of a pair of objects.

//Test the Cluster Mean calculation between two data points
double[,] cluster = { { 15, 32, 35.6 }, { 19, 54, 65.1 } };
double[] centroid = KMeans.ClusterMean(cluster);
Response.Write("<br/>Cluster mean Calc: "+ centroid.ToString());

Sources

  1. H. Chad Lane, Kurt VanLehn; Intention Based Scoring: An Approach to Measuring Success at Solving the Composition Problem; Technical Symposium on Computer Science Education. Proceedings of the 36th SIGCSE technical symposium on Computer Science education, 2005, St. Louis, Missouri, USA.
  2. K-Means clustering tutorials
  3. Wikipedia

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

saharkiz
Web Developer
Philippines Philippines
My name : Aresh Saharkhiz.
Origin: Unknown
 
Education : BS Computer Science
MS Computer Science
Interests : Genetic Programming
Neural Networks
Game AI
Programming: (language == statementEnd(semicolon)
 

http://sites.google.com/site/docaresh
 
Skill:
Flash
Carrara 3D
PHP,ASP,ASP.NET
J2SE

Comments and Discussions

 
GeneralMy vote of 4 Pinmemberhiphopper012323-May-13 2:31 
QuestionI just want a 2-d array of all the points. Pinmemberrohit5766-Jul-12 23:56 
AnswerThis is the answer Pinmemberhiphopper012323-May-13 20:23 
Questioneuclidean distance PinmemberMember 384042825-Aug-11 5:31 
General[My vote of 2] Plagiarism Pinmemberjuggler19-Apr-11 1:17 
GeneralRe: [My vote of 2] Plagiarism Pinmembersaharkiz19-Jun-11 2:13 
GeneralBugs PinmemberWernight29-Mar-11 2:28 
Questionhow to use it to solve my problem PinmemberUnruled Boy26-Jan-11 21:29 
Generalk-means clustering for large amount of data sets PinmemberGayathri Asokan5-Oct-10 5:26 
GeneralVery good article on K-means. PingroupTrevor Misfeldt18-Oct-09 18:24 
Questioncan this cluster academic paper? Pinmemberkv400012-May-09 17:06 
QuestionStudent & Cluster Pinmemberseoulaja20-Apr-09 18:57 
Questionthis can be applied to nXn dataset Pinmemberhellohowur11-Apr-09 18:44 
GeneralVery Nice Article if you are into Unsupervised Clustering PinmemberMember 46013655-Jan-09 23:49 
GeneralIntention based scoring and clustering Pinmemberjconwell5-Jan-09 9:05 
GeneralRe: Intention based scoring and clustering Pinmemberaresguya5-Jan-09 14:28 
GeneralRe: Intention based scoring and clustering PinmemberGayathri Asokan5-Oct-10 16:41 
GeneralNice Article. PinmemberRazanPaul4-Jan-09 3:00 
GeneralRe: Nice Article. Pinmemberjconwell5-Jan-09 4:38 
GeneralRe: Nice Article. Pinmemberjconwell5-Jan-09 9:07 
GeneralRe: Nice Article. Pinmemberaresguya5-Jan-09 12:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 3 Jan 2009
Article Copyright 2009 by saharkiz
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid