Wednesday, March 31, 2010

Quick & cheap way to rename colum in table - sp_rename

Quick & cheap way to rename colum in table:


EXEC sp_rename
    @objname = 'MY_TABLE.COULMN_NAME',
    @newname = 'COLUMN_NAME',
    @objtype = 'COLUMN'


Get fun!
0 comments
Labels: ,
Reactions:

Friday, March 26, 2010

ID3-impl

Below is my implementation of the ID3 algorithm based on my story about it.

It builds decision tree for next training data:

 AGE | COMPETITION | TYPE | PROFIT
 =========================================
 old | yes       | swr | down (False in my impl)
 --------+-------------+---------+--------
 old | no       | swr  | down
 --------+-------------+---------+--------
 old | no       | hwr | down
 --------+-------------+---------+--------
 mid | yes       | swr | down
 --------+-------------+---------+--------
 mid | yes       | hwr | down
 --------+-------------+---------+--------
 mid | no       | hwr | up (True in my impl)
 --------+-------------+---------+--------
 mid | no       | swr | up
 --------+-------------+---------+--------
 new | yes       | swr | up
 --------+-------------+---------+--------
 new | no       | hwr | up
 --------+-------------+---------+--------
 new | no       | swr | up
 --------+-------------+---------+--------

And built tree looks like this:

           Age
         / |    \
        /  |     \
    new/   |mid   \old
      /    |       \
    True Competition False
         /      \
        /        \
     no/          \yes
      /            \
    True             False



The Implementation of algorithm ID3


using System;
using System.Collections.Generic;
using System.Linq;

namespace ID3
{
    public static class Program
    {

        static void Main(string[] args)
        {
            var R = new Dictionary<string, List<string>>();
            R.Add("Age", new List<string>() { "old", "mid", "new" });
            R.Add("Competition", new List<string>() { "yes", "no" });
            R.Add("Type", new List<string>() { "hwr", "swr" });


            var C = "Profit";
            var TrainingSet = GetTrainingData();
            var algorithm = new Id3Algorithm();
            Tree desicionTree = algorithm.ID3(R, C, "root", TrainingSet);
        }

        private static List<TrainingRecord> GetTrainingData()
        {
            var trainingRecords = new List<TrainingRecord>();
            Dictionary<string, string> attributes;

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "old");
            attributes.Add("Competition", "yes");
            attributes.Add("Type", "swr");
            trainingRecords.Add(new TrainingRecord(attributes, false));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "old");
            attributes.Add("Competition", "no");
            attributes.Add("Type", "swr");
            trainingRecords.Add(new TrainingRecord(attributes, false));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "old");
            attributes.Add("Competition", "no");
            attributes.Add("Type", "hwr");
            trainingRecords.Add(new TrainingRecord(attributes, false));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "mid");
            attributes.Add("Competition", "yes");
            attributes.Add("Type", "swr");
            trainingRecords.Add(new TrainingRecord(attributes, false));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "mid");
            attributes.Add("Competition", "yes");
            attributes.Add("Type", "hwr");
            trainingRecords.Add(new TrainingRecord(attributes, false));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "mid");
            attributes.Add("Competition", "no");
            attributes.Add("Type", "hwr");
            trainingRecords.Add(new TrainingRecord(attributes, true));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "mid");
            attributes.Add("Competition", "no");
            attributes.Add("Type", "swr");
            trainingRecords.Add(new TrainingRecord(attributes, true));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "new");
            attributes.Add("Competition", "yes");
            attributes.Add("Type", "swr");
            trainingRecords.Add(new TrainingRecord(attributes, true));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "new");
            attributes.Add("Competition", "no");
            attributes.Add("Type", "hwr");
            trainingRecords.Add(new TrainingRecord(attributes, true));

            attributes = new Dictionary<string, string>();
            attributes.Add("Age", "new");
            attributes.Add("Competition", "no");
            attributes.Add("Type", "swr");
            trainingRecords.Add(new TrainingRecord(attributes, true));


            return trainingRecords;
        }
    }

    internal class Tree
    {
        public string Name { get; private set; }
        public string ArcName { get; private set; }
        public bool IsLeaf{ get; private set; }

        public Dictionary<string, Tree> Trees { get; private set; }

        public Tree(string name, string arcName, Dictionary<string, Tree> trees)
        {
            Name = name;
            ArcName = arcName;
            Trees = trees;
            if (Trees == null) IsLeaf = true;
            else if (Trees.Count <= 0) IsLeaf = true;
        }
    }

    internal class TrainingRecord
    {
        public Dictionary<string, string> Attributes { get; private set; }
        public bool Success { get; private set; }

        public TrainingRecord(Dictionary<string, string> attributes, bool success)
        {
            Attributes = attributes;
            Success = success;
        }
    }


    /*    function ID3 (R: множина некатегоризаційних властивостей,
       C: категоризаційна властивість,
       S: множина для навчання) returns дерево прийняття рішень;
       begin
     Якщо S пуста, повернути один вузол із значенням невдача;
     Якщо S складаєтсья із рядків, для яких значення категоризаційної
        властивості одне й те ж,
        повернути єдиний вузол із тим значенням;
     Якщо R пуста, тоді повернути єдиний вузол із значенням, яке є
        найбільш частішим серед значень катеригоційної властивості,
        що було знайдено серед рядків S;
     Нехай D є властивістю із найбільшим приростом Gain(D,S)
        серед властивостей в множині R;
     Нехай {dj| j=1,2, .., m} - значення властивості D;
     Нехай {Sj| j=1,2, .., m} - підмножини S, що включають
        відповідні рядки із значенням dj для властивості D;
     Повернути дерево із коренем поміченим D і дуги позначені
        d1, d2, .., dm що продовжуються наступними деревами

          ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
       end ID3;
 */

    internal class Id3Algorithm
    {
        public Tree ID3(Dictionary<string, List<string>> R, string C, string arcName, List<TrainingRecord> S)
        {
            //1
            if(S.Count <= 0) return new Tree(false.ToString(), arcName, null);
            //2
            var prevValue = S[0].Success;
            foreach (var trainingRecord in S)
            {
                if(prevValue != trainingRecord.Success)
                {
                    prevValue = trainingRecord.Success;
                    break;
                }
            }
            if(prevValue == S[0].Success)
            {
                return new Tree(prevValue.ToString(), arcName, null);
            }
            //3
            if(R.Count <= 0)
            {
                var sCount = S.Where(x => x.Success).Count();
                var fCount = S.Where(x => !x.Success).Count();
                var resValue = (sCount < fCount) ? true : false;

                new Tree(resValue.ToString(), arcName, null);
            }
            //4
            double maxGain = double.MinValue;
            string maxAtrb = string.Empty;
            foreach (var attribute in R)
            {
                double currGain = Gain(attribute.Key, attribute.Value, S);
                if(currGain > maxGain)
                {
                    maxGain = currGain;
                    maxAtrb = attribute.Key;
                }
            }

            var partitioning = new Dictionary<string, List<TrainingRecord>>();

            foreach (var posValue in R[maxAtrb])
            {
                var Si = S.Where(x => x.Attributes[maxAtrb] == posValue).ToList();
                partitioning.Add(posValue, Si);
            }
            R.Remove(maxAtrb);

            var childTrees = new Dictionary<string, Tree>();
            foreach (var Si in partitioning)
            {
                childTrees.Add(Si.Key, ID3(R, C, Si.Key, Si.Value));
            }

            return new Tree(maxAtrb, arcName, childTrees);
        }

        private double Gain(string s, List<string> posValues, List<TrainingRecord> trainingRecords)
        {
            return Info(trainingRecords) - Info(s, posValues, trainingRecords);
        }

        private double Info(string attribute, List<string> posValues, List<TrainingRecord> list)
        {
            double nGeneral = list.Count;
            double sum = 0;
            foreach (var value in posValues)
            {
                var sCount = list.Where(x => (x.Attributes[attribute] == value) && x.Success).Count();
                var fCount = list.Where(x => (x.Attributes[attribute] == value) && (!x.Success)).Count();
                var n = (double)(sCount + fCount);
                var iValue = I(new List<double>() { sCount / n, fCount / n });
                sum += (n / nGeneral) * iValue;
            }
            return sum;
        }

        private double Info(List<TrainingRecord> trainingRecords)
        {
            int n = trainingRecords.Count;
            var sCount = trainingRecords.Where(x => x.Success == true).Count();
            var fCount = trainingRecords.Where(x => x.Success == false).Count();
            var p1 = sCount / (double)n;
            var p2 = fCount / (double)n;

            double info = I(new List<double>() { p1, p2 });
            return info;
        }

        private double I(List<double> P)
        {
            double sum = 0;
            foreach (var p in P)
            {
                if (p != 0)
                {
                    sum += p * Math.Log(p, 2);
                }
            }
            return -sum;
        }
    }
}

and the result in Competition node from debug mode:


That is bold path in tree below:


           Age 
         / |    \
        /  |     \
    new/   |mid   \old
      /    |       \
    True Competition False
         /      \
        /        \
     no/          \yes
      /            \
    True             False

I'm going to implement all  this stuff online tomorrow for students who will listen to me.
0 comments
Labels: ,
Reactions:

Thursday, March 25, 2010

Дерева прийняття рішень, алгоритми ID3 та С4.5


Вступ



Алгоритми ID3 і C4.5  придумані Джоном Квінланом (John R. Quinlan) для індукування Класифікаційних Моделей(Classification Models), які ще називають Деревами прийняття рішень(Decision Trees), із даних.

Перш за все ми маємо множину рядків даних. Кожен вектор, або рядок, має таку ж структуру, складається із набору пар властивість/значення. Одна із цих властивостей представляє категорію нашого вектору. Нашим завданням є побудувати дерево прийняття рішень, яке базуючись на відповідях про властивості, що не відповідають за категорію, зробити висновок про значення категорізаційної властивості. Зазвичай категорізаційна властивість приймає тільки два значення {Так, Ні}, або {true, false}, або {success, failure}. В будь-якому випадку одне із значень буде означати невдачу.
Для прикладу, ми можемо мати результати замірів про деяку подію, зроблених експертами. Для кожної події ми знаємо рішення, яке було прийняте експертами, напр. ствердне рішення, відхилити або ж інше. Іншими словами ми маємо вектор із некатегоризаційними властивостями та категоризаційну властивісь - прийняте рішення.
Розглянемо більш детальний приклад. Ми маємо справу із записами що засвідчують погодні умови для гри в гольф. Категоризаційна властивість є рішення про те чи слід грати в гру чи ні. Некатегоризаційні властивості такі:


             ВЛАСТИВІСТЬ | МОЖЛИВІ ЗНАЧЕННЯ
 ============+=======================
 небо        | сонячно, хмарно, дощ
 ------------+-----------------------
 температура | значення
 ------------+-----------------------
 вологість   | значення
 ------------+-----------------------
 вітряно     | так, ні
 ============+=======================

а тут набір даних для побудови дерева:


 НЕБО   | ТЕМПЕРАТУРА | ВОЛОГІСТЬ | ВІТРЯНО | ГРАТИ?
 =====================================================
 сонячно|      30     |    85     |   ні   | Не грати
 сонячно|      27     |    90     |   так  | Не грати
 хмарно |      28     |    78     |   ні   | Грати
 дощ    |      21     |    96     |   ні   | Грати
 дощ    |      20     |    80     |   ні   | Грати
 дощ    |      18     |    70     |   так  | Не грати
 хмарно |      18     |    65     |   так  | Грати
 сонячно|      22     |    95     |   ні   | Не грати
 сонячно|      21     |    70     |   ні   | Грати
 дощ    |      24     |    80     |   ні   | Грати
 сонячно|      24     |    70     |   так  | Грати
 хмарно |      22     |    90     |   так  | Грати
 хмарно |      27     |    75     |   ні   | Грати
 дощ    |      22     |    80     |   так  | Не грати
Зауважмо, що дві властивості мають недетерміновані значення - температура і вологість. ID3 алгоритм не може напряму мати справу із такими випадками, але є модифікації, які дозволють йому працювати із такими значеннями. Дерева прийняття рішень важливі не тільки тому, що вони дозволяють узагальнити те, що ми знаємо, або відомий набір даних для навчання, але тому, що ми можемо сподіватися на те, що алгоритм правильно скласифікує нові, невідомі випадки. Таким чином коли ми будуємо класифікаційну модель (дерево), ми повиння мати дані для навчання і дані для перевірки правильності побудованої моделі.
Спрощений приклад складу магазину, який включає тільки дискретні значення властивостей речей для продажу, та виручка як категоризаційну властивість, яка може мати два значення {висока, низька}. Некатигоризаційні властивості:



 ВЛАСТИВІСТЬ | МОЖЛИВІ ЗНАЧЕННЯ
 ============+=======================
 вік         | старий, середній, новий
 ------------+-----------------------
 конкуренція | ні, так
 ------------+-----------------------
 тип         | ПЗ, "залізо"
 ------------+-----------------------

   і дані для навчання такі:

 ВІК     | КОНКУРЕНЦІЯ | ТИП     | ВИРУЧКА
 =========================================
 старий  | так         | ПЗ      | низька
 --------+-------------+---------+--------
 старий  | ні          | ПЗ      | низька
 --------+-------------+---------+--------
 старий  | ні          | залізо  | низька
 --------+-------------+---------+--------
 сер.    | так         | ПЗ      | низька
 --------+-------------+---------+--------
 сер.    | так         | залізо  | низька
 --------+-------------+---------+--------
 сер.    | ні          | залізо  | висока
 --------+-------------+---------+--------
 сер.    | ні          | ПЗ      | висока
 --------+-------------+---------+--------
 новий   | так         | ПЗ      | висока
 --------+-------------+---------+--------
 новий   | ні          | залізо  | висока
 --------+-------------+---------+--------
 новий   | ні          | ПЗ      | висока
 --------+-------------+---------+--------
Основні концепції алгоритму ID3 такі:

  • В дереві рішень кожен вузол відповідає за некатегоризаційну властивість, а кожна дуга, яка виходить із кореня за можливі значення того атрибуту. Листки дерева визначають очікуване значення категоризаційної властивості для записів, що відповідають шляху пройденому від кореня до цього листочка. (Ось чому ми називаємо цю модель деревом прийняття рішень.)
  • В дереві рішень кожен вузол повинен відповідати за некатегоризаційну властивість, яка є найбільш інформативна поміж інших властивостей, що ще не є в шляху від кореня до заданого вузла. (Це дає поняття "Хорошого" дерева прийняття рішень.)
  • Ентропія використовується для визначчення на скільки вузол є інформативним. (Це дає визначення до того, що ми розуміємо під "Хорошим" деревом.)
С4.5 є доповненням до алгоритму ID3, що враховує допустимі значення, недетерміновані значення, відсікання дерева, виведення правил та інше.

 

Означення


Якщо є n можливих повідомлень, тоді вірогідність p кожного є рівна 1/n а інформативність передана цим повідомленням є такою -log(p) = log(n).  Для прикладу, якщо є 16 повідомлень, тоді log(16) = 4 і нам потрібно 4 біти, щоб ідентифікувати кожне повідомлення.
В загальному, якщо ми маємо розподіл імовірностей P = (p1, p2, .., pn) тоді інформативність передана цим розподілом, або Ентропія Р, визначається так:: 
 I(P) = -(p1*log(p1) + p2*log(p2) + .. + pn*log(pn))
Для прикладу, якщо P є (0.5, 0.5) тоді I(P) рівне 1, якщо P є (0.67, 0.33) тоді I(P) рівне 0.92, а якщо P є (1, 0) тоді I(P) дорівнює 0. [Зауважте, що чим більш подібні ймовірності в розподілі, тим більша є інформативність]Якщо множина T записів є розбита на виокремлі класи C1, C2, .., Ck базуючись на значенні категоризаційної властивості, тоді інформація, необхідна для ідентифікації класу елемента із множини Т є Info(T) = I(P), де P є ймовірнісний розподіл розбиття (C1, C2, .., Ck): 
 P = (|C1|/|T|, |C2|/|T|, ..., |Ck|/|T|)
В нашому прикладі гри в гольф, ми отримуємо Info(T) = I(9/14, 5/14) = 0.94,
а в нашому прикладі із складом магазину ми отримуємо Info(T) = I(5/10,5/10) = 1.0.
Якщо перше розбиття T, базоване на значенні некатигоризованого атрибуту X буде таке T1, T2, .., Tn тоді інформація необхідна для визначення класу елементу із Т є середнім із інформацій необхідних для ідертифікації класу елемента Ti, іншими словами середнє із Info(Ti): 
                                       |Ti|
 Info(X,T) = СУМА по i від 1 до n      ---- * Info(Ti)
                                        |T|
У випадку гри в гольф, для властивості Небо, ми маємо: 
 Info(Outlook,T) = 5/14*I(2/5,3/5) + 4/14*I(4/4,0) + 5/14*I(3/5,2/5)
   = 0.694
Дамо означення приросту інформації Gain(X,T) як

 Gain(X,T) = Info(T) - Info(X,T)
Це представляє різницю між інформацією необхідною для визначення елемента із Т і інформації необхідної для визначення елемента із Т, після того, якщо значення властивості Х було визначено, іншими словами приріст інформації завдяки відомості властивості Х.
В нашому прикладі із грою в гольф, для властивосіті Небо, приріст буде:

 Gain(Outlook,T) = Info(T) - Info(Outlook,T) = 0.94 - 0.694 = 0.246.
Якщо взяти властивість Вітряно, ми отримаємо такі значення Info(Windy,T) = 0.892 та Gain(Windy,T) = 0.048. Таким чином Небо надає більше інформаційного приросту аніж Вітряно.
Ми можемо використовувати знання приросту для відсортовування властивостей і для побудови дерева прийняття рішень, де в кожному вузлі знаходиться властивість із найбільшим інформаційним приростом в порівнянні до інших властивостей, які не включені в шлях від кореня до поточного вузла.
Це впорядкування вирішує два завдання:

  • Для створення малих дерев, що дозволяє після декількох питань визначити рішення.
  • Задовольнити бажану оптимальність процесу для рядків, що розглядаються.

Алгоритм ID3


Алгоритм ID3 використовується для побудови дерев прийняття рішень, маючи множину некатегоризаційних властивостей C1, C2, .., Cn, категоризаційну властивість C, і множину записів для навчання T.


   function ID3 (R: множина некатегоризаційних властивостей,
   C: категоризаційна властивість,
   S: множина для навчання) returns дерево прийняття рішень;
   begin
 Якщо S пуста, повернути один вузол із значенням невдача;
 Якщо S складаєтсья із рядків, для яких значення категоризаційної
    властивості одне й те ж, 
    повернути єдиний вузол із тим значенням;
 Якщо R пуста, тоді повернути єдиний вузол із значенням, яке є
    найбільш частішим серед значень катеригоційної властивості,
    що було знайдено серед рядків S;
 Нехай D є властивістю із найбільшим приростом Gain(D,S) 
    серед властивостей в множині R;
 Нехай {dj| j=1,2, .., m} - значення властивості D;
 Нехай {Sj| j=1,2, .., m} - підмножини S, що включають 
    відповідні рядки із значенням dj для властивості D;
 Повернути дерево із коренем поміченим D і дуги позначені 
    d1, d2, .., dm що продовжуються наступними деревами 

      ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
   end ID3;

В прикладі із грою в гольф ми отримуємо наступне дерево: 
                      Небо
                   / |      \
                  /  |       \
          хмарно /   |сонячно \дощ
                /    |         \
           Грати  Вологість   Вітряно
                   /   |          |  \
                  /    |          |   \
            <=75 /  >75|       так|    \ні
                /      |          |     \
             Грати  Не грати   Не грати  Грати


   В прикладі із магазинним складом дерево буде:


           Вік
         / |    \
        /  |     \
    нов/   |сер   \старе
      /    |       \
    Вис  Competition Низька
         /      \
        /        \
     ні/          \так
      /            \
    Вис            Низька


Використання зважених приростів (Gain Ratios)


Поняття приросту (Gain) введене раніше має тенденцію одобряти властивості, що мають велику кількість значень. Для прикладу, якщо в нас є властивість D, що має різні значення для кожного рядка, тоді інформативність буде Info(D,T) рівною 0, таким чином приріст Gain(D,T) є максимальним. Щоб компенсувати це Квінлан запропонував використання наступного зглажування замість звичного приросту: 
                   Gain(D,T)
 GainRatio(D,T) = ----------
                  SplitInfo(D,T)

   де SplitInfo(D,T) є інформація у відповідності до розбиття T на основі
   значень категоризаційної властивості D. Таким чином SplitInfo(D,T) є

   I(|T1|/|T|, |T2|/|T|, .., |Tm|/|T|)

   де {T1, T2, .. Tm} є розбиття множини T продуковане значенням D.

   У випадку нашої гри в гольф SplitInfo(Outlook,T) рівне 

 -5/14*log(5/14) - 4/14*log(4/14) - 5/14*log(5/14) = 1.577

   таким чином GainRatio для Небо буде 0.246/1.577 = 0.156. І 
   SplitInfo(Windy,T) буде 

 -6/14*log(6/14) - 8/14*log(8/14) = 6/14*0.1.222 + 8/14*0.807 = 0.985

   отже, GainRatio для Вітряно є 0.048/0.985 = 0.049


Доповнення C4.5


С4.5 додає цілий ряд доповнень до оригінального алгоритму ID3.
Під час побудови дерева рішень ми можемо мати справу із навчальними даними, що мають рядки із невідомими значеннями властивостей під час обрахунку приросту, беручи до уваги лише рядки, де ця властивість визначена.
Під час використання дерева, ми можемо класифікувати рядки, що мають невідомі значення властивостей, вгадуючи ймовірності появи різних результатів. Для нашого прикладу із грою у гольф, якщо ми маємо новий рядок, для якого Небо є сонячне і Вологість є невідомою, ми продовжуємо наступним чином:

   Ми рухаємося від кореня Небо до вузла Вологість проходячи
   дугу іменовану 'сонячно'. В цій позиції, оскільки ми не знаємо
   значення Вологості ми спостерігаємо, що якщо вологість є менша за 75
   є тільки два рядки коли слід грати, і якщо вологість є більша
   ніж 75 тоді є три рядки коли не слід грати. Таким чином
   ми можемо дати відповідь для рядка із ймовірностями
   (0.4, 0.6) грати або ж не грати.
Ми можемо мати справу із недетермінованими властивостями наступним чином. Припустимо що атрибут Ci є недетермінованим (число як для вологості). Ми визначаємо значення для цього атрибуту в множині для навчання. Скажімо ми маємо посортовані значення, A1, A2, .., Am. Тоді для кожного значення Aj, j=1,2,..m, ми розбиваємо рядки на такі, які менці за Aj, і такі які більші за Aj. Для кожного із розбиттів ви рахуємо приріст, або зважений приріст, і вибираємо таке розбиття, яке максимізує приріст.
В нашому прикладі із грою в гольф для вологості, якщо T є множиною навчання, ми визначаємо інформацію для кожного розбиття і знаходимо найкраще в точці 75. Таким чином діапазон для цього атрибуду визначений як {<=75, >75}. Зауважте що цей метод вимагає багато калькуляцій, тому є ресурсоємним.

Відсікання дерев прийняття рішень та виведення правил


Дерева прийняття рішень будуються на основі навчальних даних, таким чином вони практично завжди виводять правильні рішення для рядків із навчальної множини. Насправді для знаходження результату нерідко шлях по дереву може виявитися занадто довгим.
Відсікання дерева прийняття рішення полягає в заміні цілого піддерева листком. Заміна відбувається коли дерево виявляє, що очікувана помилка у піддереві є більша ніж у окремому листку. Для прикладу, якщо ми маємо таке просте дерево 

          Колір
         /     \
червоний/       \синій
       /         \
    Успіх      Невдача
було визначено за допомогою одного успішного червоного рядка і двох невдалих синіх рядків, нагадаємо що ці рядки були із навчальних даних, а потім у тестових даних ми виявили три червоні невдачі і один синій успіх, ми можемо застосувати зміну цілого піддерева одним листком невдачі. Таким чином після заміни ми будемо мати лише тві помилки замість п"яти.
Вінстон (Winston) показав як використати тест Фішера щоб визначити чи категорія-властивість дійсно залежить від заданої некатегоризаційної властивості. Якщо це так, то така властивість просто не має знаходитися в жодному шляху дерева.
Квінлан (Quinlan) і Брейман (Breiman) запропонували більш умудрену відсікаючу евристику.
Можна виробити набір правил на основі дерева прийняття рішення: записуємо правило для кожного шляху від кореня до листка. В такому правилі ліва сторона легко будується із міткок вузлів і з"єднуюючих дуг.
Результуючий набір правил може бути спрощений:
Нехай LHS є ліва сторона правила. Нехай LHS' є отриманий із LHS шляхом вилучення деяких умов. Ми можемо впевнено замінити LHS за допомогою LHS' в цьому правилі, для кожного вектора із множини навчання, що задовольняє LHS також задовольняє LHS'.
Правило може бути видалено, якщо "більш ніякі правила є незастосовні".




This post has been translated from page: http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html, 02/25/2010.

Цей пост був перекладений із сторінки: http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html, 25.03.2010.
2 comments
Labels: ,
Reactions:

Happy Birthday to you, Natali!

Today is the birthday of my girlfriend.

HAPPY BIRTHDAY TO YOU, NATALI!

Her friends made her a present - nice T-Shirt where she is with me. Take a look:


Not sure if it is possible to see me there on picture, but believe I'm there.

I wasn't so much original, so I gave her flowers:


Currently she is most often reader of my blog than others, not sure if blog itself make any sense to her, but truth is truth.
2 comments
Labels:
Reactions:

Wednesday, March 24, 2010

My implementation of Self-Organizing Map

Lets quickly remind how does Self-Organizing Map works and which are building blocks of it.

In my implementation I have processor named SomLearningProcessor which does all main algorithm steps. After you created instance of that class you are able to call void Learn() method, which goes through all iterations finds best matching neuron with method int FindBestMatchingNeuron(double[] dataVector) and then it accommodates network with using dataVector and found BMN - this is done with method void AccommodateNetworkWeights(int bestNeuronNum, double[] dataVector, int iteration). I will return back to this processor with more details, I just wanted to give quick vision what is it.

So lets move to building blocks of our learning algorithm:

Network

First of all it has Network, which I inject into our SomLearningProcessor through the INetwork interface:

    public interface INetwork
    {
        IList<INeuron> Neurons { get; set; }

        ITopology Topology { get; set; }
    }

As you see it has list of Neurons which should fill the leaning grid, which is provided through the Topology interface. The default implementation of the network interface supplies possibility to randomize neurons with specifying minWeights and maxWeights boundaries for randomizing.

    public class NetworkBase : INetwork
    {
        public NetworkBase(bool randomize, IList<double> maxWeights, IActivationFunction activationFunction, ITopology topology)
        {...

Also we are injecting IActivationFunction for our neurons, so they will calculate reaction basing on this interface. Interface provides method double GetResult(double inputValue);
There are following concrete implementations of the interface IActivationFunction:
  • HardLimitActivationFunction
  • LinearActivationFunction
  • SymmetricHardLimitActivationFunction
  • TransparentActivationFunction
For Self-Organizing Maps I'm using TransparentActivationFunction, which just returns summarized value.

Topology

Another interesting thing that we are using during learning process is Topology. Interface looks like this:


    public interface ITopology
    {
        int NeuronsCount { get; }

        int RowCount { get; }

        int ColCount { get; }

        double WholeTopologyRadius { get; }

        int GetNeuronNumber(Location location);

        Location GetNeuronLocation(int neuronNumber);

        IList<int> GetDirectlyConnectedNeurons(int neuronNumber);

        Dictionary<int, double> GetNeuronsInRadius(int neuronNumber, double radius);
    }

As you see Topology consists with Rows and Columns as usual matrix, but the main point of interest is the method: Dictionary<int, double> GetNeuronsInRadius(int neuronNumber, double radius); What does it do?
For the found best matching neuron neuronNumber - it should find all neurons which are located in boundaries of provided radius. Please also note that I'm returning pairs <NeuronNumber, DistanceFromItToBMN> in result dictionary. This allow increase performance a bit, because no need to double calculate distances.
Currently I have two finished implementations of ITopology they are SimpleMatrixTopology and BoundMatrixTopology.

Difference between them is that BoundMatrixTopology is closed cover like on the picture below, for matrix 6x5 and winning neuron number 22 with radius 2.1 it returns following neighbor neurons.


As you see it also returned 4 as connected neuron.

Same situation for SimpleMatrixToplogy returns next:


So far we have visual explanation how it searches for the neighbor neurons. On the picture below we could see which distances are returned by the GetNeuronsInRadius method.


For my research I'm using SimpleMatrixTopology because it is much faster than BoundMatrixTopology.

A bit about Learning Process

Learning process is build upon changing weights of the neurons in order to be more close to input data vector. But also with increasing iteration number we should shrink the radius where we search for neighbor neurons and we should decrease learning rate. Also those neurons which are close to winner should be modified more than those which are far from it. This purposes are supplied by three interfaces. They are IRadiusProvider, INeighbourhoodFunction and  ILearningFactorFunction.


RadiusProvider

Answers for the question which radius we should take on the n-th iteration. Currently I have one implementation of the interface, which looks like below:


    public class DefaultRadiusProvider : IRadiusProvider
    {
        public int MaxIterations { get; private set; }
        public double TopologyRadius { get; private set; }
        public double TimeConstant { get; private set; }

        public DefaultRadiusProvider(int maxIterations, double startRadius)
        {
            MaxIterations = maxIterations;
            TopologyRadius = startRadius;

            TimeConstant = maxIterations / Math.Log(startRadius);
        }

        public double GetRadius(int iteration)
        {
            return TopologyRadius*Math.Exp(-iteration/TimeConstant);
        }
    }

As you see when we create instance of it we define TimeConstant and that stands for:


when we calculate radius we are using next formula:

In those two formulas δ0 is half of the initial Grid radius and I setup it in constructor of Topology like: Math.Max(ColCount, RowCount) / 2.0, but of course we could choose wider initial value.

NeighbourhoodFunction

The most commonly used is Gauss Neighbourhood function, because it is quite smooth.


    public class GaussNeighbourhoodFunction : INeighbourhoodFunction
    {
        public double GetDistanceFalloff(double distance, double radius)
        {
            double denominator = 2 * radius * radius;
            return Math.Exp(- distance / denominator);
        }
    }

We provide two parameters one of them is distance between neuron i and neuron j, another parameter is current radius, calculated by RadiusProvider. So the formula of it is:

LearningFactorFunction

And as we said before, learning rate should decrease with time. For this purpose I have few implementations of the interface ILearningFactorFunction. I'm using ExponentionalFactorFunction  which has method:

        public override double GetLearningRate(double iteration)
        {
            return StartLearningRate * Math.Exp(- iteration / MaxIterationsCount);
        }


The formula looks like:

where τ2 is equal to maximum iterations count and η0 is starting learning rate. I set it to the 0.07.

Other Interfaces 

During learning process I'm using few other interfaces. They are:

ShuffleProvider - provides method using which I shuffle input space vectors on each epoch.

LearningDataProvider - gives us possibility to get i-th input vector and answers for questions how many there are vectors and what is the dimension of input space. Using this interface I can mask providing of completely random input vectors as I did in this application. Or I can provide DataPersister into it, so it will be able read data from file or whatever.

MetricFunction - is just distance measurement for our grid. I have CityBlocks and Euclidean implementations.


SomLearningProcessor

With mix of all described above we can build our Learning Processor. Below is full code snippet of SomLearningProcessor:

    public class SomLearningProcessor
    {
        public INetwork Network { get; private set; }
        public ITopology Topology { get; private set; }

        protected IShuffleProvider ShuffleProvider { get; set; }
        protected ILearningDataProvider LearningDataProvider { get; set; }
        protected IRadiusProvider RadiusProvider { get; private set; }
        protected INeighbourhoodFunction NeighbourhoodFunction { get; set; }
        protected IMetricFunction MetricFunction { get; set; }
        protected ILearningFactorFunction LearningFactorFunction { get; set; }

        protected int MaxIterationsCount { get; set; }

        public SomLearningProcessor(
            ILearningDataProvider learningDataProvider,
            INetwork network,
            IMetricFunction metricFunction,
            ILearningFactorFunction learningFactorFunction,
            INeighbourhoodFunction neighbourhoodFunction,
            int maxIterationsCount,
            IShuffleProvider shuffleProvider)
        {
            LearningDataProvider = learningDataProvider;
            Network = network;
            Topology = network.Topology;
            MetricFunction = metricFunction;
            LearningFactorFunction = learningFactorFunction;
            NeighbourhoodFunction = neighbourhoodFunction;
            MaxIterationsCount = maxIterationsCount;
            ShuffleProvider = shuffleProvider;

            RadiusProvider = new DefaultRadiusProvider(maxIterationsCount, Topology.WholeTopologyRadius);
        }

        public virtual void Learn()
        {
            int vectorsCount = LearningDataProvider.LearningVectorsCount;
            IList<int> suffleList = new ShuffleList(vectorsCount);

            for (int iteration = 0; iteration < MaxIterationsCount; iteration++)
            {
                suffleList = ShuffleProvider.Suffle(suffleList);

                for (int dataInd = 0; dataInd < vectorsCount; dataInd++)
                {
                    double[] dataVector = LearningDataProvider.GetLearingDataVector(suffleList[dataInd]);

                    int bestNeuronNum = FindBestMatchingNeuron(dataVector);

                    AccommodateNetworkWeights(bestNeuronNum, dataVector, iteration);
                }
            }
        }

        protected virtual int FindBestMatchingNeuron(double[] dataVector)
        {
            int result = -1;
            Double minDistance = Double.MaxValue;
            for (int i = 0; i < Network.Neurons.Count; i++)
            {
                double distance = MetricFunction.GetDistance(Network.Neurons[i].Weights, dataVector);
                if (distance < minDistance)
                {
                    minDistance = distance;
                    result = i;
                }
            }
            return result;
        }

        protected virtual void AccommodateNetworkWeights(int bestNeuronNum, double[] dataVector, int iteration)
        {
            var radius = RadiusProvider.GetRadius(iteration);
            var effectedNeurons = Topology.GetNeuronsInRadius(bestNeuronNum, radius);

            foreach (var effectedNeuron in effectedNeurons.Keys)
            {
                var distance = effectedNeurons[effectedNeuron];

                AccommodateNeuronWeights(effectedNeuron, dataVector, iteration, distance, radius);
            }
        }

        protected virtual void AccommodateNeuronWeights(int neuronNumber, double[] dataVector, int iteration, double distance, double radius)
        {
            var neuronWghts = Network.Neurons[neuronNumber].Weights;

            var learningRate = LearningFactorFunction.GetLearningRate(iteration);
            var falloffRate = NeighbourhoodFunction.GetDistanceFalloff(distance, radius);

            for (int i = 0; i < neuronWghts.Length; i++)
            {
                double weight = neuronWghts[i];
                neuronWghts[i] += learningRate * falloffRate * (dataVector[i] - weight);
            }
        }
    }

Lets talk a bit about each of the methods.

public virtual void Learn()

It is the main public method which could be used in outside world, so ti will learn Network using all stuff that we injected in constructor. After Lean has executed usage code could use learned Network through the public property. What this method does is: it goes through all iterations up to MaxIterationsCount, then shuffles input space (or not shuffles, it depends on shuffling provider), finds Best Matching Neuron and Accommodates Network weights.

protected virtual int FindBestMatchingNeuron(double[] dataVector)

Is the most expensive operation. As you see it goes through all the neurons in Network and calculated distance from current neuron to dataVector. Then it returns neuron with minimal distance.


protected virtual void AccommodateNetworkWeights(int bestNeuronNum, double[] dataVector, int iteration)

Takes BMN number, asks RadiusProvider for the radius on current iteration and then asks Topology to find all neurons connected to BMN in current radius. For each found neuron it accommodates weights in next method.

protected virtual void AccommodateNeuronWeights(int neuronNumber, double[] dataVector, int iteration, double distance, double radius)

The most interesting line of code in this method is actual accommodation:

neuronWghts[i] = neuronWghts[i] + learningRate * falloffRate * (dataVector[i] - neuronWghts[i]);
Which stands for formula:


Why did I make all methods virtual and so much protected properties? That is intent of my next post on implementation of SOM, where I'm going to talk about Parallelization of calculations in our algorithm.
0 comments
Labels: ,
Reactions:

Tuesday, March 23, 2010

Decorator

I have a story about the doctor who had a very good and fast car - Mercedes. On the way to work he is often stuck in traffic congestion and this makes him mad and late so as an impact his patients suffer. And he has a dream that his car became Ambulance and all cars make the way to him. Only one issue with this: Ambulance should beep and his car has no such ability so your task is to decorate Mersedes so when it goes it beeps.
How can you accomplish this?

DECORATOR

So here we have Car class:

public class Car {
    protected String BrandName;

    public void Go(){
        System.out.println("I'm "+BrandName+" and I'm on my way...");
    }
}

and the Mersedes implementation:

public class MercedesCar extends Car {
    public MercedesCar() {
        BrandName = "Mercedes";
    }
}

The Decorator pattern is used to add some functionality to your objects. In our example we want to add beeping to the concrete implementation of Car, but also we can add other functionality. So in order to save contract of Car class and have base class for all features we create the CarDecorator class like below:

public class CarDecorator extends Car{
    protected Car decoratedCar;

    public CarDecorator(Car car) {
        decoratedCar = car;
    }

    @Override
    public void Go() {
        decoratedCar.Go();
    }
}

as you see it has decoratedCar wrapped, that is why patterns is also called Wrapper.
So in order to add some additional functionality we derive from Decorator class:


public class AmbulanceCar extends CarDecorator {
    public AmbulanceCar(Car car) {
        super(car);
    }

    @Override
    public void Go() {
        super.Go();
        System.out.println("...beep-beep-beep-...");
    }
}

so it was slight extension - beeping :)

And usage looks very friendly - we cover Mersedes with Ambulance features, after that we can cover it with more abilities, in other words we can add features dynamically.


        Car doctorsDream = new AmbulanceCar(new MercedesCar());
        doctorsDream.Go();

Output:

I'm Mercedes and I'm on my way...
...beep-beep-beep-...

I think you extected it. Now lets take a look at the UML diagram of this wisdom:


This pattern has some similarities to the Composite and Adapter patterns. Adapter could change the interface of behavior, but Decorator not (we are derived from Car). Composite works with lot of components, not like Decorator with only one.

What was interested for me here is usage of the IDEA instead of eclipse and I must say that this is just heaven to use it. I feel myself comfortable with Resharper so it was quite very easy to write code on the fly. And porting of code from eclipse did not make any issues...
4 comments
Labels: ,
Reactions:
Subscribe to: Posts (Atom)