Education Archives - Andriy Buday

ID3-impl

March 26, 2010 Education, Pedagogic Practice No comments

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.

No comments

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

March 25, 2010 Education, Ukrainian 2 comments

Вступ

Алгоритми 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

k-means lecture text

March 11, 2010 Education, Pedagogic Practice No comments

Привітання та дуже загальний вступ

Привіт. Мене звати Андрій Будай і сьогодні я вестиму цю пару, темою якої є k-means алгорим. Some parts will be in English, so please do not scare if I switch to English unexpectedly, like I just did.

As you all know we are talking about the clustering of data. Human brains are very good at finding similarity in things. For example, biologists have discovered that things belong to one of two types: things are either brown and run away or things are green and don’t run away. The first group they call animals, and the second is plants.
Процес групування речей по певних ознаках ми називаємо кластеризацією. Якщо ми говоримо про то, що біологи почали поділяти тварин на ряди, роди та види, то ми говоримо про ієрархічну класифікацію. Яку я передбачаю ви вже розглянули, зоокрема підхід ієрархічної кластиризації згори-вниз та знизу-вгору.

Розуміння Partitioning алгоритмів

А що якщо ми хочемо групувати дані не в порядку збільшення або зменшення об”єму груп, якщо ми хочемо погрупувати N векторів даних на K кластерів за один логічний хід? Такий різновид кластерізації називається Partitioning алгоритмами. Іншими словами ми розбиваємо множину.

Ще раз нагадаємо що таке розбиття множини:

Система множин S={X₁ … X_n} називається розбиттям множини M, якщо ця система задовольняє наступним умовам:

будь-яка множина X_k з S є підмножиною множини M:

∀X∈S: X⊆M

будь-які дві множини X_i, X_j з S мають порожній перетин:

∀X_i, X_j ∈ S: X_i≠X_j→X_i∩X_j = ∅.

об’єднання всіх множин, які входять в розбиття M, дає множину M:

$bigcup_{X in S} X = M$

Partitioning алгоритми розбивають множину на певну кількість груп за один крок, проте результати покращуються із процесом ітерування. До найвідоміших partitioning алгоритмів відносяться k-means та його модифікації із доповненнями, quality threshold алгоритм також для кластеризації можуть бути використані Locality-sensitive hashing та Graph-theoretic methods. Якщо буде час то ми поговорими і про них також.

K-means алгоритм

Отже, k-means. Насправді алгорим не є складним і я сподіваюся що всі із вас будуть розуміти суть алгоритму та будуть мати палке бажання його реалізувати. Це моя мета на сьогоднішню пару. []

Завданням алгоритму є здійснити розбиття N векторів даних на K груп. Причому число k є попередньо відомим – або є вхідним параметром алгоритму як і дані.

Опис
[Цю частину я збираюся продиктувати]

Маючи список даних спостережень (x₁, x₂, …, x_n), де кожен x є вектором розмірності d, k-means кластеризація призначена для розбиття цього списку із n спостережень на k підмножин (k < n), в результаті чого ми повиння отримати таке розбиття S={S₁, S₂, …, S_k}, в якому внутрішньокластерна сума квадратів норм є мінімізованою:

$underset{mathbf{S}} operatorname{arg,min} sum_{i=1}^{k} sum_{mathbf x_j in S_i} left| mathbf x_j - boldsymbolmu_i right|^2$

де μ_i є центром S_i.

Кроки алгоритму

Перш за все нам слід мати множину із k центрів m₁⁽¹⁾,…,m_k⁽¹⁾, які можуть бути визначені або випадковим чином, або евристичним шляхом. Алгоритм складається із двох основних кроків – кроку присвоєння та оновлення.

Ініціалізація: Перш за все нам слід мати множину із k центрів m₁⁽¹⁾,…,m_k⁽¹⁾,
які можуть бути визначені або випадковим чином, або евристичним шляхом.
Алгоритм складається із двох основних кроків – кроку присвоєння та
оновлення.

Крок присвоєння: Присвоюємо кожен вхідний вектор до кластеру із найближчим центром.

$S_i^{(t)} = left{ mathbf x_j : big| mathbf x_j - mathbf m^{(t)}_i big| leq big| mathbf x_j - mathbf m^{(t)}_{i^*} big| text{ for all }i^*=1,ldots,k right}$

Крок оновлення: Вираховуємо нові центри, щоб вони найкраще підходили векторам за які вони відповідають.

$mathbf m^{(t+1)}_i = frac{1}{|S^{(t)}_i|} sum_{mathbf x_j in S^{(t)}_i} mathbf x_j$

Повторюємо кроки присвоєння та оновлення допоки присвоєння ще змінюються.

Демонстрація
[here I’m going to switch to English and demonstrate steps of the algo at board]


1) k initial “means” (in this case k=3) are randomly selected from the data set (shown in color).	2) k clusters are created by associating every observation with the nearest mean.	3) The centroid of each of the k clusters becomes the new means.	4) Steps 2 and 3 are repeated until convergence has been reached.

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

Other variations of the K-means algorithm

Because of some disadvantages of standard algorithm we’ve got few
different variations of it like Soft K-means, when data element is
fuzzy associated with mean, or like K-means++, which is additions to
the K-means to initialize cluster means better.

K-means++
With the intuition of spreading the k initial cluster centers away from
each other, the first cluster center is chosen uniformly at random from
the data points that are being clustered, after which each subsequent
cluster center is chosen from the remaining data points with
probability proportional to its distance squared to the point’s closest
cluster center.

Soft K-means алгоритм

В Soft K-means алгоритму кожен вектор має часткову приналежність до якогось кластеру, так як же і в розмитій логіці – існуть не тільки 1 та 0, а ще й 0.667. Таким чином, вектори, що знаходяться ближче до центру кластеру мають більшу приналежність до нього, а ті які знаходяться по краях мають дуже малу приналежність. Отже, для кожного вектора x ми маємо коефіцієнт який відповідає за приналежність до k-того кластеру u_k(x). Звичайно, що сума коефіцієнтів для заданого вектора x є рівною 1:

$forall x left(sum_{k=1}^{mathrm{num.} mathrm{clusters}} u_k(x) =1right).$

Таким чином, центр кластеру вираховується як середнє всіх векторів, домножених на цей коефіцієнт приналежності до кластеру:

$mathrm{center}_k = {{sum_x u_k(x)^m x} over {sum_x u_k(x)^m}}.$

Коефіцієнт є обернено пропорційний до відстані до центру кластеру:

$u_k(x) = {1 over d(mathrm{center}_k,x)},$

опісля коефіцієнти нормалізуються із використання параметра m > 1 щоб сума була рівною 1 за такою формулою:

$u_k(x) = frac{1}{sum_j left(frac{d(mathrm{center}_k,x)}{d(mathrm{center}_j,x)}right)^{2/(m-1)}}.$

Коли m
близьке до 1, кластери ближчі до центру мають більшу приналежність, а ті що дальше мають меншу приналежність. Для m = 2, це відповідає лінійній нормалізації коефіцієнтів, щоб отримати суму 1 і алгоритм подібний до звичайного k-means.

Кроки цього алгоритму є дуже подібними до звичайного:

Вибираємо кількість кластерів.
Випадковим чином вибираємо приналежність кожного із векторів до якогось кластеру.
Повторюємо наступне допоки алгоритм не збіжиться (це коли зміна коефіцієнтів між ітераціями не перевищує деякого числа , що є порогом чутливості) :
- Вираховуємо центр для кожного кластеру за допомогою формули наведеної вище.
- Для кожного вектору вираховуємо коефіцієнти приналежності до кластерів.

Цей алгоритм також має деякі проблеми що й у звичайному алгоритму, зокрема залежність від початково вибраних кластерів, та не обов”язкове знаходження глобального мінімуму.

Можливий підхід до реалізації

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

[Не дуже хочу закидати реалізацію, щоб студенти завчасно не використали її]

He-he! I’ve got it in about 3.5 hours.

I would say that core algorithm code looks very good, at least take a look at method Process:

        public void Process()
        {
            Initialize();

            while (!ClustersRemainTheSame())
            {
                AssignStep();
                UpdateStep();
            }
        }
I’ve also used realized algorithm in two applications – one is clusterization of animals by theirs properties and another is graphical demoing usage. Below is nice screenshoot:

Application

[If I’ll see that we are ok with English this part will be in it, otherwise we will have this in Ukrainian.]

“The k-means clustering algorithm is commonly used in computer vision as a form of image segmentation. The results of the segmentation are used to aid border detection and object recognition. In this context, the standard Euclidean distance is usually insufficient in forming the clusters. Instead, a weighted distance measure utilizing pixel coordinates, RGB pixel color and/or intensity, and image texture is commonly used“

One of the application examples is clustering colors in image to compress image. A good article on this is written up here.

Завершення пари

Побажання зробити реалізацію алгоритму

Час на питання

P.S. So far I have some good plan for Friday… not 100% complete, but I’m satisfied with what I have. And tomorrow I’m going to work on this once again. Also not really good that I just translated a lot of stuff from wiki pages.

No comments

K-means algorithm for Students of Lviv National University

March 9, 2010 Education, Pedagogic Practice, Ukrainian No comments

On Friday, I will have my first teaching experience (or at least teaching students of my University). This is part of the Master Year pedagogic practice. Subject is called “Data Mining” and theme of Friday’s lesson will be “K-means” algorithm.

Few things here before I start
I will have this post mixed of English and Ukrainian. Why? Because the way I’ll be presenting algorithm in both languages and because I need some report in Ukrainian, so do not want to double write a lot – I’m lazy ass as someone said.

План уроку (Agenda)

1. Привітання та дуже загальний вступ

Даю знати хто я і про що буду розповідати. Also I have a nice joke in English that could grab attention of the students. Hope they will be able to recognize and understand my English.

2. Розуміння Partitioning алгоритмів

Тут я нагадаю що таке Cluster analysis та згадую про Hierarchical і Partitional різновиди. І дещо про різниці між ними.

3. K-means алгоритм

– завдання алгоритму
– введення позначень
– кроки алгоритму
– демонстрація алгоритму як на дошці так і на комп”ютері
– переваги та недоліки

4. Other variations of the K-means algorithm

Because of some disadvantages of standard algorithm we’ve got few different variations of it like Soft K-means, when data element is fuzzy associated with mean, or like K-means++, which is additions to the K-means to initialize cluster means better.

5. Soft K-means алгоритм

– різниця в кроках алгоритму

6. Можливий підхід до реалізації (можливо напишу програму ще раз)

7. Application

If I’ll see that we are ok with English this part will be in it, otherwise we will have this in Ukrainian.
One of the application examples is clustering colors in image to compress image.

8. Побажання зробити реалізацію алгоритму

9. Час на питання

I hope tomorrow I’ll have article with whole lesson text, more structured and with examples, also hope to write k-means plus demo from scratch. Will see how fast am I.

No comments

Education

ID3-impl

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

Вступ

Означення

Алгоритм ID3

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

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

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

k-means lecture text

K-means algorithm for Students of Lviv National University

Highlights

Recent Posts

Recent Comments

Archives

Education

ID3-impl

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

Вступ

Означення

Алгоритм ID3

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

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

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

k-means lecture text

K-means algorithm for Students of Lviv National University

Highlights

Recent Posts

Recent Comments

Categories

Archives