To jest stara wersja strony!
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace Morcinek.Machine_Learning
{
/// <summary>
/// Klasa odpowiedzialna za zbudowanie drzewa decyzyjnego i na jego podstawie
/// do klasyfikowania wectora atrybutów do kategorii docelowych
/// </summary>
public class DecisionTree
{
#region Members
private ILeaf m_rootNode = null;
private object[][] m_learingTable = null; // zbiór uczący
/// <summary>
/// Zawiera w tablicy nazwy atrybutów konieczne do rozszyfrowania, które Testy jeszcze zostały
/// </summary>
private string[] m_testNameList = null;
/// <summary>
/// Indeks pod jakim można w zbiorze uczącym znaleźć przydzieloną kategorię
/// </summary>
private int m_categoryIndex;
private AttrChangeCollection m_attrChangeCollection;
private double m_entropyTreshhold = 0.14;
#endregion
#region Constructor
public DecisionTree()
{
m_attrChangeCollection = new AttrChangeCollection();
}
#endregion
#region Public Methods
/// <summary>
/// Rozpoczyna proces budowania drzewa decyzyjnego
/// </summary>
/// <param name="learningTable">Zbiór uczący</param>
/// <param name="attributesNames">Nazwy kolejnych atrybutów</param>
public void Initialize(object[][] learningTable, string[] attributesNames)
{
List<int> tresholds;
List<int> S;
m_learingTable = learningTable; // Przypisanie zbioru uczącego
m_categoryIndex = learningTable[0].Length - 1;
List<int> P = new List<int>();
for (int i = 0; i < m_learingTable.Length; i++) // Zamiana zbioru na indeksy
P.Add(i);
/*for (int i = 0; i < m_categoryIndex; i++) // Próba zagregowania każdego atrybutu
{
tresholds = DiscreteDown(P, i);
m_attrChangeCollection.Add(tresholds, i);
}
m_attrChangeCollection.Change(m_learingTable); //*/
m_testNameList = attributesNames;
S = new List<int>();
for (int i = 0; i < m_testNameList.Length; i++) // Testy tożsame z nowymi atrybutami
S.Add(i);
int d = ChooseCategory(P);
StreamWriter sw = new StreamWriter("nazwa_pliku.txt", false); //tworzy plik "nazwa_pliku.txt" jezeli taki nie istnieje, lub otwiera juz istniejacy plik nie niszczac zawartosci i bedzie dopisywac na koncu
sw.WriteLine("digraph G {"); //zapisuje do pliku tekst
m_rootNode = BuildTree(P, d, S);
string temp;
ShowedNode showedNode = m_rootNode.ShowTree(out temp);
showedNode.GetGraphvizName(sw);
sw.WriteLine("}"); //zapisuje do pliku nastepny tekst
sw.Flush(); //czysci bufor, wszystko co bylo w buferze zostaje zapisane do pliku
sw.Close(); // zamyka plik
m_attrChangeCollection.WriteAggregateValues();
}
/// <summary>
/// Funcja zwraca nowo stworzony węzęł lub liść(jeśli nie ma sensu dla węzła)
/// </summary>
/// <param name="P">Indeksy ze zbioru uczącego z których korzystamy</param>
/// <param name="d">Domyślna etykieta</param>
/// <param name="S">Indeksy dla nazw atrybutów z których można testy stworzyć</param>
/// <returns>Liść lub węzeł</returns>
private ILeaf BuildTree(List<int> P, int d, List<int> S)
{
if (P.Count == 0) // kryterium Stopu
return new TermostatLeaf(d, P); // Zostaje kategoria domyślna
ILeaf tempLeaf = OnlyOneCategory(P); // Jedyna kategoria
if (tempLeaf != null) // kryterium Stopu
return tempLeaf;
if (S.Count == 0) // kryterium Stopu
return new TermostatLeaf(ChooseCategory(P), P); // Najczęściej pojawiająca się kategoria
TermostatNode node = new TermostatNode();
int testIndex = ChooseTest(P, S);
NominalTest t = new NominalTest(m_testNameList[S[testIndex]], S[testIndex]); // Określamy który atrybut jest dla tego testu
List<int> STemp = new List<int>(S);
STemp.RemoveAt(testIndex); // Wyrzucenie już użytego testu
foreach (int index in P)
{
t.AddResult((int)m_learingTable[index][t.AttributeIndex]);
}
node.Test = t; // Przypisanie testu do node'a
d = ChooseCategory(P);
node.Category = d; // Przypisanie większościowej kategorii do node'a
node.P = P; // Przypisanie pozostałych przykładów do node'a
foreach (int r in t.Results)
{
List<int> PTemp = new List<int>(); // Utworzenie nowej listy tylko z tych danych które prowadzą do 'r'
foreach (int indexP in P) // Dla każdego przykładu etykietowanego
{
if ((int)m_learingTable[indexP][t.AttributeIndex] == r) // Czy atrybut przykładu zgadza się z naszym rezulatatem 'r'
{
PTemp.Add(indexP); // Dodanie do P które przekażemy do niższego węzła
}
}
node.DictOfNodes[r] = BuildTree(PTemp, d, STemp); // Najpierw zostanie zbudowany nowy węzeł dopiero później nie zostanie nigdzie dodany
}
return node;
}
/// <summary>
/// Funkcja zakwalifikuje podany ciąg atrybutów do jednej kategorii
/// </summary>
/// <param name="attributes">Tablica atrybutów</param>
/// <returns>Kategoria</returns>
public int FindCategory(object[] attributes)
{
m_attrChangeCollection.Change(attributes);
return m_rootNode.GetCategory(attributes);
}
#endregion
#region Private Methods
/// <summary>
/// Wybiera najbardziej liczną kategorię w podanym zbiorze uczącym
/// </summary>
/// <param name="indexList">Lista indeksów mówiących które tablice z zbioru uczącego są w grze</param>
/// <param name="d"></param>
/// <returns>Kategoria</returns>
private int ChooseCategory(List<int> P)
{
// Najbardziej liczną kategorię powinno się na razie zwracać.
Dictionary<int, int> categoryCounter = new Dictionary<int, int>();
int category = 0;
foreach (int var in P)
{
category = (int)m_learingTable[var][m_categoryIndex]; // Kategoria tych uczących które jeszcze zostały w indexList
if (categoryCounter.ContainsKey(category))
{
categoryCounter[category]++;
}
else
{
categoryCounter.Add(category, 1);
}
}
int biggerAmount = 0;
foreach (int key in categoryCounter.Keys)
{
if (biggerAmount < categoryCounter[key])
{
category = key;
}
}
return (int)category;
}
/// <summary>
/// Wybiera najlepszy test na podstawie najmniejszej entropii
/// </summary>
/// <param name="P">Lista indeksów pozostałego zbioru uczącego</param>
/// <param name="S">Lista pozostałych testów</param>
/// <returns>Indeks wybranego testu</returns>
private int ChooseTest(List<int> P, List<int> S)
{
if (S.Count > 0)
{
NominalTest test = null;
double minEntropy = Double.PositiveInfinity;
int bestIndex = 0;
for (int i = 0; i < S.Count; i++)
{
test = new NominalTest(m_testNameList[S[i]], S[i]); // Określamy który atrybut jest dla tego testu
double testEntropy = CountTestEntropy(P, test);
if (testEntropy < minEntropy)
{
minEntropy = testEntropy;
bestIndex = i;
}
}
return bestIndex;
}
else
{
throw new Exception("Brak sprawdzania czy testy sie nie skończyły");
}
}
/// <summary>
/// Sprawdza czy w zbiorze uczącym jest tylko jedna kategoria
/// </summary>
/// <param name="P">Lista indeksów pozostałego zbioru uczącego</param>
/// <returns>Liść lub null w przypadku błędu</returns>
private ILeaf OnlyOneCategory(List<int> P)
{
if (P.Count > 0)
{
bool repeated = false;
int category = (int)m_learingTable[P[0]][m_categoryIndex];
for (int i = 1; i < P.Count; i++)
{
if (category != (int)m_learingTable[P[i]][m_categoryIndex]) // Jeśli któryś jest inny niż pierwszy
repeated = true;
}
if (!repeated) // Jeśli się nie powtórzył
{
return new TermostatLeaf(category, P); // Zwraca jedyną kategorię
}
return null;
}
else
{
throw new Exception("Brak sprawdzania czy zbiór uczący nie jest pusty");
}
}
/// <summary>
/// Wylicza entropię danego przykładu trenującego dla danego testu
/// </summary>
/// <param name="P">Lista indeksów pozostałego zbioru uczącego</param>
/// <param name="test">Test (atrybut)</param>
/// <returns>Entropia</returns>
private double CountTestEntropy(List<int> P, ITest test)
{
// Przez |P| nie dzielimy gdyż nie zmienia to nic
double allSum = 0;
int attrIndex = test.AttributeIndex;
Dictionary<int, int> dict; // Kategoria -> ilość wystąpień Kategorii
List<int> result = new List<int>();
List<int> temp = new List<int>();
foreach (int indexP in P)
if (!result.Contains((int)m_learingTable[indexP][attrIndex]))
result.Add((int)m_learingTable[indexP][attrIndex]); // Pozbieranie możliwych rezultatów
foreach (int r in result) // Dla kolejnych rezultatów testu
{
dict = new Dictionary<int,int>();
temp.Clear();
foreach (int indexP in P)
{
if ((int)m_learingTable[indexP][attrIndex] == r) // Czy przykład należy do tego rezultatu
{
temp.Add(indexP);
}
}
allSum += CountEntropy(temp) * temp.Count / P.Count;; // Entropia Et(P) czyli suma po r |Ptr|/|P| * Etr(P)
}
return allSum;
}
/// <summary>
/// Rekurencyjnie wywoływana funkcja dyskretyzacji-zstępującej
/// </summary>
/// <param name="P">Zbiór przykładów</param>
/// <param name="attrIndex">Indeks opisujący atrybut</param>
/// <returns>Lista punktów dzielących wartości</returns>
private List<int> DiscreteDown(List<int> P, int attrIndex)
{
if (OnlyOneValue(P,attrIndex)) // Kryterium Stopu. Jeśli została tylko jedna wartość atrybutu w zbiorze uczącym
return new List<int>();
int treshold;
List<int> P0;
List<int> P1;
treshold = ChooseTreshold(P, attrIndex); // Wybranie progu
SplitList(P, attrIndex, treshold, out P0, out P1);
double information = CountEntropy(P);
double entropy = (CountEntropy(P0) * P0.Count + CountEntropy(P1) * P1.Count) / P.Count;
if (information - entropy <= m_entropyTreshhold) // Kryterium Stopu bazujące na wzrastaniu informacji
return new List<int>();
List<int> fi0 = DiscreteDown(P0, attrIndex); // Dzielenie zbioru < treshold
List<int> fi1 = DiscreteDown(P1, attrIndex); // Dzielenie zbioru >= treshold
List<int> ret = new List<int>(fi0);
ret.Add(treshold);
ret.AddRange(fi1);
return ret;
}
/// <summary>
/// Wylicza tą entropię z logarytmem
/// </summary>
/// <param name="top"></param>
/// <param name="bottom"></param>
/// <returns></returns>
private double CountEntropy(int top, int bottom)
{
double temp = (double)top / (double)bottom;
return - temp * Math.Log(temp, 2);
}
/// <summary>
/// Oblicza entropię Etr(P) czyli sumuje entropie po wszystkiech kategoriach pojęcia docelowego
/// </summary>
/// <param name="P">Zbiór uczący</param>
/// <returns></returns>
private double CountEntropy(List<int> P)
{
int value;
double sum = 0;
Dictionary<int, int> dict = new Dictionary<int,int>(); // Kategoria -> ilość wystąpień Kategorii
List<int> result = new List<int>();
foreach (int indexP in P)
{
value = (int)m_learingTable[indexP][m_categoryIndex];
if (dict.ContainsKey(value))
dict[value]++; // Zliczanie jak liczne są poszczególne kategorie
else
dict[value] = 1;
}
sum = 0;
foreach (int count in dict.Values)
{
sum += CountEntropy(count, P.Count); // Wyliczanie entropii Etr(P)
}
//sum *= P.Count; // Mnożenie przez wagę (ilość danego rezultatu)
return sum;
}
/// <summary>
/// Wybiera próg dzielący wartości
/// </summary>
/// <param name="P">Zbiór przykładów</param>
/// <param name="attrIndex">Indeks opisujący atrybut</param>
/// <returns>Próg</returns>
private int ChooseTreshold(List<int> P, int attrIndex)
{
if (P.Count > 0)
{
double entropy;
double minEntropy = double.PositiveInfinity;
int bestTreshold = 0;
List<int> P0;
List<int> P1;
List<int> tresholdList = new List<int>();
foreach (int indexP in P)
{
int tempa = (int)m_learingTable[indexP][attrIndex];
if (!tresholdList.Contains(tempa))
tresholdList.Add(tempa); // Wybranie możliwości podziału
}
tresholdList.Sort();
foreach (int treshold in tresholdList) // Dla kolejnych wartości rozdzielających (progowych)
{
SplitList(P, attrIndex, treshold, out P0, out P1);
entropy = (CountEntropy(P0) * P0.Count + CountEntropy(P1) * P1.Count) / P.Count;
if (entropy < minEntropy)
{
minEntropy = entropy;
bestTreshold = treshold;
}
}
return bestTreshold;
}
else
{
throw new Exception("P jest pusty, nie można wyznaczyć progu");
}
}
/// <summary>
/// Dzieli zbiór przykładów na mniejszy i równy od progu oraz większy od progu
/// </summary>
/// <param name="P">Zbiór przykładów</param>
/// <param name="attrIndex">Indeks opisujący atrybut</param>
/// <param name="treshold">Próg podziału</param>
/// <param name="P0">Wartości poniżej progu</param>
/// <param name="P1">Wartości powyżej progu</param>
private void SplitList(List<int> P, int attrIndex, int treshold, out List<int> P0, out List<int> P1)
{
P0 = new List<int>(P);
P1 = new List<int>();
for (int i = 0; i < P0.Count; i++) // Jedziemy do końca listy która nam się skraca, może inny warunek
{
if ((int)m_learingTable[P0[i]][attrIndex] > treshold) // Jeśli większy niż treshold to:
{
P1.Add(P0[i]); // Dodajemy do większego od treshold
P0.RemoveAt(i); // Zdejmujemy z mniejszego lub równego od treshold
i--;
}
}
}
/// <summary>
/// Sprawdza czy tylko jedna wartość występuje w danym zbiorze
/// </summary>
/// <param name="P">Zbiór przykładów</param>
/// <param name="attrIndex">Indeks opisujący atrybut</param>
/// <returns></returns>
private bool OnlyOneValue(List<int> P, int attrIndex)
{
int value = (int)m_learingTable[P[0]][attrIndex];
foreach (int indexP in P)
{
if ((int)m_learingTable[indexP][attrIndex] != value)
return false;
}
return true;
}
#endregion
}
}