Implementation of Fixed-width clustering algorithm

Question

Dear All hope this message finds you well. I want to ask about the the implementation of the Fixed-width clustering algorithm. anyone can help me ASAP? Fixed-width clustering algorithm: Fixed width clustering creates a set of clusters of fixed radius (width) w. Here the width w is a parameter to be specified by the user. First a data vector is taken and used as the centroid (center) of the first cluster with radius w. Then for each subsequent data vector the Euclidean distance between the centroid of the current clusters and this data vector is computed. If the distance to the closest cluster center from the data vector is less than the radius w the data vector is added into that cluster and the centroid of that cluster is adjusted to the mean of the data vectors it contains. If the distance to the closest cluster center is more than the radius w then a new cluster is formed with that data vector as the centroid. This operation produces a set of disjoint fixed width (radius of w) clusters in the feature space. Thanks in advance

Vulpes · Answer

OK if you're only clustering single temperature readings using this algorithm then it's fairly easy: using System; using System.Collections.Generic; static class FixedWidth { static double width; // fixed width static void Main() { List > clusters = new List >(); List centroids = new List (); // sample data double[] data = {30 28 31.5 34 34.2 29.5 33 31.4 28.7 29.9 36 32.6}; width = 1.75; List cluster = new List (); // create cluster cluster.Add(data[0]); // add first data item clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[0]); // add centroid of new cluster to centroids list for(int i = 1; i { int closest = -1; // impossible value double minDistance = Double.MaxValue; // likewise for (int j = 0; j { double distance = Math.Abs(data[i] - centroids[j]); if (distance { minDistance = distance; closest = j; } } if (minDistance { clusters[closest].Add(data[i]); // add data to closest cluster centroids[closest] = GetCentroid(clusters[closest]); // recalculate centroid of cluster } else { cluster = new List (); // create new cluster cluster.Add(data[i]); clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[i]); // add centroid of new cluster to centroids list } } // print results Console.Clear(); Console.WriteLine(The fixed width is {0}
 width); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following values :
 i + 1); Console.Write(	); foreach(double d in clusters[i]) Console.Write({0}  d); Console.Write( - Centroid {0:F3} centroids[i]); Console.WriteLine(); } Console.ReadKey(); } static double GetCentroid(List cluster) { double sum = 0.0; foreach(double d in cluster) sum += d; return sum / cluster.Count; } }

Vulpes · Answer

OK I've rewritten the program to use a basic Cluster class rather than a List . Rather than wrap the List this class simply exposes the whole List as a property. It also contains a Centroid property which returns a Flow representing the centroid of the Cluster. Again it's very rushed so keep an eye out for bugs: using System; using System.Collections.Generic; class Flow { public double Src {get; set;} public double Des {get; set;} public double Port {get; set;} public double Field4 {get; set;} public double Field5 {get; set;} public double Field6 {get; set;} public double Field7 {get; set;} public double Field8 {get; set;} public double Field9 {get; set;} public Flow(double src double des double port double field4 double field5 double field6 double field7 double field8 double field9) { Src = src; Des = des; Port = port; Field4 = field4; Field5 = field5; Field6 = field6; Field7 = field7; Field8 = field8; Field9 = field9; } public override string ToString() { return String.Format((Src={0} Des={1} Port={2} Field4={3} Field5={4} Field6={5} Field7={6} Field8={7} Field9={8}) Src Des Port Field4 Field5 Field6 Field7 Field8 Field9); } } class Cluster { public List Flows {get; set;} public Cluster() { Flows = new List (); } public Flow Centroid { get { double[] sum = new double[9]; foreach(Flow f in Flows) { sum[0] += f.Src; sum[1] += f.Des; sum[2] += f.Port; sum[3] += f.Field4; sum[4] += f.Field5; sum[5] += f.Field6; sum[6] += f.Field7; sum[7] += f.Field8; sum[8] += f.Field9; } for(int i = 0; i return new Flow(sum[0] sum[1] sum[2] sum[3] sum[4] sum[5] sum[6] sum[7] sum[8]); } } } static class FixedWidth { static double width; // fixed width static void Main() { List clusters = new List (); List centroids = new List (); // data all set to default value of zero for now double[] src = new double[12]; double[] des = new double[12]; double[] port = new double[12]; double[] field4 = new double[12]; double[] field5 = new double[12]; double[] field6 = new double[12]; double[] field7 = new double[12]; double[] field8 = new double[12]; double[] field9 = new double[12]; Cluster data = new Cluster(); for(int i = 0; i { Flow f = new Flow(src[i] des[i] port[i] field4[i] field5[i] field6[i] field7[i] field8[i] field9[i]); data.Flows.Add(f); } width = 2.25; // or whatever Cluster cluster = new Cluster(); // create cluster cluster.Flows.Add(data.Flows[0]); // add first reading clusters.Add(cluster); // add cluster to clusters list centroids.Add(data.Flows[0]); // add centroid of new cluster to centroids list for(int i = 1; i { int closest = -1; // impossible value double minDistance = Double.MaxValue; // likewise for (int j = 0; j { double distance = GetDistance(data.Flows[i] centroids[j]); if (distance { minDistance = distance; closest = j; } } if (minDistance { clusters[closest].Flows.Add(data.Flows[i]); // add reading to closest cluster centroids[closest] = clusters[closest].Centroid; // recalculate centroid of cluster } else { cluster = new Cluster(); // create new cluster cluster.Flows.Add(data.Flows[i]); clusters.Add(cluster); // add cluster to clusters list centroids.Add(data.Flows[i]); // add centroid of new cluster to centroids list } } // print results Console.Clear(); Console.WriteLine(The fixed width is {0}
 width); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following flows :
 i + 1); foreach(Flow f in clusters[i].Flows) Console.WriteLine(f); Console.WriteLine(Centroid : ); Console.WriteLine(centroids[i]); Console.WriteLine(); } // now merge similar clusters if (clusters.Count > 1) { List clusterIndicesToRemove = new List (); for (int i = 0; i { for (int j = i + 1; j { if (GetDistance(centroids[i] centroids[j]) { clusters[j].Flows.InsertRange(0 clusters[i].Flows); centroids[j] = clusters[j].Centroid; clusterIndicesToRemove.Add(i); } } } for (int i = clusters.Count - 1; i >= 0; i--) { if (clusterIndicesToRemove.Contains(i)) { clusters.RemoveAt(i); centroids.RemoveAt(i); } } } // print merged results Console.WriteLine(

The merged results are
); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following flows :
 i + 1); foreach(Flow f in clusters[i].Flows) Console.WriteLine(f); Console.WriteLine(Centroid : ); Console.WriteLine(centroids[i]); Console.WriteLine(); } Console.ReadKey(); } static double GetDistance(Flow f1 Flow f2) { double[] d = new double[9]; d[0] = f1.Src - f2.Src; d[1] = f1.Des - f2.Des; d[2] = f1.Port - f2.Port; d[3] = f1.Field4 - f2.Field4; d[4] = f1.Field5 - f2.Field5; d[5] = f1.Field6 - f2.Field6; d[6] = f1.Field7 - f2.Field7; d[7] = f1.Field8 - f2.Field8; d[8] = f1.Field9 - f2.Field9; double sum = 0; for(int i = 0; i return Math.Sqrt(sum); } }

Vulpes · Answer

I've never heard of this particular algorithm but it sounds similar to the Quality Threshold (or QT) algorithm. Please see my article ( http://www.c-sharpcorner.com/UploadFile/b942f9/6167/ ) for an implementation of the latter which you may be able to adjust if it's not quite what you want.

Vulpes · Answer

1. Well a Cluster class would just be a wrapper for a List where T is the type of object to be clustered. To create this you'd need to wrap all the methods of List that you want to use which if there are a lot of them is a tedious thing to program. Frankly I can't see any point in doing this unless you want to give Cluster some methods or properties which List doesn't already have. 2. If I've understood that correctly there's no difference in principle from what the code is already doing except that the Flow objects have been grouped into a series of DataViews first. So you process the DataViews in a loop. Clusters are created for the objects in the first DataView. You then process the objects in the second DataView adding them to existing clusters where appropriate or creating new clusters otherwise. And so on for the remaining DataViews. I'd imagine that the final results won't be much different than if you'd clustered the objects in the original order.

Vulpes · Answer

This part of the code is concerned with populating the List object data with Flow objects which can then be clustered: // data all set to default value of zero for now double[] src = new double[12]; double[] des = new double[12]; double[] port = new double[12]; double[] field4 = new double[12]; double[] field5 = new double[12]; double[] field6 = new double[12]; double[] field7 = new double[12]; double[] field8 = new double[12]; double[] field9 = new double[12]; List data = new List (); for(int i = 0; i { Flow f = new Flow(src[i] des[i] port[i] field4[i] field5[i] field6[i] field7[i] field8[i] field9[i]); data.Add(f); } As such it can be replaced with code which imports the flows from a table (csv file XML file database Excel spreadsheet etc). As long as you end up with a List called 'data' the rest of the code should work.

Vulpes · Answer

src.Length is just a way of specifying the number of data items. This is set to 12 in the example code but can of course be anything you like. Note that we can't use data.Count instead because the 'for' loop is creating and adding Flow objects to the data list. 'data' is a List and so data[0] is the first Flow object in the list.

Vulpes · Answer

Sorry for the delay in responding but I've been out all day. The following is very rushed so watch out for bugs: using System; using System.Collections.Generic; class Flow { public double Src {get; set;} public double Des {get; set;} public double Port {get; set;} public double Field4 {get; set;} public double Field5 {get; set;} public double Field6 {get; set;} public double Field7 {get; set;} public double Field8 {get; set;} public double Field9 {get; set;} public Flow(double src double des double port double field4 double field5 double field6 double field7 double field8 double field9) { Src = src; Des = des; Port = port; Field4 = field4; Field5 = field5; Field6 = field6; Field7 = field7; Field8 = field8; Field9 = field9; } public override string ToString() { return String.Format((Src={0} Des={1} Port={2} Field4={3} Field5={4} Field6={5} Field7={6} Field8={7} Field9={8}) Src Des Port Field4 Field5 Field6 Field7 Field8 Field9); } } static class FixedWidth { static double width; // fixed width static void Main() { List > clusters = new List >(); List centroids = new List (); // data all set to default value of zero for now double[] src = new double[12]; double[] des = new double[12]; double[] port = new double[12]; double[] field4 = new double[12]; double[] field5 = new double[12]; double[] field6 = new double[12]; double[] field7 = new double[12]; double[] field8 = new double[12]; double[] field9 = new double[12]; List data = new List (); for(int i = 0; i { Flow f = new Flow(src[i] des[i] port[i] field4[i] field5[i] field6[i] field7[i] field8[i] field9[i]); data.Add(f); } width = 2.25; // or whatever List cluster = new List (); // create cluster cluster.Add(data[0]); // add first reading clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[0]); // add centroid of new cluster to centroids list for(int i = 1; i { int closest = -1; // impossible value double minDistance = Double.MaxValue; // likewise for (int j = 0; j { double distance = GetDistance(data[i] centroids[j]); if (distance { minDistance = distance; closest = j; } } if (minDistance { clusters[closest].Add(data[i]); // add reading to closest cluster centroids[closest] = GetCentroid(clusters[closest]); // recalculate centroid of cluster } else { cluster = new List (); // create new cluster cluster.Add(data[i]); clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[i]); // add centroid of new cluster to centroids list } } // print results Console.Clear(); Console.WriteLine(The fixed width is {0}
 width); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following flows :
 i + 1); foreach(Flow f in clusters[i]) Console.WriteLine(f); Console.WriteLine(Centroid : ); Console.WriteLine(centroids[i]); Console.WriteLine(); } // now merge similar clusters if (clusters.Count > 1) { List clusterIndicesToRemove = new List (); for (int i = 0; i { for (int j = i + 1; j { if (GetDistance(centroids[i] centroids[j]) { clusters[j].InsertRange(0 clusters[i]); centroids[j] = GetCentroid(clusters[j]); clusterIndicesToRemove.Add(i); } } } for (int i = clusters.Count - 1; i >= 0; i--) { if (clusterIndicesToRemove.Contains(i)) { clusters.RemoveAt(i); centroids.RemoveAt(i); } } } // print merged results Console.WriteLine(

The merged results are
); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following flows :
 i + 1); foreach(Flow f in clusters[i]) Console.WriteLine(f); Console.WriteLine(Centroid : ); Console.WriteLine(centroids[i]); Console.WriteLine(); } Console.ReadKey(); } static Flow GetCentroid(List cluster) { double[] sum = new double[9]; foreach(Flow f in cluster) { sum[0] += f.Src; sum[1] += f.Des; sum[2] += f.Port; sum[3] += f.Field4; sum[4] += f.Field5; sum[5] += f.Field6; sum[6] += f.Field7; sum[7] += f.Field8; sum[8] += f.Field9; } for(int i = 0; i return new Flow(sum[0] sum[1] sum[2] sum[3] sum[4] sum[5] sum[6] sum[7] sum[8]); } static double GetDistance(Flow f1 Flow f2) { double[] d = new double[9]; d[0] = f1.Src - f2.Src; d[1] = f1.Des - f2.Des; d[2] = f1.Port - f2.Port; d[3] = f1.Field4 - f2.Field4; d[4] = f1.Field5 - f2.Field5; d[5] = f1.Field6 - f2.Field6; d[6] = f1.Field7 - f2.Field7; d[7] = f1.Field8 - f2.Field8; d[8] = f1.Field9 - f2.Field9; double sum = 0; for(int i = 0; i return Math.Sqrt(sum); } }

Vulpes · Answer

Do you mean that: 1. You want to cluster 1 particular field of the class (say src) as was done with the temperature field in the previous posts; or 2. You want to cluster all 9 fields of the class giving them equal weightings using a 9-dimensional Euclidean distance function?

Vulpes · Answer

Yes you'll have to create a class (Reading say) containing the temperature and the corresponding sensor ID and a cluster will then be a List rather than a List . It's not difficult to change it. Here's the code: using System; using System.Collections.Generic; class Reading { public double Temperature {get; set;} public int SensorId {get; set;} public Reading(double temperature int sensorId) { Temperature = temperature; SensorId = sensorId; } } static class FixedWidth { static double width; // fixed width static void Main() { List > clusters = new List >(); List centroids = new List (); // sample data double[] data = {30 28 31.5 34 34.2 29.5 33 31.4 28.7 29.9 36 32.6}; int[] sensors = {1 2 2 3 3 1 2 4 1 2 3 4}; width = 2.25; List cluster = new List (); // create cluster cluster.Add(new Reading(data[0] sensors[0])); // add first reading clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[0]); // add centroid of new cluster to centroids list for(int i = 1; i { int closest = -1; // impossible value double minDistance = Double.MaxValue; // likewise for (int j = 0; j { double distance = Math.Abs(data[i] - centroids[j]); if (distance { minDistance = distance; closest = j; } } if (minDistance { clusters[closest].Add(new Reading(data[i] sensors[i])); // add reading to closest cluster centroids[closest] = GetCentroid(clusters[closest]); // recalculate centroid of cluster } else { cluster = new List (); // create new cluster cluster.Add(new Reading(data[i] sensors[i])); clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[i]); // add centroid of new cluster to centroids list } } // print results Console.Clear(); Console.WriteLine(The fixed width is {0}
 width); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following values (sensor Id in brackets) :
 i + 1); Console.Write(	); foreach(Reading r in clusters[i]) Console.Write({0}({1})  r.Temperature r.SensorId); Console.Write( - Centroid {0:F3} centroids[i]); Console.WriteLine(); } // now merge similar clusters if (clusters.Count > 1) { List clusterIndicesToRemove = new List (); for (int i = 0; i { for (int j = i + 1; j { if (Math.Abs(centroids[i] - centroids[j]) { clusters[j].InsertRange(0 clusters[i]); //centroids[j] = GetCentroid(clusters[j]); // changed to line below centroids[j] = (centroids[i] + centroids[j])/ 2.0; clusterIndicesToRemove.Add(i); } } } for (int i = clusters.Count - 1; i >= 0; i--) { if (clusterIndicesToRemove.Contains(i)) { clusters.RemoveAt(i); centroids.RemoveAt(i); } } } // print merged results Console.WriteLine(

The merged results are
); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following values (sensor Id in brackets) :
 i + 1); Console.Write(	); foreach(Reading r in clusters[i]) Console.Write({0}({1})  r.Temperature r.SensorId); Console.Write( - Centroid {0:F3} centroids[i]); Console.WriteLine(); } Console.ReadKey(); } static double GetCentroid(List cluster) { double sum = 0.0; foreach(Reading r in cluster) sum += r.Temperature; return sum / cluster.Count; } }

Aqua · Answer

Hello I want to save in addition the sensor ID with the tempreture value which means when I said that this value is outlier I want to know it comes from which sensor. For ex. when the value 80 is outlier I want to know that it comes from sensor no. 1. what is the more suitable data type is it the class? where it contains the tempreture value & the sensor ID. this means that I need a list of classes. is it right? I want to edit the fixed-width algorithm & the merge algorithm to fit my need. is it possible?? and how can I fix it? Many Thanks

Vulpes · Answer

TBH I'd never heard of it before but a quick google found this ( http://www.codeproject.com/KB/recipes/K_nearest_neighbor.aspx ).

Aqua · Answer

how can I implement the K Nearest Neighbor KNN algorithm on the resulted clusters???

Aqua · Answer

Yes my work will depend on the merged clusters not on the original clusters

Vulpes · Answer

I mean that if you do something subsequently with the merged cluster which assumes that the centroid is the actual center of the data vectors as it was with the original clusters then this could lead to inconsistencies in the calculations.

Aqua · Answer

i can't understand what u mean by  However you'll have some problems if you need to process that cluster again as the centroid won't coincide with the reality of the situation.

Vulpes · Answer

Yes if the centroid of the new cluster has to be the mean of the old ones then that line will be: centroids[j] = (centroids[i] + centroids[j])/ 2.0; However you'll have some problems if you need to process that cluster again as the centroid won't coincide with the reality of the situation.

Aqua · Answer

sorry but the new centroid of the new cluster will be the mean of C1 & C2 then: centroids[j] = GetCentroid(clusters[j]) will be centroids[i] + centroids[j] / 2 is this right?

Aqua · Answer

Thanks for prompt response :)

Vulpes · Answer

OK in the light of that info I've added some new code (highlighted) to the program: using System; using System.Collections.Generic; static class FixedWidth { static double width; // fixed width static void Main() { List > clusters = new List >(); List centroids = new List (); // sample data double[] data = {30 28 31.5 34 34.2 29.5 33 31.4 28.7 29.9 36 32.6}; width = 2.25; List cluster = new List (); // create cluster cluster.Add(data[0]); // add first data item clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[0]); // add centroid of new cluster to centroids list for(int i = 1; i { int closest = -1; // impossible value double minDistance = Double.MaxValue; // likewise for (int j = 0; j { double distance = Math.Abs(data[i] - centroids[j]); if (distance { minDistance = distance; closest = j; } } if (minDistance { clusters[closest].Add(data[i]); // add data to closest cluster centroids[closest] = GetCentroid(clusters[closest]); // recalculate centroid of cluster } else { cluster = new List (); // create new cluster cluster.Add(data[i]); clusters.Add(cluster); // add cluster to clusters list centroids.Add(data[i]); // add centroid of new cluster to centroids list } } // print results Console.Clear(); Console.WriteLine(The fixed width is {0}
 width); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following values :
 i + 1); Console.Write(	); foreach(double d in clusters[i]) Console.Write({0}  d); Console.Write( - Centroid {0:F3} centroids[i]); Console.WriteLine(); } // now merge similar clusters if (clusters.Count > 1) { List clusterIndicesToRemove = new List (); for (int i = 0; i { for (int j = i + 1; j { if (Math.Abs(centroids[i] - centroids[j]) { clusters[j].InsertRange(0 clusters[i]); centroids[j] = GetCentroid(clusters[j]); clusterIndicesToRemove.Add(i); } } } for (int i = clusters.Count - 1; i >= 0; i--) { if (clusterIndicesToRemove.Contains(i)) { clusters.RemoveAt(i); centroids.RemoveAt(i); } } } // print merged results Console.WriteLine(

The merged results are
); for(int i = 0; i { Console.WriteLine(
Cluster {0} contains the following values :
 i + 1); Console.Write(	); foreach(double d in clusters[i]) Console.Write({0}  d); Console.Write( - Centroid {0:F3} centroids[i]); Console.WriteLine(); } Console.ReadKey(); } static double GetCentroid(List cluster) { double sum = 0.0; foreach(double d in cluster) sum += d; return sum / cluster.Count; } } Please note that: 1. For consistency with how the data vectors are added to a cluster the inter-cluster distance has to be ' 2. The centroid of the new cluster won't be the mean of the centroids of the two merged clusters unless those clusters have the same number of data vectors. I've therefore recalculated it to be the mean of all data vectors of the new cluster. 3. To get some clusters to merge I've changed the fixed width in the sample data to 2.25 which results in the first two clusters being merged. Technically the first one is merged into the second and then the first one is removed rather than creating a new one. The clusters are then automatically renumbered.

Aqua · Answer

I mean by similar: A pair of clusters c1 and c2 are similar if the inter-cluster distance d(c1 c2) between their centers is less than the width w. If c1 and c2 are similar then a new cluster c3 is produced whose center is the mean of the centers of c1 and c2 and whose number of data vectors is the sum of those in c1 and c2. The merging procedure compares each cluster ci with clusters {ci+1 ci+2 ...} and merges ci with the first cluster cj such that d(ci cj) i should such a cj exist.

Aqua · Answer

Many thanks

Vulpes · Answer

Taking those questions in the same order: 1. Technically the Euclidean distance between two points x and y in one dimensional space is: Sqrt( (y - x) * (y - x)) which reduces to the absolute value of (y - X) which is what I've used. 2. From my limited knowledge of the subject I'd have thought it made sense to normalize the data before you cluster it. However the program makes no assumptions about whether the data is normalized or not and so you can do whatever you think is appropriate. 3. It depends what you mean by 'similar' clusters. However if you can devise a 'similarity' test then it's easy to merge clusters each of which is represented by a List in the program. You just need to copy the elements of Cluster B into Cluster A and then remove Cluster B from the Clusters list.

Aqua · Answer

Dear Vulpes Firstly I appreciate your effort and time and would like to thank you very much really it is perfect it is what I want . Secondly I want to ask some questions if you don't mind: Dose this algorithm calculate the Euclidean Distance between the value and the centroid of the cluster to assign the value to the appropriate cluster? is it must to normalize the data before I cluster it? how can I check if there is a pair of similar clusters should be combine i.e. merging of clusters. Sorry for the inconvenience and thank you for your cooperation.

Aqua · Answer

Dear Yes I saw it it is perfect. but I want the the Fixed width clustering :) I want the data to read from the Database it is a stream data i.e. it is sensor readings. To be exact it is a temperature readings from sensor devices. The Fixed width clustering algorithm will be performed on these data to detect the outliers value in these data. thank you for your cooperation & understanding