March 25, 2010 Education, Ukrainian 2 comments
Дерева прийняття рішень, алгоритми 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)
тоді інформативність передана цим розподілом, або Ентропія Р, визначається так::
Для прикладу, якщо 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):
В нашому прикладі гри в гольф, ми отримуємо 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):
У випадку гри в гольф, для властивості Небо, ми маємо:
Дамо означення приросту інформації Gain(X,T) як
Це представляє різницю між інформацією необхідною для визначення елемента із Т і інформації необхідної для визначення елемента із Т, після того, якщо значення властивості Х було визначено, іншими словами приріст інформації завдяки відомості властивості Х.
В нашому прикладі із грою в гольф, для властивосіті Небо, приріст буде:
Якщо взяти властивість Вітряно, ми отримаємо такі значення
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.
Happy Birthday to you, Natali!
March 24, 2010 Personal 2 comments
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.
My implementation of Self-Organizing Map
March 24, 2010 KohonenAlgorithm, MasterDiploma No comments
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; }
NeuronsCount { get; }
int RowCount { get;
}
}
int ColCount { get;
}
}
double WholeTopologyRadius { get; }
int
GetNeuronNumber(Location
location);
GetNeuronNumber(Location
location);
Location
GetNeuronLocation(int neuronNumber);
IList<int> GetDirectlyConnectedNeurons(int neuronNumber);
Dictionary<int, double>
GetNeuronsInRadius(int neuronNumber, double radius);
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 6×5 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;
}
TopologyRadius { get; private set;
}
public
double TimeConstant { get; private
set; }
double TimeConstant { get; private
set; }
public
DefaultRadiusProvider(int
maxIterations, double startRadius)
DefaultRadiusProvider(int
maxIterations, double startRadius)
{
MaxIterations = maxIterations;
TopologyRadius = startRadius;
TimeConstant = maxIterations / Math.Log(startRadius);
}
public double GetRadius(int
iteration)
iteration)
{
return
TopologyRadius*Math.Exp(-iteration/TimeConstant);
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 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)
override double
GetLearningRate(double iteration)
{
return StartLearningRate * Math.Exp(- iteration /
MaxIterationsCount);
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; }
set; }
public ITopology Topology { get; private set; }
protected
IShuffleProvider
ShuffleProvider { get; set; }
IShuffleProvider
ShuffleProvider { get; set; }
protected ILearningDataProvider LearningDataProvider { get; set; }
protected
IRadiusProvider
RadiusProvider { get; private set;
}
IRadiusProvider
RadiusProvider { get; private set;
}
protected
INeighbourhoodFunction
NeighbourhoodFunction { get; set; }
INeighbourhoodFunction
NeighbourhoodFunction { get; set; }
protected IMetricFunction MetricFunction { get; set; }
protected
ILearningFactorFunction
LearningFactorFunction { get; set; }
ILearningFactorFunction
LearningFactorFunction { get; set; }
protected
int MaxIterationsCount { get; set; }
int MaxIterationsCount { get; set; }
public SomLearningProcessor(
ILearningDataProvider
learningDataProvider,
learningDataProvider,
INetwork network,
IMetricFunction
metricFunction,
metricFunction,
ILearningFactorFunction
learningFactorFunction,
learningFactorFunction,
INeighbourhoodFunction
neighbourhoodFunction,
neighbourhoodFunction,
int maxIterationsCount,
IShuffleProvider
shuffleProvider)
shuffleProvider)
{
LearningDataProvider =
learningDataProvider;
learningDataProvider;
Network =
network;
network;
Topology =
network.Topology;
network.Topology;
MetricFunction =
metricFunction;
metricFunction;
LearningFactorFunction = learningFactorFunction;
NeighbourhoodFunction = neighbourhoodFunction;
MaxIterationsCount =
maxIterationsCount;
maxIterationsCount;
ShuffleProvider = shuffleProvider;
RadiusProvider = new DefaultRadiusProvider(maxIterationsCount,
Topology.WholeTopologyRadius);
Topology.WholeTopologyRadius);
}
public virtual
void Learn()
void Learn()
{
int vectorsCount =
LearningDataProvider.LearningVectorsCount;
LearningDataProvider.LearningVectorsCount;
IList<int> suffleList = new ShuffleList(vectorsCount);
for (int
iteration = 0; iteration < MaxIterationsCount; iteration++)
iteration = 0; iteration < MaxIterationsCount; iteration++)
{
suffleList = ShuffleProvider.Suffle(suffleList);
for (int
dataInd = 0; dataInd < vectorsCount; dataInd++)
dataInd = 0; dataInd < vectorsCount; dataInd++)
{
double[] dataVector =
LearningDataProvider.GetLearingDataVector(suffleList[dataInd]);
LearningDataProvider.GetLearingDataVector(suffleList[dataInd]);
int bestNeuronNum =
FindBestMatchingNeuron(dataVector);
FindBestMatchingNeuron(dataVector);
AccommodateNetworkWeights(bestNeuronNum, dataVector, iteration);
}
}
}
protected
virtual int
FindBestMatchingNeuron(double[]
dataVector)
virtual int
FindBestMatchingNeuron(double[]
dataVector)
{
int result = -1;
Double minDistance = Double.MaxValue;
for (int i
= 0; i < Network.Neurons.Count; i++)
= 0; i < Network.Neurons.Count; i++)
{
double distance =
MetricFunction.GetDistance(Network.Neurons[i].Weights, dataVector);
MetricFunction.GetDistance(Network.Neurons[i].Weights, dataVector);
if
(distance < minDistance)
(distance < minDistance)
{
minDistance = distance;
result = i;
}
}
return
result;
result;
}
protected
virtual void
AccommodateNetworkWeights(int
bestNeuronNum, double[] dataVector, int iteration)
virtual void
AccommodateNetworkWeights(int
bestNeuronNum, double[] dataVector, int iteration)
{
var radius = RadiusProvider.GetRadius(iteration);
var
effectedNeurons = Topology.GetNeuronsInRadius(bestNeuronNum, radius);
effectedNeurons = Topology.GetNeuronsInRadius(bestNeuronNum, radius);
foreach (var
effectedNeuron in
effectedNeurons.Keys)
effectedNeuron in
effectedNeurons.Keys)
{
var
distance = effectedNeurons[effectedNeuron];
distance = effectedNeurons[effectedNeuron];
AccommodateNeuronWeights(effectedNeuron, dataVector, iteration,
distance, radius);
}
}
protected
virtual void
AccommodateNeuronWeights(int
neuronNumber, double[] dataVector, int iteration, double
distance, double radius)
virtual void
AccommodateNeuronWeights(int
neuronNumber, double[] dataVector, int iteration, double
distance, double radius)
{
var neuronWghts =
Network.Neurons[neuronNumber].Weights;
Network.Neurons[neuronNumber].Weights;
var
learningRate = LearningFactorFunction.GetLearningRate(iteration);
learningRate = LearningFactorFunction.GetLearningRate(iteration);
var
falloffRate = NeighbourhoodFunction.GetDistanceFalloff(distance,
radius);
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]);
(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.
Decorator
March 23, 2010 Design Patterns 4 comments
I have a story about the doctor who had a very good and fast Mercedes. On the way to work he is often stuck in traffic congestion and this makes him mad and late making his patients suffer. He has a dream of his car becoming Ambulance so that all cars make the way. Only one issue with this: Ambulance should beep loud. Currently his car has no such loud horn. The doctor also doesn’t want to waive his warranty by changing internals of this car. Let’s decorate Mersedes so when you drive it beeps real loud. How can we accomplish this using a Decorator design pattern?
DECORATOR
So here we have Car class and Mersedes implementations:
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:
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:
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.
Output:
I’m Mercedes and I’m on my way…
…beep-beep-beep-…
…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.
Resharper – navigating to .Net Framework code
March 23, 2010 Resharper No comments
As you know with Resharper when you press “Ctrl+B” you navigate to the declaration of thing you are currently located on. But when you press that on double for example? In Visual Studio you are able to navigate to the metadata view, but Resharper provides 3 options: Object Browser, MetadataView and actual .Net Framework code. If you have no appropriate mscorlib.pdb Resharper will download it like on the picture below:
So finally you are able to see this code:
namespace
System
{
[ComVisible(true)]
[Serializable]
public
struct
Double
: IComparable,
IFormattable, IConvertible, IComparable<double>,
IEquatable<double>
{
public
const double
MinValue = –1.79769313486232E+308;
public
const double
MaxValue = 1.79769313486232E+308;
public
const double
Epsilon = 4.94065645841247E–324;
public
const double
NegativeInfinity = –Infinity;
public
const double
PositiveInfinity = Infinity;
public
const double NaN
= NaN;
//….
System
{
[ComVisible(true)]
[Serializable]
public
struct
Double
: IComparable,
IFormattable, IConvertible, IComparable<double>,
IEquatable<double>
{
public
const double
MinValue = –1.79769313486232E+308;
public
const double
MaxValue = 1.79769313486232E+308;
public
const double
Epsilon = 4.94065645841247E–324;
public
const double
NegativeInfinity = –Infinity;
public
const double
PositiveInfinity = Infinity;
public
const double NaN
= NaN;
//….
This is one of things why I love Resharper, no need to go for another tool like Reflector.
Simple example to see multithreading data sharing issues
March 23, 2010 .NET, Concurrency No comments
I heard a lot of the corruption that could be made by the multiple threads when they share same data. And understanding why that happen is not so hard, but I wanted some bright example of it, which will be able to quickly show what is going on.
So here is my example:
public class Counter
{
public
int Count = 0;
int Count = 0;
public
void UpdateCount()
void UpdateCount()
{
for
(int i = 0; i < 10000; i++)
(int i = 0; i < 10000; i++)
{
Count = Count + 1;
}
}
}
class Program
{
static
void Main(string[]
args)
void Main(string[]
args)
{
var
counter = new Counter();
counter = new Counter();
var
threads = new Thread[500];
threads = new Thread[500];
for
(int i = 0; i < threads.Length;
++i)
(int i = 0; i < threads.Length;
++i)
{
threads[i] = new Thread(counter.UpdateCount);
threads[i].Start();
}
foreach
(var thread in threads)
(var thread in threads)
thread.Join();
Console.WriteLine(string.Format(
@”If you are running this code on multiple processors machine you
probably will not get expected ThreadCount*Iterations={0}*{1}={2}, but
less number, which is currently equal to {3}”,
probably will not get expected ThreadCount*Iterations={0}*{1}={2}, but
less number, which is currently equal to {3}”,
threads.Length, 10000,
threads.Length * 10000, counter.Count));
threads.Length * 10000, counter.Count));
}
}
As you see I’m using 500 threads. Why? First it is because this ensures that lot of them will be allocated on another processor and second is because the UpdateCount runs “Count = Count + 1” that is quite very trivial and requires about 3 atomic operations, so to increase possibility to run them in concurrent threads I increased their count.
Below is the output:
If you are running this code on multiple processors machine you probably will no
t get expected ThreadCount*Iterations=500*10000=5000000, but less number, which
is currently equal to 4994961
Press any key to continue . . .
t get expected ThreadCount*Iterations=500*10000=5000000, but less number, which
is currently equal to 4994961
Press any key to continue . . .
As you see the actual number of the Count field is less than expected. We lost one each time when next happens at once:
Thread 1: Reads Count (1000)
Thread 2: Reads Count (1000)
Thread 1: Increases Count (1001)
Thread 2: Increases Count (1001)
Thread 1: Writes Count (1001)
Thread 2: Writes Count (1001) – he-he so it wrote back the same number, not 1002
You probably already know how to solve this with lock or Interlocked class or other stuff.
For example just change line Count = Count + 1; with line Interlocked.Increment(ref Count); or lock (this)Count = Count + 1; But I’m getting fun writing this.
Code Complete – Classes, Methods, Defence Programming
March 21, 2010 Book Reviews, Clean Code, Opinion No comments
Yesterday I’ve read 3 chapters of the “Code Complete“. First one of them was a “Classes” and second was “Methods”. I would say that I took almost nothing for myself from those pages, but the third one was “Defense Programming” and it was quite enjoyable to read.
Classes
Class should stand for one logical unit of understanding from real world or from your system. In other worlds it should be noun, that could do some appropriate operations. It is not just a set of data. Also class should have Single Responsibility – not doing things it should not do and not be cohesive to other classes. Class should not contain too much data and too many methods.
After that McConnel talks about the Composition and Inheritance.
Use inheritance when behavior contract is the same and data is the same to some extend, but only concrete behavior differs, but not expectations of it.
Use composition when behavior is 100% the same, but you still could distinguish what you have before and what you would like to have further.
This means that no need to have AccountLessPerson if the person does not have bank account, it definitely better to have Person with field BankAccount.
Liskov Substitution Principle says that once you have class B derived from class A, other classes should work with B by the contract which is the same as A declares, only enhancements to the behavior is allowed, no real change in it.
Methods
It was boring to read this chapter. i.e. methods should have appropriate names, they should not be longer than N lines of code and be readable, they should not take more than 7 parameters, they should not change params, they should not change global fields etc….
It had to be much better to read there more about how methods should interact with other system.
Defence Programming
This was the most interesting part for me. This all is about building the wall of protection to your system. And this is needed to serve two main purposes: first is stability of the system and the second is for insuring correct behavior.
Assert
Assertion is the way to defense your code from wrong input data, and even defensing yourself from giving wrong result. For example in the beginning of method GetOrdersForAccountNumber(int accountNumber) you could have Assert.That(accountNumber > 0, “since you will not be able to make order with wrong number”) and after you finished with all calculations you could have Assert.That(orders != null, “because don’t think that that is good idea to pass out null object…”).
Exception handling
Exceptions is the tool for working with unusual situations that occur in your application. Some languages still don’t have build-in exception handling, and I’m so lucky that I work with such language like C#. McConner says “Develop with language, not on language”, but the C# just leads to writing a good code. Exception handling is quite big theme to discuss so I hope to have separate post on it.
Self-Organizing Maps – Заженемо речі в гратку
March 20, 2010 KohonenAlgorithm, MasterDiploma 2 comments
Одним із хороших тестів Самоорганізаційної карти є двовимірна інтерпретація двовимірного вхідного простору. Нейрони нейромережі почитають заповняти той простір із якого приходять вхідні вектори, таким чином можна наочно спостерігати за тим чи нейромережа дає хороші результати.
Для цього я використав решітку розміру 10 на 10. Нейромережа була початково ініціалізована випадковими значеннями нейронів від 0.25 до 0.75. Таким чином якщо постійно вчити нейромережу випадковими значеннями (від 0 до 1), то гратка повинна “розвернутися” на всю площину.
Я використовую 500 кроків на кожному із яких проганяю 100 випадкових точок для того щоб згладити навчання.
Ініціалізація:
Перша ітерація:
Друга:
300:
Остання (500та):
Якщо вхідні значення подавати не із всієї множини X [0, 1], Y[0, 1], а із множини що займає певний об”єкт, то карта просто дуже легко впишеться в нього.
Щоб переконатися в цьому я використав силует дівчини і для навчання подавав тільки точки, які входили в площину, де знаходиться дівчина.
Зробити це для мене було, корисно, оскільки я таки знайшов недолугі частини моєї імплементації і виправив декілька помилок в алгоритмі. Надалі я можу спокійно працювати над паралелізацією обрахунків.
Я сподіваюся що вам сподобалося. Коментарі?
How to add icon for your custom UserControl to the Toolbox
March 19, 2010 .NET, HowTo, WindowsForms No comments
I read about ToolboxBitmapAttribute and while doing my usual work have decided to use it.
First of all I created my UserControl named BufferedControl which should provide double buffering functionality for me. Once I finished with my control I navigated to Toolbox to add new tool like on the picture:
And do you know what happend next? It said to me that there is no controls which could be added to the Toolbox. But why? It is derived from UserControl and looks fine. So in order to see what is the difference I added empty UserControl1 and was able to add it to the Toolbox. I thought that the reason is because I do not have designer file for my control and some specific methods like Initialize(), but after I added them nothing helped. I did more research and finally figured out that I did not have default public constructor. My constructor was like here:
public
BufferedControl(IBufferedControlController controller)
BufferedControl(IBufferedControlController controller)
{
Controller = controller;
BufferContext = new BufferedGraphicsContext();
SizeGraphicsBuffer();
SetStyle(ControlStyles.OptimizedDoubleBuffer, false);
SetStyle(ControlStyles.DoubleBuffer,
false);
false);
}
So lets move to adding icon of your UserControl to the Toolbox
1) First add your control and draw the icon. Below is screenshot of what I have for this.
a) Once you done, you should ensure that your control has public default constructor and that OnPaint method will not raise exceptions after it was called on instance created with default constructor.
b) Also go to properties of your icon and set Build Action –> Embedded Resource.
2) Add ToolboxBitmap attribute to your control class declaration. In my case it looks like below:
namespace
Som.Application.Grid
Som.Application.Grid
{
[ToolboxBitmap(“Som.Application.Grid.BufferedControl.ico”)]
public class BufferedControl : UserControl
{
//…
3) Navigate to ToolBox and add your control from your assembly:
That’s it!
I love Performance Profiler
March 14, 2010 IDE, Performance 2 comments
Honestly I haven’t used any Performance Profiler, since I did not feel need to use it and also I thought that it could be boring… How was I wrong! It is so easy and intuitive, I’m getting super good reports with highlighting of expensive code and it keeps highlighting in Visual Studio. So I’m always aware which code is expensive.
Take a look:
I love it.
