--- pl:miw:miw08_rbs_ml:decisiontree [2008/06/10 14:19]
miw
+++ pl:miw:miw08_rbs_ml:decisiontree [2019/06/27 15:50] (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<Integer> PTemp = 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<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'
+				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<Integer> P)
-		/// <param name="d"></param>
+	{
-		/// <returns>Kategoria</returns>
+		HashMap<Integer, Integer> categoryCounter = 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(category, categoryCounter.get(category) + 1);
-				if (categoryCounter.ContainsKey(category))
-				{
-					categoryCounter[category]++;
-				}
-				else
-				{
-					categoryCounter.Add(category, 1);
-				}
 			}
+			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ła
-		/// <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 r 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 r : 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<int> DiscreteDown(List<int> P, int attrIndex)
+	private ArrayList<Integer> discreteDown(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<Integer> P)
+	{
+		Integer key;
+		double sum = 0;
+		HashMap<Integer, Integer> dict = 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(temp, 2);
+				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<Integer> P, Integer attrIndex)
+	{
+		if (P.size() > 0)
 		{
-			int value;
+			double entropy;
-			double sum = 0;
+			double minEntropy = Double.POSITIVE_INFINITY;
-			Dictionary<int, int> dict = new Dictionary<int,int>();			// Kategoria -> ilość wystąpień Kategorii
+			Integer bestTreshold = 0;
-			List<int> result = new List<int>();
+			ArrayList<Integer> P0;
+			ArrayList<Integer> P1;
-			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>

pl/miw/miw08_rbs_ml/decisiontree.1213100372.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice