Service Oriented Architecture – Introduction

April 22, 2010 SOA No comments

Currently I’m part of local SOA group. Purpose of it is to accumulate information about SOA and its implementation, to talk and discuss different approaches that could be applied with this paradigm of developing software. I volunteered to prepare first introduction presentation. So other more experienced guys will prepare more deep presentations. Right folks? ;)

What is SOA?

Over internet you could find lot of different definitions to SOA. One of the most simplest is:

Service Oriented Architecture is an architectural style of building software applications that promotes loose coupling between components for their reuse.

Term itself could be a bit confusing, because it combines two different things. First two words describe software methodology – how to build software. Third word, architecture, represents picture of company’s assets, which all together should build a good building. So, in other words, we could say that SOA is strategy that forces building software assets in business using service-oriented methodology.

Wikipedia gives more complex definition:
A paradigm for organizing and utilizing distributed capabilities that may be under the control of different ownership domains. It provides a uniform means to offer, discover, interact with and use capabilities to produce desired effects consistent with measurable preconditions and expectations.

SOA is not simply IT solution, it is whole paradigm shift. It is another step to the IT industry dream, when we will not need write low level code, but just combining different ready components to have product which is good for immediate selling. It is about describing, building, using and managing your IT environment with focus on services and capabilities it provides rather then on concrete technology used for that.



Advantages both for Business and for Development

Before we start with what stands behind SOA lets first take a look on advantages that it brings for Business and Development process.

Advantages of service-oriented development:

Software reuse is one of the most commonly used arguments to justify SOA. If services are developed of good size and correct scale they could be reused. Consider that you company has for sailing departments, each of them works with orders, so all of them have code that checks customers credit card, books order and so on. But checking credit card is almost 100% the same task in all departments, so developers could gather code and make it shared for all systems, in this case software reuse is accomplished. All that we need to have in our systems is client that is able to consume service. Systems are no longer concerned about the internal verification process. In future is company will create new department it will just reuse existing service, so development time will be saved and money for business.
But we could not say that reuse will be accomplished everytime. First of all service should be of right size, not to big and with correct scope. This meas that we will not be able to use ‘verify credit card and book that car’ in department where they sale phones. I also found that by only from 10 to 40 percents of services are reused. This adds additional requirement to implementers to be accurate with choosing correct scope and size of service.
Productivity increase. That is easy, once we achieved re-use system, we could not spend our time on implementing same things, testing them. We only need integrate services and do integration testing, so this becomes more cheaper.
Increased agility. Even if re-use will not be achieved we anyway get additional agility with having services. For example our selling department has divided whole process into few services, like ‘check user’, ‘check credit card’, ‘get order’, ‘ship order’… And if will need change in process we could do this in isolated island of concrete service. That is how we get more flexibility.    

Advantages of SOA strategy are:

Better alignment with business. Business people can now imagine how their business are constructed in terms of technology. Once they better understand how application is built they could promote their requirements to development teams in more efficient way. And as well development team is now more suitable with understanding of what does that business really do. It is now much easier to explain why having credit card in one service is good decision.
A better way to sell architecture to the business. Having gap in understanding how all is really implemented was also a preventing thing to sell IT product to the business.

What are services?

So we talk about services. But what exactly are those services?
Service is complete self-contained component, that provides defined tasks. List of tasks could be obtained by consumer using agreed contracts. Consumer should not know about internal implementation of service. Communication between consumer and service should be done through platform and language independent contracts.

Here is list of just mentioned properties of good Service:

  • Self-contained module that performs a predetermined task
  • Software components that have published contracts/interfaces
  • Black-box to the consumers
  • Platform-Independent
  • Language-Independent
  • Operating-System-Independent
  • Interoperable

Main Architecture Concepts

On the picture below we see how three main parts of SOA interacts with each other.

Loose coupling – Services maintain a relationship that
minimizes dependencies and only requires that they maintain an awareness
of each other.
Service contract – Services adhere to a communications
agreement, as defined collectively by one or more service description
documents.

Service abstraction – Beyond what is described in the service
contract, services hide logic from the outside world.

Service reusability – Logic is divided into services with the
intention of promoting reuse.

Service composability – Collections of services can be
coordinated and assembled to form composite services.

Service autonomy – Services have control over the logic they
encapsulate.

Service optimization – All else equal, high-quality services
are generally considered preferable to low-quality ones.

Service discoverability – Services are designed to be
outwardly descriptive so that they can be found and assessed via
available discovery mechanisms

How could it be implemented?

Since SOA is technology independent we currently have really lot of different possiblities to implement it. So this could be simple Web service, which sends data packed into XML with help of SOAP, at the same time contracts are established with WSDL. Possibility to discover available services could be UDDI.

We could also realize SOA with REST, DCOM, CORBA, DDS and other things.

Also Microsoft has its solution for the SOA which is WCF. It is very great tool to develop distributed application. I’m glad that already have at least some experience using it.

What
are SOA Patterns?

Here is very good site on disign patterns applicable with SOA.

Mistakes when implementing SOA

There are lot of mistakes that could appear when you are trying to introduce SOA in your project. They are listed in Twelve Common SOA Mistakes pdf.

I hope that I will be able to provide a good presentation, since I don’t feel myself to be professional in this area and don’t have enough required background, except of few months using WCF.


No comments

Refactor: Sequential Coupling => Template Method

April 14, 2010 Design Patterns, Refactoring 2 comments

Another colleague brought me present today – the blog post. Thank you. You were right!

We will do some refactoring which will lead us from Anti-Pattern to Pattern. From Sequential Coupling to Template Method. And as I see it could be very common way to refactor bad code that represents mentioned anti-pattern.

So, lets start with the following question. What do you see to be wrong with following code?

  public class Manager
  {
    public void DoTheProject()
    {
      IWorker worker = GetMeWorker();
      worker.PreWork();
      worker.Work();
   
  worker.AfterWork();
    }

Manager is very angry guy and he needs to get the project done. For that he would like to get some worker, which implements IWorker interface, and delegate some work to him. But also manager knows that worker could be new to project so it will require do go ahead and to some preparational work before and maybe something to do after work is done…

What is wrong? Answer is that Manager cares too much about how worker should organize his work. Why should manager know that worker needs to be prepared for work? What do we have here is the Sequential Coupling anti-pattern.

(My definition) 

Sequential Coupling Anti-Pattern – appears when consuming code is forced to call methods of used object in particular sequence to make it work correctly.

If we call Work and then PreWork, code could be broken. And we want to prevent this. For example, we can move all that stuff in one method – Work, but also sometimes it is needed to perform pre or/and after work, but sometimes not. That is why we had following design that allowed us do this. See that StandardWorker doesn’t need do something after he has finished. This was achieved with virtual and abstract methods.

  public interface IWorker
  {
    void
PreWork();
    void
Work();
    void
AfterWork();
  }
  public abstract class
WorkerBase : IWorker
  {
    public
virtual void
PreWork(){}
   
public abstract
void Work();
    public
virtual void
AfterWork(){}
  }
  public class StandardWorker : WorkerBase
  {
    public override
void PreWork()
    {
      Console.WriteLine(“… I need to prepare to work …”);
    }
    public
override void
Work()
    {
     
Console.WriteLine(“… hard work is in process …”);
    }
  }

So, what we need to do is to hide the order in which we call methods, be sure that order remains the same, and still have possibility to override each of method. What I just described is Template Method.

In our example we could leave one method in interface, then implement it in base class with calling everything else we need in correct order, each of those things we call could be overridden, we left them protected to do not show to the world.

  public interface IWorker
  {
    void Work();
  }
  public abstract class
WorkerBase : IWorker
  {
    
    //this is template method
    public
void Work()
    {
      PreWorkActivity();
      WorkActivity();
   
  AfterWorkActivity();
    }
    protected virtual
void PreWorkActivity() { }
    protected abstract void
WorkActivity();
    protected virtual void AfterWorkActivity() { }
  }
  public class StandardWorker : WorkerBase
  {
    protected override
void PreWorkActivity()
    {
      Console.WriteLine(“… I need to prepare to work …”);
    }
    protected override
void WorkActivity()
    {
      Console.WriteLine(“… hard work is in process …”);
    }
  }
  public class Manager
  {
    public
void DoTheProject()
    {
      IWorker worker = GetMeWorker();
      worker.Work();
    }
    private IWorker GetMeWorker()
    {
      return new
StandardWorker();
    }
  }

It really looks for me that it could be common to perform refactoring from Sequential Coupling to Template Method. Hope you liked this post.


2 comments

Null is not equal to null. How could that happen?

April 13, 2010 C# 2 comments

Today one of my colleagues bring me a present – a new blog post!

Please take a look on the following picture and think how could execution step into the if statement. See that oldPerson is null!

She has asked everyone if anyone knows how could this happen. Do you know?

Honestly my first thought was that it is something with Nullable<T>, or maybe method Find isn’t what we think about it. I had thought that it could be LinQ method, which is somehow wrong, whatever. But nothing of that is true. :(

She did not sent the whole picture so we did not know what is the type of oldPerson object. So far we don’t know the type and we know that “!=” behaves somehow different. That’s it! Operator is wrong and I won beer. (of course not :) )

So let’s take a look on implementation of the operator:

    1 using System.Collections.Generic;
    2 
    3 namespace ConsoleApplication1
    4 {
    5     internal class Person
    6     {
    7         public string Name { get; set; }
    8 
    9         public static bool operator ==(Person left, Person right)
   10         {
   11             if (ReferenceEquals(null, right)) return false;
   12             if (ReferenceEquals(left, right)) return true;
   13             return Equals(left.Name, right.Name);
   14         }
   15 
   16         public static bool operator !=(Person left, Person right)
   17         {
   18             return !(left == right);
   19         }
   20 
   21         public bool Equals(Person obj)
   22         {
   23             return (this == obj);
   24         }
   25 
   26         public override bool Equals(object obj)
   27         {
   28             if (ReferenceEquals(this, obj)) return true;
   29             if (obj.GetType() != typeof(Person)) return false;
   30             return (this == ((Person)obj));
   31         }
   32 
   33     }
   34 
   35     class Program
   36     {
   37         static void Main(string[] args)
   38         {
   39             var persons = new List<Person>()
   40                 {
   41                     new Person(){Name = “Ivan”},
   42                     new Person(){Name = “Andriy”}
   43                 };
   44 
   45             foreach (var item in persons)
   46             {
   47                 var oldPerson = persons
   48                     .Find(x => x.Name == item.Name+“Not Andriy”);
   49 
   50                 if (oldPerson != null)
   51                 {
   52                     item.Name = oldPerson.Name;
   53                 }
   54             }
   55         }
   56     }
   57 }

Do you already see where the problem is? It is definitely in line 11: if (ReferenceEquals(null, right)) return false;
if we will get null in right object it will say that null is not equal to null.

Reason why she needs that so much complicated is because she accesses properties of the object in return condition later:
return Equals(left.Name, right.Name);


2 comments

Get started with F#

April 4, 2010 .NET, C#, F# No comments

Renaissance of functional languages

We are at renaissance of functional languages. When I read blog posts I often see guys talking about functional programming and stuff related to it. Community wants more features that functional style provides for us. In response to that creators of languages and technologies are now introducing a lot of amazing cool features to make our life happier. They also create new languages, and so on.

What is going on with C# nowadays?

Let’s start with what we do have with C# nowadays. It has moved to functional side slightly. Introducing LINQ is big step in that direction. We are moving away from imperative programming to functional, for example this simple loop represents imperative way to work with list items.

      foreach (var element in
list)
      {
   
    Console.WriteLine(element);
      }

Using LinQ we can have so much elegant functional syntax:

      list.ForEach(Console.WriteLine);

So we pass function into function. Simply saying that is why we call this functional programming. If example above isn’t so bright take a look on next:

      Func<int, int>
doubleThat = delegate(int x) { return
x * 2; };
      var
from2To20 = from1To10.Select(doubleThat).ToList();

Another example of that C# is more close to those languages is introducing var keyword, which doesn’t mean that we can change type in further code like in dynamic languages, but that is thing which really helps us to write code without being really concerned about types, but the language itself is still strongly typed. If you would say here about C# dynamics, hm.. honestly I’m not a fan of that thing in C#, but maybe it gives some advantages for us.

Immutability

Few days ago I have heard podcast where guy from Microsoft .NET languages team spoke about different features that community had requested to language C#. One of them was immutability and it looks that they are going to introduce this in further releases (after 4.0 of course). So what is immutability? It is something that functional languages has by default and imperative hasn’t :).

For example we have

   int number = 1;
   number = number + 3;

We can change number as many times as we want. But the same in F# will produce compilation error:

(“<-” is assignment operator in F#). In order to make it work you will need another element result:

If you want variable with you 100% want to change you should declare this using mutable keyword:

Functions

So lets move to much interesting – declaring functions:

ten will be immutable variable which has value 10.

Are you familiar with parameter binding in C++ functors? It doesn’t matter but, currying of methods in F# reminds me that. Take a look how we get new method with mixing function multiply and using one frozen parameter.

Using F# library in other .Net languages 

I did all this fun stuff with creating new F# library in Visual Studio. I viewed results of code which interested me with selecting it and pressing ‘Send To Interactive’ from context menu. Next what was interested for me is how can I use that dll in my usual C# program. So I created console application, added reference to my F# lib. Now I can use it like below:

See how things differs out there. Method is seen as method, immutable variables as properties without setter and mutable as properties with setter. Forgot to mention that FirstFSharpProgram  defines with keyword module at the top of *.fs file.

Why?

When could F# be useful? Anywhere you would like. But as it creators says it has lot of multi-threading capabilities plus to that you write immutable code, which was the main root of stupid bugs in imperative programming. Plus to that you can easily use it in combination to other .NET languages.

Don’t miss chance to learn this language if you are interested in it.

Take a look on this elegant Fibbonachi solution: let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)


No comments

Refactoring your code to be multithreaded

April 3, 2010 .NET, Concurrency No comments

In this post I will start with some time consuming algorithm, which is very simple and will move to decrease its execution time with using advantage of my two processors.

Time consuming algorithm

For example you have some complex calculations algorithm, which runs on array of dozens of elements. For simplicity let it be list of doubles like below:

      var
inputVector = new List<double>();
      for (int i = 0; i < 10000; i++)
        inputVector.Add(random.NextDouble());

All complex calculations that you do are located in class OneThreadAlgorithm. It goes through all array and gets index of the element, which is more closer to value d that you provide inside of method FindBestMatchingIndex.

  internal class OneThreadAlgorithm
  {
    public readonly List<double>
InputVector;
   
public OneThreadAlgorithm(List<double> inputVector)
    {
      InputVector = inputVector;
    }
    public int FindBestMatchingIndex(double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      for (int i
= 0; i < InputVector.Count; i++)
      {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[i],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = i;
 
      }
      }
 
    return bestInd;
    }
  }

If you are interested in DistanceProvider, it just returns between two double elements. Take a look on it.

  public static class
DistanceProvider
  {
    public static
double GetDistance(double val1, double
val2)
    {
     
for (int
i = 0; i < 10000; i++)i = i + 1 – 1;
      return Math.Abs(val1 – val2);
    }
  }

As you see I have some loop before returning value. It is needed to imitate hard calculations. I’m not using Thread.Sleep(), because there are some nuances, that will appear when we will move to multithreading, so I would I like to neglect them.

First change: dividing calculations to sections

As we see algorithm just loops through collection of values and finds some element. To make it going in few threads first we need to accommodate it. The intent of our accommodation is to divide calculations to sections, so we introduce following method

    public void FindBestMatchingIndexInRange(int start, int
end, double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      for (int i
= start; i < end; i++)
      {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[i],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = i;
 
      }
      }
      BestMatchingElements.Add(bestInd);
    }

So, what it does is the same that we had previously. Only the difference is that now we start searching for best matching indexes in range starting with index start and finishing with end, also we put result to the BestMatchingElements list. After we went through all sections we can find best matching element only in that list. See that below:

    public int FindBestMatchingIndex(double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
     
BestMatchingElements = new List<int>();
      int sectionLength = InputVector.Count /
ParallelingNumber;
      int start = 0;
      int end = sectionLength;
      for (int i = 0; i < ParallelingNumber; i++)
      {
       
FindBestMatchingIndexInRange(start, end, d);
        start = end;
   
    end += sectionLength;
        if (i == ParallelingNumber – 1) end =
InputVector.Count;
      }
      foreach (var
elementIndex in BestMatchingElements)
      {
        var currentDistance = DistanceProvider.GetDistance(InputVector[elementIndex],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = elementIndex;
        }
      }
      return bestInd;
 
  }

So now it works as well as before, theoretically it is a bit slower, and it does, especially when you divide array to lot of segments (number of segments we define with variable
ParallelingNumber property).

Second modification: storing task information into one object

When we use multithreading we schedule method which represents public delegate void WaitCallback (Object state). So to accomplish this we create new class FindBestInRangeRequest and use it as an object that passes to changed method:

    public void FindBestMatchingIndexInRange(object bestInRangeRequest)

    {
      var request = (FindBestInRangeRequest)bestInRangeRequest;
      double minDist = double.MaxValue;
 
    int bestInd = -1;
      for (int i
= request.Start; i < request.End; i++)
   
  {

That new class FindBestInRangeRequest encapsulates Start, End, D and other values needed to schedule a threading task. See that class:

    internal class FindBestInRangeRequest
    {
      public int Start { get;
private set;
}
      public
int End { get;
private set;
}
      public
double D { get;
private set;
}
      public
ManualResetEvent Done { get; private
set; }
      public
FindBestInRangeRequest(int start, int end, double
d, ManualResetEvent
done)
      {
     
  Start = start;
        End = end;
        D = d;
       
Done = done;
      }
    }

As you see we are also passing the ManualResetEvent
object, which has method Set(), with using it we can identify that task execution has finished.

Third modification: Using ThreadPool

We can allocate threads manually, but that operation is very expensive, so it is strongly recommended to use ThreadPool.
So here is how we do use ThreadPool to call FindBestMatchingIndexInRange.

        var
bestInRangeRequest = new FindBestInRangeRequest(start,
end, d, DoneEvents[i]);
        ThreadPool.QueueUserWorkItem(FindBestMatchingIndexInRange,
bestInRangeRequest);

after we have scheduled all ranges we should ensure that all threads has synchronized. We could do this using

      WaitHandle.WaitAll(DoneEvents);

 method.
Another interesting thing is that saving into BestMatchingElements is not safe, so we use to unsure safe adding.

      Monitor.Enter(BestMatchingElements);
      BestMatchingElements.Add(bestInd);
      Monitor.Exit(BestMatchingElements);

which is the same to the locking with keyword lock.

Full code base of algorithm

  internal class MultiThreadAlgorithm
  {
    public int ParallelingNumber { get; private set; }
    private List<int>
BestMatchingElements { get; set; }
    private ManualResetEvent[] DoneEvents { get;
set; }
   
public readonly
List<double> InputVector;
    public
MultiThreadAlgorithm(List<double> inputVector, int parallelingNumber)
    {
      InputVector = inputVector;
      ParallelingNumber = parallelingNumber;
      DoneEvents = new
ManualResetEvent[ParallelingNumber];
    }
    public int FindBestMatchingIndex(double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      BestMatchingElements = new List<int>();
     
for (int
i = 0; i < ParallelingNumber; i++)
      {
        DoneEvents[i] = new
ManualResetEvent(false);
      }
      int sectionLength = InputVector.Count /
ParallelingNumber;
      int start = 0;
      int end = sectionLength;
      for (int i = 0; i < ParallelingNumber; i++)
      {
        var bestInRangeRequest = new FindBestInRangeRequest(start,
end, d, DoneEvents[i]);
        ThreadPool.QueueUserWorkItem(FindBestMatchingIndexInRange,
bestInRangeRequest);
        start = end;
        end +=
sectionLength;
        if (i == ParallelingNumber – 1) end = InputVector.Count;
      }
      WaitHandle.WaitAll(DoneEvents);
      foreach (var elementIndex in
BestMatchingElements)
      {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[elementIndex],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = elementIndex;
        }
      }
      return bestInd;
 
  }
    public void
FindBestMatchingIndexInRange(object
bestInRangeRequest)
    {
      var request
= (FindBestInRangeRequest)bestInRangeRequest;
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      for (int i
= request.Start; i < request.End; i++)
   
  {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[i],
request.D);
        if (currentDistance < minDist)
        {
          minDist =
currentDistance;
          bestInd = i;
        }
      }
      Monitor.Enter(BestMatchingElements);
      BestMatchingElements.Add(bestInd);
      Monitor.Exit(BestMatchingElements);
     
request.Done.Set();
    }
    internal class
FindBestInRangeRequest
    {
      public int
Start { get; private set; }
      public int End { get;
private set;
}
      public
double D { get;
private set;
}
      public
ManualResetEvent Done { get; private
set; }
      public
FindBestInRangeRequest(int start, int end, double
d, ManualResetEvent
done)
      {
     
  Start = start;
        End = end;
        D = d;
       
Done = done;
      }
    }
  }

Do you see how our class is cumbersome. So that is why do we call multithreading to be complex and not an easy to implement.

Does this pay off?
Of course, it does. I wrote this example, because I’ve been working on another, a bit more complex thing, but generally I did the same.

Here is output of execution of three variants of algorithm: simple, division to sections, multithreading.

One thread result = 9841. TIME: 0H:0M:2S:583ms
One thread with sections result = 9841. TIME: 0H:0M:2S:917ms
Multi threads result = 9841. TIME: 0H:0M:1S:939ms
Press any key to continue . . .

As could bee seen, multithreading variant is much-much faster. It could be even faster if I had more than two processors on my machine.


No comments

Quick & cheap way to rename colum in table – sp_rename

March 31, 2010 QuickTip, SQL No comments

Quick & cheap way to rename colum in table:

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

Get fun!


No comments

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

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.


2 comments

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; }
        int RowCount { get;
}
        int ColCount { get;
}
        double WholeTopologyRadius { get; }
        int
GetNeuronNumber(Location
location);
     
  Location
GetNeuronLocation(int neuronNumber);
        IList<int> GetDirectlyConnectedNeurons(int neuronNumber);
        Dictionary<int, double>
GetNeuronsInRadius(int neuronNumber, double radius);
 
  }

As you see Topology consists with Rows and Columns as usual matrix, but the main point of interest is the method: Dictionary<int, double>

GetNeuronsInRadius(int neuronNumber, double radius); What does it do?
For the found best matching neuron neuronNumber – it should find all neurons which are located in boundaries of provided radius. Please also note that I’m returning pairs <NeuronNumber, DistanceFromItToBMN> in result dictionary. This allow increase performance a bit, because no need to double calculate distances.
Currently I have two finished implementations of ITopology they are SimpleMatrixTopology and BoundMatrixTopology.

Difference between them is that BoundMatrixTopology is closed cover like on the picture below, for matrix 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;
}
        public
double TimeConstant { get; private
set; }
        public
DefaultRadiusProvider(int
maxIterations, double startRadius)
        {
           
MaxIterations = maxIterations;
           
TopologyRadius = startRadius;
            TimeConstant = maxIterations / Math.Log(startRadius);
        }
        public double GetRadius(int
iteration)
        {
            return
TopologyRadius*Math.Exp(-iteration/TimeConstant);
        }
    }

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

when we calculate radius we are using next formula:

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

NeighbourhoodFunction

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

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

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

LearningFactorFunction

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

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

The formula looks like:

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

Other Interfaces 

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

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

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

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

SomLearningProcessor

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

    public class SomLearningProcessor
    {
        public INetwork Network { get; private
set; }
   
    public ITopology Topology { get; private set; }
        protected
IShuffleProvider
ShuffleProvider { get; set; }
        protected ILearningDataProvider LearningDataProvider { get; set; }
        protected
IRadiusProvider
RadiusProvider { get; private set;
}
        protected
INeighbourhoodFunction
NeighbourhoodFunction { get; set; }
        protected IMetricFunction MetricFunction { get; set; }
        protected
ILearningFactorFunction
LearningFactorFunction { get; set; }
        protected
int MaxIterationsCount { get; set; }
        public SomLearningProcessor(
            ILearningDataProvider
learningDataProvider,
            INetwork network,
            IMetricFunction
metricFunction,
            ILearningFactorFunction
learningFactorFunction,
            INeighbourhoodFunction
neighbourhoodFunction,
            int maxIterationsCount,
            IShuffleProvider
shuffleProvider)
        {
            LearningDataProvider =
learningDataProvider;
            Network =
network;
            Topology =
network.Topology;
            MetricFunction =
metricFunction;
           
LearningFactorFunction = learningFactorFunction;
            NeighbourhoodFunction = neighbourhoodFunction;
            MaxIterationsCount =
maxIterationsCount;
           
ShuffleProvider = shuffleProvider;
            RadiusProvider = new DefaultRadiusProvider(maxIterationsCount,
Topology.WholeTopologyRadius);
        }
        public virtual
void Learn()
        {
            int vectorsCount =
LearningDataProvider.LearningVectorsCount;
   
        IList<int> suffleList = new ShuffleList(vectorsCount);
            for (int
iteration = 0; iteration < MaxIterationsCount; iteration++)
            {
           
    suffleList = ShuffleProvider.Suffle(suffleList);
                for (int
dataInd = 0; dataInd < vectorsCount; dataInd++)
                {
                    double[] dataVector =
LearningDataProvider.GetLearingDataVector(suffleList[dataInd]);
                    int bestNeuronNum =
FindBestMatchingNeuron(dataVector);
                   
AccommodateNetworkWeights(bestNeuronNum, dataVector, iteration);
                }
       
    }
        }
        protected
virtual int
FindBestMatchingNeuron(double[]
dataVector)
        {
            int result = -1;
            Double minDistance = Double.MaxValue;
            for (int i
= 0; i < Network.Neurons.Count; i++)
     
      {
                double distance =
MetricFunction.GetDistance(Network.Neurons[i].Weights, dataVector);
                if
(distance < minDistance)
                {
                    minDistance = distance;
                    result = i;
                }
       
    }
            return
result;
        }
        protected
virtual void
AccommodateNetworkWeights(int
bestNeuronNum, double[] dataVector, int iteration)
 
      {
            var radius = RadiusProvider.GetRadius(iteration);
            var
effectedNeurons = Topology.GetNeuronsInRadius(bestNeuronNum, radius);
            foreach (var
effectedNeuron in
effectedNeurons.Keys)
            {
                var
distance = effectedNeurons[effectedNeuron];
               
AccommodateNeuronWeights(effectedNeuron, dataVector, iteration,
distance, radius);
            }
        }
        protected
virtual void
AccommodateNeuronWeights(int
neuronNumber, double[] dataVector, int iteration, double
distance, double radius)
        {
            var neuronWghts =
Network.Neurons[neuronNumber].Weights;
            var
learningRate = LearningFactorFunction.GetLearningRate(iteration);
            var
falloffRate = NeighbourhoodFunction.GetDistanceFalloff(distance,
radius);
       
    for (int
i = 0; i < neuronWghts.Length; i++)
     
      {
                double weight = neuronWghts[i];
 
              neuronWghts[i] += learningRate * falloffRate *
(dataVector[i] – weight);
            }
        }
    }

Lets talk a bit about each of the methods.

public virtual
void Learn()

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

protected
virtual int
FindBestMatchingNeuron(double[]
dataVector)

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

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

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

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

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

neuronWghts[i] = neuronWghts[i] + learningRate * falloffRate *
(dataVector[i] – neuronWghts[i]);

Which stands for formula:

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


No comments