Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:miw:miw08_rbs_ml:decisiontree [2008/06/10 12:19]
miw
pl:miw:miw08_rbs_ml:decisiontree [2017/07/17 08:08] (aktualna)
Linia 1: Linia 1:
-<​code="​csharp">​ +<​code="​Java">​ 
-using System; +package MachineLearning;
-using System.Collections.Generic;​ +
-using System.Text;​ +
-using System.IO;+
  
-namespace Morcinek.Machine_Learning+import java.util.*; 
 + 
 +/** 
 + * Klasa drzewa decyzyjnego. Zbudeje drzewo na podstawie przykładów uczących 
 + * @author Angello 
 + * 
 + */ 
 +public class DecisionTree
 { {
- /// <​summary>​ + private TermostatLeaf m_rootNode = null; 
- /// Klasa odpowiedzialna za zbudowanie drzewa decyzyjnego i na jego podstawie ​ + private Object[][] m_learingTable = null; // zbiór uczący 
- /// do klasyfikowania wectora ​atrybutów do kategorii docelowych +  
- /// </​summary>​ + /** 
- public class DecisionTree +  * Zawiera w tablicy nazwy atrybutów ​konieczne ​do rozszyfrowania,​ które Testy jeszcze zostały 
- { +  *
- #region Members+ private String[] m_testNameList = null;
  
- private ILeaf m_rootNode = null; + /** 
- private object[][] m_learingTable = null; // zbiór ​uczący + * Indeks pod jakim można w zbiorze ​uczącym znaleźć przydzieloną kategorię 
- /// <​summary>​ +  *
- /// Zawiera w tablicy nazwy atrybutów konieczne do rozszyfrowania,​ które Testy jeszcze zostały + private ​Integer m_categoryIndex;
- /// </​summary>​ +
- private ​string[] m_testNameList = null;+
  
- /// <​summary>​ + private ​AttrChangeCollection m_attrChangeCollection;
- /// Indeks pod jakim można w zbiorze uczącym znaleźć przydzieloną kategorię +
- /// </​summary>​ +
- private ​int m_categoryIndex;+
  
- private ​AttrChangeCollection m_attrChangeCollection;+ /** 
 + * Próg entropii używany w agregacji atrybutów porządkowych 
 + */ 
 + private ​double m_entropyTreshhold = 0.091;
  
- private double m_entropyTreshhold ​0.14;+ /** 
 + * Domyślny konstruktor 
 + */ 
 + public DecisionTree() 
 +
 + m_attrChangeCollection ​new AttrChangeCollection(); 
 + }
  
- #​endregion + /** 
- +  * Buduje drzewo decyzyjne  
- #region Constructor + * @param learningTable Zbiór uczący 
- + * @param attributesNames Nazwy kolejnych atrybutów 
- public DecisionTree()+ */ 
 + public void initialize(Object[][] learningTable,​ String[] attributesNames,​ boolean c45) 
 + { 
 + ArrayList<​Integer>​ tresholds; 
 + ArrayList<​Integer>​ S; 
 + m_learingTable = learningTable;​ //​ Przypisanie zbioru uczącego 
 + m_categoryIndex = learningTable[0].length - 1; 
 + ArrayList<​Integer>​ P = new ArrayList<​Integer>​();​ 
 + for (int i = 0; i < m_learingTable.length;​ i++) // Zamiana zbioru na indeksy 
 + P.add(i);​ 
 +  
 + if(c45)
  {  {
- m_attrChangeCollection ​new AttrChangeCollection();+ 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 ArrayList<​Integer>​();​
 + for (int i = 0; i < m_testNameList.length;​ i++) // Testy tożsame z nowymi atrybutami
 + S.add(i);​
  
- #endregion+ Integer d = chooseCategory(P);​
  
- #region Public Methods+ m_rootNode = buildTree(P,​ d, S);
  
- /// <​summary>​ + ShowedNode showedNode ​m_rootNode.showTree();
- /// 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 + WriteFile sw new WriteFile(); 
- + sw.open("​Graph_file.txt"​); 
- tresholds ​DiscreteDown(P, i); + sw.writeLine("​digraph G {"); //zapisuje do pliku tekst 
- m_attrChangeCollection.Add(tresholds, i); + showedNode.getGraphvizName(sw); 
- + sw.close();
- 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);+ sw.writeLine("​}"​); //zapisuje do pliku nastepny tekst 
 + sw.close();​ // zamyka plik
  
- 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 + m_attrChangeCollection.WriteAggregateValues(); 
- sw.WriteLine("​digraph G {"); //zapisuje do pliku tekst + }
-  +
- m_rootNode = BuildTree(P,​ d, S);+
  
- string temp; + /** 
- ShowedNode showedNode = m_rootNode.ShowTree(out temp);+  * Funcja zwraca nowo stworzony węzęł lub liść(jeśli nie ma sensu dla węzła) 
 + * @param P Zbiór uczący 
 + * @param d Domyślna etykieta 
 + * @param S Dostępne testy 
 + * @return Liść lub węzeł 
 + */ 
 + private TermostatLeaf buildTree(ArrayList<​Integer>​ P, Integer d, ArrayList<​Integer>​ S) 
 +
 + if (P.size() == 0) // kryterium Stopu 
 + return new TermostatLeaf(d, P); // Zostaje kategoria domyślna
  
- showedNode.GetGraphvizName(sw);+ TermostatLeaf tempLeaf = onlyOneCategory(P); // Jedyna kategoria 
 + if (tempLeaf != null) // kryterium Stopu 
 + return tempLeaf;
  
 + if (S.size() == 0) // kryterium Stopu
 + return new TermostatLeaf(chooseCategory(P),​ P); // Najczęściej pojawiająca się kategoria
  
- sw.WriteLine("​}"​); //zapisuje do pliku nastepny tekst + Integer testIndex = chooseTest(P, S); 
- sw.Flush(); //czysci bufor, wszystko co bylo w buferze zostaje zapisane do pliku + NominalTest t = new NominalTest(m_testNameList[S.get(testIndex)],​ S.get(testIndex)); // Określamy który atrybut jest dla tego testu 
- sw.Close(); // zamyka plik+ ArrayList<​Integer>​ STemp = new ArrayList<​Integer>​(S);​ 
 + STemp.remove(testIndex); // Wyrzucenie już użytego testu
  
- m_attrChangeCollection.WriteAggregateValues(); + for (Integer index : P) 
- + { 
 + t.AddResult((Integer)m_learingTable[index][t.AttributeIndex]);​
  }  }
  
- + d = chooseCategory(P); 
- /// <​summary>​ + TermostatNode node new TermostatNode(t,​ d, P); 
- /// Funcja zwraca nowo stworzony węzęł lub liść(jeśli nie ma sensu dla węzła+  
- /// </​summary>​ + for (Integer r : t.Results())
- /// <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 + ArrayList<IntegerPTemp = new ArrayList<Integer>​();​ // ​Utworzenie nowej listy tylko z tych danych które prowadzą ​do 'r' 
- return new TermostatLeaf(d,​ P); // Zostaje kategoria domyślna + for (Integer indexP : P) // Dla każdego ​przykładu etykietowanego
- +
- 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<intSTemp = 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'​ + if ((Integer)m_learingTable[indexP][t.AttributeIndex] == r) // Czy atrybut ​przykładu ​zgadza się z naszym rezulatatem '​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
-+
- 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 
  }  }
- + node.addNode(r, buildTree(PTemp,​ d, STemp)); // Najpierw zostanie zbudowany nowy węzeł dopiero później nie zostanie nigdzie dodany
- return ​node;+
  }  }
  
- /// <​summary>​ + return ​node
- /// 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+ /** 
 + * Funkcja zakwalifikuje podany ciąg atrybutów do jednej kategorii 
 + * @param attributes Zbiór atrybutów 
 + * @return Kategoria 
 + */ 
 + public Integer findCategory(Object[] attributes) 
 +
 + m_attrChangeCollection.Change(attributes);​ 
 + return m_rootNode.getCategory(attributes);​ 
 + }
  
- #region Private Methods + /** 
- +  ​* ​Wybiera najbardziej liczną kategorię w podanym zbiorze uczącym 
- /// <​summary>​ +  * @param P Zbiór ​uczący 
- /// Wybiera najbardziej liczną kategorię w podanym zbiorze uczącym + * @return Kategoria 
- /// </​summary>​ + *
- /// <param name="​indexList">​Lista indeksów mówiących które tablice z zbioru ​uczącego są w grze</param> + private Integer chooseCategory(ArrayList<IntegerP) 
- /// <param name="​d"></​param+ { 
- /// <returns>Kategoria</returns+ HashMap<Integer, IntegercategoryCounter = new HashMap<Integer, Integer>(); 
- private ​int ChooseCategory(List<​int> ​P)+ int category = 0; 
 + for (Integer var : P)
  {  {
- // Najbardziej liczną kategorię powinno się na razie zwracać. + category = (Integer)m_learingTable[var][m_categoryIndex];​ // Kategoria tych uczących które jeszcze zostały w indexList 
- Dictionary<​int,​ int> ​categoryCounter ​= new Dictionary<​int,​ int>()+ if (categoryCounter.containsKey(category))
- 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 + categoryCounter.put(categorycategoryCounter.get(category) + 1); 
- if (categoryCounter.ContainsKey(category)) +
-+
- categoryCounter[category]++;​ +
-+
- else +
-+
- categoryCounter.Add(category1); +
- }+
  }  }
 + else
 + {
 + categoryCounter.put(category,​ 1);
 + }
 + }
  
- int ​biggerAmount = 0; + Integer ​biggerAmount = 0; 
- foreach ​(int key in categoryCounter.Keys)+ for (Integer ​key categoryCounter.keySet()) 
 +
 + if (biggerAmount < categoryCounter.get(key))
  {  {
- if (biggerAmount < categoryCounter[key]) + category = key;
-+
- category = key; +
- }+
  }  }
- return (int)category;​ 
  }  }
 + return category;
 + }
  
- /// <​summary>​ + /** 
- /// Wybiera najlepszy test na podstawie najmniejszej entropii +  ​* ​Wybiera najlepszy test na podstawie najmniejszej entropii 
- /// </​summary>​ +  * @param P Zbiór ​uczący 
- /// <param name="P">​Lista indeksów pozostałego zbioru ​uczącego</​param>​ +  * @param S Zbiór ​testów 
- /// <param name="S">​Lista pozostałych ​testów</​param>​ +  * @return Wybrany test 
- /// <​returns>​Indeks wybranego testu</​returns>​ + *
- private ​int ChooseTest(List<int> P, List<int> S)+ private ​Integer chooseTest(ArrayList<Integer> P, ArrayList<Integer> S
 +
 + if (S.size() > 0)
  {  {
- if (S.Count > 0) + NominalTest test = null; 
-+ double minEntropy = Double.POSITIVE_INFINITY
- NominalTest test = null; + Integer ​bestIndex = 0;
- double minEntropy = Double.PositiveInfinity+
- int ​bestIndex = 0;+
  
- for (int i = 0; i < S.Count; i++)+ for (Integer ​i = 0; i < S.size(); i++
 +
 + test = new NominalTest(m_testNameList[S.get(i)],​ S.get(i));​ //​ Określamy który atrybut jest dla tego testu 
 + double testEntropy = countTestEntropy(P,​ test); 
 + if (testEntropy < minEntropy)
  {  {
- test new NominalTest(m_testNameList[S[i]],​ S[i]); // Określamy który atrybut jest dla tego testu + minEntropy ​= testEntropy;​ 
- double ​testEntropy ​= CountTestEntropy(P,​ test)+ bestIndex = i;
- if (testEntropy < minEntropy) +
-+
- minEntropy = testEntropy;​ +
- bestIndex = i; +
- }+
  }  }
-  
- return bestIndex; 
- } 
- else 
- { 
- throw new Exception("​Brak sprawdzania czy testy sie nie skończyły"​);​ 
  }  }
 +
 + return bestIndex;
  }  }
 + else
 + {
 + throw new RuntimeException("​Brak sprawdzania czy testy sie nie skończyły"​);​
 + }
 + }
  
- /// <​summary>​ + /** 
- /// Sprawdza czy w zbiorze uczącym jest tylko jedna kategoria +  ​* ​Sprawdza czy w zbiorze uczącym jest tylko jedna kategoria 
- /// </​summary>​ +  * @param P Zbiór ​uczący 
- /// <param name="P">​Lista indeksów pozostałego zbioru ​uczącego</​param>​ +  * @return ​Liść lub null w przypadku ​braku pożadanego węzł
- /// <​returns>​Liść lub null w przypadku ​błędu</returns> + *
- private ​ILeaf OnlyOneCategory(List<int> P)+ private ​TermostatLeaf onlyOneCategory(ArrayList<Integer> P
 +
 + if (P.size() > 0)
  {  {
- if (P.Count > 0) + boolean ​repeated = false; 
-+ Integer ​category = (Integer)m_learingTable[P.get(0)][m_categoryIndex];​
- bool ​repeated = false; +
- int ​category = (int)m_learingTable[P[0]][m_categoryIndex];​+
  
- for (int i = 1; i < P.Count; i++) + for (Integer ​i = 1; i < P.size(); i++) 
- +
- if (category != (int)m_learingTable[P[i]][m_categoryIndex]) //​ Jeśli któryś jest inny niż pierwszy + if (category != (Integer)m_learingTable[P.get(i)][m_categoryIndex]) //​ Jeśli któryś jest inny niż pierwszy 
- repeated = true+ repeated = true;
-+
- if (!repeated) //​ Jeśli się nie powtórzył +
-+
- return new TermostatLeaf(category,​ P); // Zwraca jedyną kategorię +
-+
- return null;+
  }  }
- else+ if (!repeated) //​ Jeśli się nie powtórzył
  {  {
- throw new Exception("Brak sprawdzania czy zbiór uczący nie jest pusty");+ return ​new TermostatLeaf(category, P); // Zwraca jedyną kategorię
  }  }
 + return null;
  }  }
- + else
- /// <​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 + throw new RuntimeException("Brak sprawdzania czy zbiór uczący nie jest pusty"); 
- 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])+ * Wylicza entropię danego przykładu trenującego dla danego testu 
- result.Add((int)m_learingTable[indexP][attrIndex]); // Pozbieranie możliwych rezultatów+ * @param P Zbiór uczący 
 + * @param test Test 
 + * @return Entropia 
 + */ 
 + private double countTestEntropy(ArrayList<​Integer> ​P, NominalTest test
 +
 + double allSum = 0; 
 + Integer attrIndex = test.AttributeIndex;​ 
 + ArrayList<​Integer>​ result = new ArrayList<​Integer>​(); 
 + ArrayList<​Integer>​ temp = new ArrayList<​Integer>​();
  
- foreach ​(int in result) //​ Dla kolejnych rezultatów testu+ for (Integer indexP : P) 
 + if (!result.contains((Integer)m_learingTable[indexP][attrIndex])) 
 + result.add((Integer)m_learingTable[indexP][attrIndex]);​ //​ Pozbieranie możliwych rezultatów 
 + 
 + for (Integer ​result) //​ Dla kolejnych rezultatów testu 
 +
 + temp.clear();​ 
 + for (Integer indexP : P)
  {  {
- dict = new Dictionary<​int,​int>​(); + if ((Integer)m_learingTable[indexP][attrIndex] == r) // Czy przykład należy do tego rezultatu
- 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);
-+
- temp.Add(indexP); +
- }+
  }  }
- allSum += CountEntropy(temp) * temp.Count / P.Count;;​ //​ Entropia Et(P) czyli suma po r |Ptr|/|P| * Etr(P) 
  }  }
- return ​allSum;+ allSum ​+= countEntropy(temp) * temp.size() / P.size();; // Entropia Et(P) czyli suma po r |Ptr|/|P| * Etr(P)
  }  }
 + return allSum;
 + }
  
- /// <​summary>​ + /** 
- /// Rekurencyjnie wywoływana funkcja dyskretyzacji-zstępującej +  ​* ​Rekurencyjnie wywoływana funkcja dyskretyzacji-zstępującej 
- /// </​summary>​ +  * @param P Zbiór ​uczący 
- /// <param name="P">Zbiór ​przykładów</​param>​ +  * @param attrIndex Indeks opisujący atrybut 
- /// <param name="attrIndex">Indeks opisujący atrybut</​param>​ +  * @return ​Lista punktów dzielących wartości 
- /// <​returns>​Lista punktów dzielących wartości</returns> + *
- private ​List<intDiscreteDown(List<int> P, int attrIndex) + private ​ArrayList<IntegerdiscreteDown(ArrayList<Integer> P, Integer ​attrIndex) 
- +
- if (OnlyOneValue(P,​attrIndex)) //​ Kryterium Stopu. Jeśli została tylko jedna wartość atrybutu w zbiorze uczącym + if (onlyOneValue(P,​attrIndex)) //​ Kryterium Stopu. Jeśli została tylko jedna wartość atrybutu w zbiorze uczącym 
- return new List<int>();+ return new ArrayList<Integer>();
  
- int ​treshold; + Integer ​treshold; 
- List<int> P0; + ArrayList<Integer> P0 = new ArrayList<​Integer>​(P)
- List<int> P1;+ ArrayList<Integer> P1 = new ArrayList<​Integer>​();
  
- treshold = ChooseTreshold(P, attrIndex);​ //​ Wybranie progu + treshold = chooseTreshold(P, attrIndex);​ //​ Wybranie progu 
- SplitList(P, attrIndex, treshold, ​out P0, out P1);+ splitList(P, attrIndex, treshold, P0, P1);
  
- double information = CountEntropy(P); + double information = countEntropy(P); 
- double entropy = (CountEntropy(P0) * P0.Count CountEntropy(P1) * P1.Count) / P.Count+ double entropy = (countEntropy(P0) * P0.size() ​countEntropy(P1) * P1.size()) / P.size()
- if (information - entropy <= m_entropyTreshhold) //​ Kryterium Stopu bazujące na wzrastaniu informacji + if (information - entropy <= m_entropyTreshhold) //​ Kryterium Stopu bazujące na wzrastaniu informacji 
- return new List<int>();+ return new ArrayList<Integer>();
  
- List<int> fi0 = DiscreteDown(P0, attrIndex);​ //​ Dzielenie zbioru < treshold+ ArrayList<Integer> fi0 = discreteDown(P0, attrIndex);​ //​ Dzielenie zbioru < treshold
  
- List<int> fi1 = DiscreteDown(P1, attrIndex);​ //​ Dzielenie zbioru >= treshold+ ArrayList<Integer> fi1 = discreteDown(P1, attrIndex);​ //​ Dzielenie zbioru >= treshold
  
- List<int> ret = new List<int>​(fi0);​ + ArrayList<Integer> ret = new ArrayList<Integer>​(fi0);​ 
- ret.Add(treshold);​ + ret.add(treshold);​ 
- ret.AddRange(fi1); + ret.addAll(fi1); 
- return ret; + return ret; 
- }+ }
  
- /// <​summary>​ + /** 
- /// Wylicza ​tą entropię ​z logarytmem +Wylicza entropię 
- /// </​summary>​ +  * @param top 
- /// <param name="top"><​/param> + * @param bottom 
- //<param name="​bottom"></​param+ * @return 
- /// <returns></returns+ */ 
- private double CountEntropy(int top, int bottom)+ private double countEntropy(Integer top, Integer bottom) 
 + { 
 + double temp (double)top / (double)bottom;​ 
 + return - temp * Math.log(temp);​ 
 +
 + 
 + /** 
 + * Oblicza entropię Etr(P) czyli sumuje entropie po wszystkiech kategoriach pojęcia docelowego  
 + * @param P Zbiór uczący 
 + * @return 
 + */ 
 + private double countEntropy(ArrayList<IntegerP) 
 + { 
 + Integer key; 
 + double sum = 0; 
 + HashMap<Integer, Integerdict = new HashMap<Integer,​Integer>​();​ /​Kategoria -ilość wystąpień Kategorii 
 +  
 + for (Integer indexP : P)
  {  {
- double temp = (double)top / (double)bottom+ key = (Integer)m_learingTable[indexP][m_categoryIndex]
- return - temp * Math.Log(temp2);+ dict.put(key,dict.containsKey(key) ? dict.get(key) + 1 : 1) ; //​ Zliczanie jak liczne są poszczególne kategorie
  }  }
 + sum = 0;
 + for (Integer count : dict.values())
 + {
 + sum += countEntropy(count,​ P.size());​ //​ Wyliczanie entropii Etr(P)
 + }
 +
 + return sum;
 + }
  
- /// <​summary>​ + /** 
- /// Oblicza entropię Etr(P) czyli sumuje entropie po wszystkiech kategoriach pojęcia docelowego +  * Wybiera próg dzielący wartości 
- /// </​summary>​ +  * @param P Zbiór uczący 
- /// <param name="P">Zbiór uczący</param> + * @param attrIndex Indeks opisujący atrybut 
- /// <returns></​returns+  * @return Próg 
- private double CountEntropy(List<​int> ​P)+ */ 
 + private Integer chooseTreshold(ArrayList<IntegerP, Integer attrIndex) 
 + { 
 + if (P.size() > 0)
  {  {
- int value+ double entropy
- double ​sum = 0; + double ​minEntropy = Double.POSITIVE_INFINITY;​ 
- Dictionary<int, intdict = new Dictionary<​int,​int>​(); // Kategoria -> ilość wystąpień Kategorii + Integer bestTreshold ​= 0; 
- List<​int>​ result = new List<int>();+ ArrayList<IntegerP0
 + ArrayList<IntegerP1;
  
- foreach ​(int indexP ​in P)+ ArrayList<​Integer>​ tresholdList = new ArrayList<​Integer>​();  
 + for (Integer ​indexP ​P)
  {  {
- value = (int)m_learingTable[indexP][m_categoryIndex]; + Integer tempa = (Integer)m_learingTable[indexP][attrIndex];  
- if (dict.ContainsKey(value)) + if (!tresholdList.contains(tempa)) 
- dict[value]++; // Zliczanie jak liczne są poszczególne kategorie + tresholdList.add(tempa); // Wybranie możliwości podziału
- else +
- dict[value] = 1;+
  }  }
- sum = 0+  
- foreach ​(int count in dict.Values)+ Collections.sort(tresholdList)
 + for (Integer treshold : tresholdList) //​ Dla kolejnych wartości rozdzielających (progowych)
  {  {
- sum +CountEntropy(count,​ P.Count);​ //​ Wyliczanie entropii Etr(P) + P0  ​new ArrayList<Integer>(P); 
-+ P1 = new ArrayList<Integer>(); 
- //sum *= P.Count;​ //​ Mnożenie przez wagę (ilość danego rezultatu) + splitList(P, attrIndex, treshold, P0, P1); 
- + entropy ​= (countEntropy(P0* P0.size() + countEntropy(P1* P1.size()P.size(); 
- return sum; + if (entropy < minEntropy)
-+
- +
- /// <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); + minEntropy = entropy; 
- entropy = (CountEntropy(P0) * P0.Count + CountEntropy(P1) * P1.Count) / P.Count; + bestTreshold = treshold;
- if (entropy < minEntropy) +
-+
- minEntropy = entropy; +
- bestTreshold = treshold; +
- }+
  }  }
- return bestTreshold;​ 
- } 
- else 
- { 
- throw new Exception("​P jest pusty, nie można wyznaczyć progu"​);​ 
  }  }
 + return bestTreshold;​
 + }
 + else
 + {
 + throw new RuntimeException("​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 +  ​* ​Dzieli zbiór przykładów na <= od progu oraz od progu 
- /// </​summary>​ +  * @param P Zbiór przykładów 
- /// <param name="P">Zbiór przykładów</​param>​ +  * @param attrIndex Indeks opisujący atrybut 
- /// <param name="attrIndex">Indeks opisujący atrybut</​param>​ +  * @param treshold Próg podziału 
- /// <param name="treshold">Próg podziału</​param>​ +  * @param P0 Wartości poniżej progu 
- /// <param name="P0">Wartości poniżej progu</​param>​ +  * @param P1 >​Wartości powyżej progu 
- /// <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)+ private void splitList(ArrayList<Integer> P, Integer ​attrIndex, ​Integer ​treshold, ​ArrayList<Integer> P0, ArrayList<Integer> P1) 
 +
 + for (int i = 0; i < P0.size(); i++) //​ Jedziemy do końca listy która nam się skraca, może inny warunek
  {  {
- P0 = new List<​int>​(P); + if ((Integer)m_learingTable[P0.get(i)][attrIndex] > treshold) // Jeśli większy niż treshold to:
- 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.get(i));​ //​ Dodajemy do większego od treshold 
-+ P0.remove(i--);​ //​ Zdejmujemy z mniejszego lub równego od treshold
- 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 +  ​* ​Sprawdza czy tylko jedna wartość występuje w danym zbiorze  
- /// </​summary>​ +  * @param P Zbiór przykładów 
- /// <param name="P">Zbiór przykładów</​param>​ +  * @param attrIndex Indeks opisujący atrybut 
- /// <param name="attrIndex">Indeks opisujący atrybut</​param>​ +  * @return 
- /// <​returns></​returns>​ + *
- private ​bool OnlyOneValue(List<int> P, int attrIndex)+ private ​Boolean onlyOneValue(ArrayList<Integer> P, Integer ​attrIndex
 +
 + Integer value = (Integer)m_learingTable[P.get(0)][attrIndex];​ 
 + for (Integer indexP : P)
  {  {
- int value = (int)m_learingTable[P[0]][attrIndex];​ + if ((Integer)m_learingTable[indexP][attrIndex] != value) 
- foreach (int indexP in P) + return false;
-+
- if ((int)m_learingTable[indexP][attrIndex] != value) +
- return false+
-+
- +
- return true;+
  }  }
  
- #endregion + return true; 
- } + }
 } }
- 
 </​code>​ </​code>​
pl/miw/miw08_rbs_ml/decisiontree.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0