Implementation of Fixed-width clustering algorithm

Aqua

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

24 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes15y ago
Accepted 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 < data.Length; i++)
{
int closest = -1; // impossible value
double minDistance = Double.MaxValue; // likewise

for (int j = 0; j < clusters.Count; j++)
{
double distance = Math.Abs(data[i] - centroids[j]);
if (distance < minDistance)
{
minDistance = distance;
closest = j;
}
}

if (minDistance <= width)
{
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}\n", width);

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following values :\n", i + 1);
Console.Write("\t");
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;
}

}
0
Vulpes13y ago
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 < 9; i++) sum[i] = sum[i] / Flows.Count;
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 < src.Length; 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 < data.Flows.Count; i++)
{
int closest = -1; // impossible value
double minDistance = Double.MaxValue; // likewise

for (int j = 0; j < clusters.Count; j++)
{
double distance = GetDistance(data.Flows[i], centroids[j]);
if (distance < minDistance)
{
minDistance = distance;
closest = j;
}
}

if (minDistance <= width)
{
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}\n", width);

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following flows :\n", 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 < clusters.Count - 1; i++)
{
for (int j = i + 1; j < clusters.Count; j++)
{
if (GetDistance(centroids[i], centroids[j]) <= width)
{
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("\n\nThe merged results are\n");

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following flows :\n", 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 < 9; i++) sum += d[i] * d[i];
return Math.Sqrt(sum);
}

}
0
Vulpes13y ago
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.
0
Vulpes13y ago
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 < src.Length; 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.
0
Vulpes13y ago
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.
0
Vulpes13y ago
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 < src.Length; 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 < data.Count; i++)
{
int closest = -1; // impossible value
double minDistance = Double.MaxValue; // likewise

for (int j = 0; j < clusters.Count; j++)
{
double distance = GetDistance(data[i], centroids[j]);
if (distance < minDistance)
{
minDistance = distance;
closest = j;
}
}

if (minDistance <= width)
{
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}\n", width);

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following flows :\n", 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 < clusters.Count - 1; i++)
{
for (int j = i + 1; j < clusters.Count; j++)
{
if (GetDistance(centroids[i], centroids[j]) <= width)
{
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("\n\nThe merged results are\n");

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following flows :\n", 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 < 9; i++) sum[i] = sum[i] / cluster.Count;
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 < 9; i++) sum += d[i] * d[i];
return Math.Sqrt(sum);
}

}
0
Vulpes13y ago
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?
0
Vulpes15y ago
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 < data.Length; i++)
{
int closest = -1; // impossible value
double minDistance = Double.MaxValue; // likewise

for (int j = 0; j < clusters.Count; j++)
{
double distance = Math.Abs(data[i] - centroids[j]);
if (distance < minDistance)
{
minDistance = distance;
closest = j;
}
}

if (minDistance <= width)
{
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}\n", width);

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following values (sensor Id in brackets) :\n", i + 1);
Console.Write("\t");
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 < clusters.Count - 1; i++)
{
for (int j = i + 1; j < clusters.Count; j++)
{
if (Math.Abs(centroids[i] - centroids[j]) <= width)
{
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("\n\nThe merged results are\n");

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following values (sensor Id in brackets) :\n", i + 1);
Console.Write("\t");
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;
}

}
0
Aqua15y ago
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
0
Vulpes15y ago
TBH, I'd never heard of it before but a quick google found this (http://www.codeproject.com/KB/recipes/K_nearest_neighbor.aspx).
0
Aqua15y ago
how can I implement the K Nearest Neighbor KNN algorithm on the resulted clusters???
0
Aqua15y ago
Yes, my work will depend on the merged clusters not on the original clusters
0
Vulpes15y ago
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.
0
Aqua15y ago
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."
0
Vulpes15y ago
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.

0
Aqua15y ago
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?

0
Aqua15y ago
Thanks for prompt response :)
0
Vulpes15y ago
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 < data.Length; i++)
{
int closest = -1; // impossible value
double minDistance = Double.MaxValue; // likewise

for (int j = 0; j < clusters.Count; j++)
{
double distance = Math.Abs(data[i] - centroids[j]);
if (distance < minDistance)
{
minDistance = distance;
closest = j;
}
}

if (minDistance <= width)
{
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}\n", width);

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following values :\n", i + 1);
Console.Write("\t");
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 < clusters.Count - 1; i++)
{
for (int j = i + 1; j < clusters.Count; j++)
{
if (Math.Abs(centroids[i] - centroids[j]) <= width)
{
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("\n\nThe merged results are\n");

for(int i = 0; i < clusters.Count; i++)
{
Console.WriteLine("\nCluster {0} contains the following values :\n", i + 1);
Console.Write("\t");
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 '<=' (rather than just '<' ) the fixed width.

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.
0
Aqua15y ago
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) < w and j > i, should such a cj exist.
0
Aqua15y ago
Many thanks
0
Vulpes15y ago
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.
0
Aqua15y ago
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:
1. Dose this algorithm calculate the Euclidean Distance between the value and the centroid of the cluster to assign the value to the appropriate cluster?
2. is it must to normalize the data before I cluster it?
3. 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.
0
Aqua15y ago
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
0
Vulpes15y ago
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.
0