Pedagogic Practice Archives

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

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