السلام عليكــم ورحمـة الله وبركاتــه ،،
مشروع تخرجي بعنوان data mining
واستخدمت الخورزميتين k-mean و Decision Tree
ولكن ..احس اني ماني متمكنة كثير من الاكواد
فياليت الي يقدر يشرحلي الاكواد ..او يدلني على مكان اقدر استفيد منه
code " decision tree"
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Data;
namespace DataMiningProject
{
public class Attribute
{
ArrayList mValues;
string mName;
object mLabel;
public Attribute(string name, string[] values)
{
mName = name;
mValues = new ArrayList(values);
mValues.Sort();
}
public Attribute(object Label)
{
mLabel = Label;
mName = string.Empty;
mValues = null;
}
public string AttributeName
{
get
{
return mName;
}
}
public string[] values
{
get
{
if (mValues != null)
return (string[])mValues.ToArray(typeof(string));
else
return null;
}
}
public bool isValidValue(string value)
{
return indexValue(value) >= 0;
}
public int indexValue(string value)
{
if (mValues != null)
return mValues.BinarySearch(value);
else
return -1;
}
public override string ToString()
{
if (mName != string.Empty)
{
return mName;
}
else
{
return mLabel.ToString();
}
}
}
public class TreeNode
{
private ArrayList mChilds = null;
private Attribute mAttribute;
public TreeNode(Attribute attribute)
{
if (attribute.values != null)
{
mChilds = new ArrayList(attribute.values.Length);
for (int i = 0; i < attribute.values.Length; i++)
mChilds.Add(null);
}
else
{
mChilds = new ArrayList(1);
mChilds.Add(null);
}
mAttribute = attribute;
}
public void AddTreeNode(TreeNode treeNode, string ValueName)
{
int index = mAttribute.indexValue(ValueName);
mChilds[index] = treeNode;
}
public int totalChilds
{
get
{
return mChilds.Count;
}
}
public TreeNode getChild(int index)
{
return (TreeNode)mChilds[index];
}
public Attribute attribute
{
get
{
return mAttribute;
}
}
public TreeNode getChildByBranchName(string branchName)
{
int index = mAttribute.indexValue(branchName);
return (TreeNode)mChilds[index];
}
}
public class DecisionTree
{
private DataTable mSamples;
private int mTotalPositives = 0;
private int mTotal = 0; // rows . count
private string mTargetAttribute = "result";
private double mEntropySet = 0.0;
/// Return all attributes which there target attribute
/// have yes values
/// samples Vector represent data base table
/// returns num of positives or zero
private int countTotalPositives(DataTable samples)
{
int result = 0;
foreach (DataRow aRow in samples.Rows)
{
if ((bool)aRow[mTargetAttribute] == true)
result++;
}
return result;
}
/// -p+log2p+ - p-log2p-
/// p+ positiv
/// p- negativ
/// /// calculate entropy
///"positives" Num of positives values of an attribute
// entropy (p1,p2,p3) = - p1 log p1 - p2 log p2 - p3 log p3
private double calcEntropy(int positives, int negatives)
{
int total = positives + negatives;
double ratioPositive = (double)positives / total;
// 3\7
double ratioNegative = (double)negatives / total;
// 4\7
// p log p
if (ratioPositive != 0)
ratioPositive = -(ratioPositive) * System.Math.Log(ratioPositive, 2);
if (ratioNegative != 0)
ratioNegative = -(ratioNegative) * System.Math.Log(ratioNegative, 2);
double result = ratioPositive + ratioNegative;
return result;
}
private void getValuesToAttribute(DataTable samples, Attribute attribute, string value, out int positives, out int negatives)
{
positives = 0;
negatives = 0;
foreach (DataRow aRow in samples.Rows)
{
// attribute : weather ,, Value : Sunny ,, TargetAttribute : true ..Add 1 to pos
// attribute : weather ,, Value : Sunny ,, TargetAttribute : false ..Add 1 to neg
if (((string)aRow[attribute.AttributeName] == value))
if ((bool)aRow[mTargetAttribute] == true)
positives++;
else
negatives++;
}
}
private double gain(DataTable samples, Attribute attribute)
{
string[] values = attribute.values;
double sum = 0.0;
//for columns
for (int i = 0; i < values.Length; i++)
{
int positives, negatives;
//calc pos neg
positives = negatives = 0;
getValuesToAttribute(samples, attribute, values, out positives, out negatives);
double entropy = calcEntropy(positives, negatives); //-p log p
sum += -(double)(positives + negatives) / mTotal * entropy;
}
return mEntropySet + sum;
}
private Attribute getBestAttribute(DataTable samples, Attribute[] attributes)
{
double maxGain = 0.0;
Attribute result = null;
foreach (Attribute attribute in attributes)
{
double aux = gain(samples, attribute);
if (aux > maxGain)
{
maxGain = aux;
result = attribute;
}
}
return result;
}
private bool allSamplesPositives(DataTable samples, string targetAttribute)
{
foreach (DataRow row in samples.Rows)
{
if (((bool)row[targetAttribute])==(false))
return false;
}
return true;
}
private bool allSamplesNegatives(DataTable samples, string targetAttribute)
{
foreach (DataRow row in samples.Rows)
{
if (((bool)row[targetAttribute])==(true))
return false;
}
return true;
}
private ArrayList getDistinctValues(DataTable samples, string targetAttribute)
{
ArrayList distinctValues = new ArrayList(samples.Rows.Count);
foreach (DataRow row in samples.Rows)
{
if (distinctValues.IndexOf(row[targetAttribute]) == -1) distinctValues.Add(row[targetAttribute]);
}
return distinctValues;
}
private object getMostCommonValue(DataTable samples, string targetAttribute)
{
ArrayList distinctValues = getDistinctValues(samples, targetAttribute);
int[] count = new int[distinctValues.Count];
foreach (DataRow row in samples.Rows)
{
int index = distinctValues.IndexOf(row[targetAttribute]);
count[index]++;
}
int MaxIndex = 0;
int MaxCount = 0;
for (int i = 0; i < count.Length; i++)
{
if (count > MaxCount)
{
MaxCount = count;
MaxIndex = i;
}
}
return distinctValues[MaxIndex];
}
private TreeNode internalMountTree(DataTable samples, string targetAttribute, Attribute[] attributes)
{
if (allSamplesPositives(samples, targetAttribute) == true)
return new TreeNode(new Attribute(true));
if (allSamplesNegatives(samples, targetAttribute) == true)
return new TreeNode(new Attribute(false));
if (attributes.Length == 0)
return new TreeNode(new Attribute(getMostCommonValue(samples, targetAttribute)));
mTotal = samples.Rows.Count;
mTargetAttribute = targetAttribute;
mTotalPositives = countTotalPositives(samples);
mEntropySet = calcEntropy(mTotalPositives, mTotal - mTotalPositives);
Attribute bestAttribute = getBestAttribute(samples, attributes);
TreeNode root = new TreeNode(bestAttribute);
DataTable aSample = samples.Clone();
foreach (string value in bestAttribute.values)
{
aSample.Rows.Clear();
DataRow[] rows = samples.Select(bestAttribute.AttributeName + " = " + "'" + value + "'");
foreach (DataRow row in rows)
{
aSample.Rows.Add(row.ItemArray);
}
ArrayList aAttributes = new ArrayList(attributes.Length - 1);
for (int i = 0; i < attributes.Length; i++)
{
if (attributes.AttributeName != bestAttribute.AttributeName)
aAttributes.Add(attributes);
}
if (aSample.Rows.Count == 0)
{
return new TreeNode(new Attribute(getMostCommonValue(aSample, targetAttribute)));
}
else
{
DecisionTree dc3 = new DecisionTree();
TreeNode ChildNode = dc3.mountTree(aSample, targetAttribute, (Attribute[])aAttributes.ToArray(typeof(Attribute)));
root.AddTreeNode(ChildNode, value);
}
}
return root;
}
public TreeNode mountTree(DataTable samples, string targetAttribute, Attribute[] attributes)
{
mSamples = samples;
return internalMountTree(mSamples, targetAttribute, attributes);
}
}
}
code k-mean
using System;
using System.Collections.Generic;
using System.Text;
using System.Data;
namespace DataMiningProject
{
/// <summary>
/// This class implement a KMeans clustering algorithm
/// </summary>
public class KMeans
{
public KMeans()
{
}
/// <summary>
/// Calculates the Euclidean Distance Measure between two data points
/// </summary>
/// <param name="X">An array with the values of an object or datapoint</param>
/// <param name="Y">An array with the values of an object or datapoint</param>
/// <returns>Returns the Euclidean Distance Measure Between Points X and Points Y</returns>
public static double EuclideanDistance(double[] X, double[] Y)
{
int count = 0;
double distance = 0.0;
double sum = 0.0;
if (X.GetUpperBound(0) != Y.GetUpperBound(0))
{
throw new System.ArgumentException("the number of elements in X must match the number of elements in Y");
}
else
{
count = X.Length;
}
for (int i = 0; i < count; i++)
{
sum = sum + Math.Pow(Math.Abs(X - Y), 2);
}
distance = Math.Sqrt(sum);
return distance;
}
/// <summary>
/// Calculates The Mean Of A Cluster OR The Cluster Center
/// </summary>
/// <param name="cluster">
/// A two-dimensional array containing a dataset of numeric values
/// </param>
/// <returns>
/// Returns an Array Defining A Data Point Representing The Cluster Mean or Centroid
/// </returns>
public static double[] ClusterMean(double[,] cluster)
{
int rowCount = 0;
int fieldCount = 0;
double[,] dataSum;
double[] centroid;
rowCount = cluster.GetUpperBound(0) + 1;
fieldCount = cluster.GetUpperBound(1) + 1;
dataSum = new double[1, fieldCount];
centroid = new double[fieldCount];
//((20+30)/2), ((170+160)/2), ((80+120)/2)
for (int j = 0; j < fieldCount; j++)
{
// take column
for (int i = 0; i < rowCount; i++)
{
// add rows values
dataSum[0, j] = dataSum[0, j] + cluster[i, j];
}
centroid[j] = (dataSum[0, j] / rowCount);
}
return centroid;
}
/// <summary>
/// Seperates a dataset into clusters or groups with similar characteristics
/// </summary>
/// <param name="clusterCount">The number of clusters or groups to form</param>
/// <param name="data">An array containing data that will be clustered</param>
/// <returns>A collection of clusters of data</returns>
public static ClusterCollection ClusterDataSet(int clusterCount, double[,] data)
{
int clusterNumber = 0;
int rowCount = data.GetUpperBound(0) + 1;
int fieldCount = data.GetUpperBound(1) + 1;
int stableClustersCount = 0;
int iterationCount = 0;
double[] dataPoint;
Random random = new Random();
Cluster cluster = null;
ClusterCollection clusters = new ClusterCollection();
System.Collections.ArrayList clusterNumbers = new System.Collections.ArrayList(clusterCount);
// Clusters Initialization : put in each cluster
// one row of data (row index Is Cluster Number)
while (clusterNumbers.Count < clusterCount)
{
clusterNumber = random.Next(0, rowCount - 1);
Console.WriteLine("Cluster number " + clusterNumber);
if (!clusterNumbers.Contains(clusterNumber))
{
cluster = new Cluster();
clusterNumbers.Add(clusterNumber);
dataPoint = new double[fieldCount];
// take row [clusterNumber: random] and put its data in data point
Console.WriteLine("nw db---------");
for (int field = 0; field < fieldCount; field++)
{
dataPoint.SetValue((data[clusterNumber, field]), field);
Console.WriteLine(dataPoint[field]);
}
cluster.Add(dataPoint);
clusters.Add(cluster);
}
}
// while the cluster count isn't stable: for two executions the clusters is same
while (stableClustersCount != clusters.Count)
{
stableClustersCount = 0;
//Generate New Clusters and Compare with the clusters(last one)
ClusterCollection newClusters = KMeans.ClusterDataSet(clusters, data);
for (int clusterIndex = 0; clusterIndex < clusters.Count; clusterIndex++)
{
if ((KMeans.EuclideanDistance(newClusters[clusterIndex].ClusterMean, clusters[clusterIndex].ClusterMean)) == 0)
{
//if Mean is equal for new and last it's stable cluster
stableClustersCount++;
}
}
iterationCount++;
clusters = newClusters;
}
return clusters;
}
/// <summary>
/// Seperates a dataset into clusters or groups with similar characteristics
/// </summary>
/// <param name="clusters">A collection of data clusters</param>
/// <param name="data">An array containing data to b eclustered</param>
/// <returns>A collection of clusters of data</returns>
public static ClusterCollection ClusterDataSet(ClusterCollection clusters, double[,] data)
{
// test each point distance to clusters
double[] dataPoint;
double[] clusterMean;
double firstClusterDistance = 0.0;
double secondClusterDistance = 0.0;
int rowCount = data.GetUpperBound(0) + 1;
int fieldCount = data.GetUpperBound(1) + 1;
int position = 0;
// create a new collection of clusters
ClusterCollection newClusters = new ClusterCollection();
for (int count = 0; count < clusters.Count; count++)
{
Cluster newCluster = new Cluster();
newClusters.Add(newCluster);
}
if (clusters.Count <= 0)
{
throw new SystemException("Cluster Count Cannot Be Zero!");
}
//((20+30)/2), ((170+160)/2), ((80+120)/2)
for (int row = 0; row < rowCount; row++)
{
dataPoint = new double[fieldCount];
// take each row and put it in array of double
for (int field = 0; field < fieldCount; field++)
{
dataPoint.SetValue((data[row, field]), field);
}
// distance between point and clusters means
// c1 mean 1, c2 mean= 2, c3 mean= 3
//point 3
//f = 2
//s = 1, f=1
//s =0, f=0 positon c3
for (int cluster = 0; cluster < clusters.Count; cluster++)
{
clusterMean = clusters[cluster].ClusterMean;
if (cluster == 0)
{
firstClusterDistance = KMeans.EuclideanDistance(dataPoint, clusterMean);
Console.WriteLine("firstClusterDistance " + firstClusterDistance);
position = cluster;
}
else
{
secondClusterDistance = KMeans.EuclideanDistance(dataPoint, clusterMean);
Console.WriteLine("secondClusterDistance " + secondClusterDistance);
if (firstClusterDistance > secondClusterDistance)
{
firstClusterDistance = secondClusterDistance;
position = cluster;
}
}
}
newClusters[position].Add(dataPoint);
}
return newClusters;
}
/// <summary>
/// Converts a System.Data.DataTable to a 2-dimensional array
/// </summary>
/// <param name="data">A System.Data.DataTable containing data to cluster</param>
/// <returns>A 2-dimensional array containing data to cluster</returns>
public static double[,] ConvertDataTableToArray(DataTable table)
{
int rowCount = table.Rows.Count;
int fieldCount = table.Columns.Count;
double[,] dataPoints;
double fieldValue = 0.0;
DataRow row;
dataPoints = new double[rowCount, fieldCount];
for (int rowPosition = 0; rowPosition < rowCount; rowPosition++)
{
row = table.Rows[rowPosition];
for (int fieldPosition = 0; fieldPosition < fieldCount; fieldPosition++)
{
try
{
fieldValue = double.Parse(row[fieldPosition].ToString());
}
catch (System.Exception ex)
{
System.Diagnostics.Debug.WriteLine(ex.ToString());
throw new InvalidCastException("Invalid row at " + rowPosition.ToString() + " and field " + fieldPosition.ToString(), ex);
}
dataPoints[rowPosition, fieldPosition] = fieldValue;
}
}
return dataPoints;
}
}
/// <summary>
/// A class containing a group of data with similar characteristics (cluster)
/// </summary>
public class Cluster : System.Collections.CollectionBase
{
private double[] _clusterSum;
/// <summary>
/// The sum of all the data in the cluster
/// </summary>
public double[] ClusterSum
{
get
{
return this._clusterSum;
}
}
private double[] _clusterMean;
/// <summary>
/// The mean of all the data in the cluster
/// </summary>
public double[] ClusterMean
{
get
{
for (int count = 0; count < this[0].Length; count++)
{
this._clusterMean[count] = (this._clusterSum[count] / this.List.Count);
}
return this._clusterMean;
}
}
/// <summary>
/// Adds a single dimension array data to the cluster
/// </summary>
/// <param name="data">A 1-dimensional array containing data that will be added to the cluster</param>
public virtual void Add(double[] data)
{
this.List.Add(data);
if (this.List.Count == 1)
{
this._clusterSum = new double[data.Length];
this._clusterMean = new double[data.Length];
}
for (int count = 0; count < data.Length; count++)
{
this._clusterSum[count] = this._clusterSum[count] + data[count];
}
}
/// <summary>
/// Returns the one dimensional array data located at the index
/// </summary>
public virtual double[] this[int Index]
{
get
{
//return the Neuron at IList[Index]
return (double[])this.List[Index];
}
}
}
/// <summary>
/// A collection of Cluster objects or Clusters
/// </summary>
public class ClusterCollection : System.Collections.CollectionBase
{
/// <summary>
/// Adds a Cluster to the collection of Clusters
/// </summary>
/// <param name="cluster">A Cluster to be added to the collection of clusters</param>
public virtual void Add(Cluster cluster)
{
this.List.Add(cluster);
}
/// <summary>
/// Returns the Cluster at this index
/// </summary>
public virtual Cluster this[int Index]
{
get
{
//return the Neuron at IList[Index]
return (Cluster)this.List[Index];
}
}
}
}