A little bit of fun with face detection in Windows Phone 8

To start off

If anybody is actually looking for Face Detection Libraries for Windows Phone and haven’t tried this one, this is for them. It’s a neat library popping off facedetecionwp7 library by Julia Schwarz. And you can do pretty cool stuffs with it with pretty less hassle.

Let’s have a little fun

Let’s go ahead and get ourselves started with a Windows Phone 8 Project. Our job would be try this library and detect faces in a picture and have some fun with it, say overlay the face with the classic troll face with the laugh. 😛

Troll

Now, no matter what that sounds, let’s give it a shot. I’ve jotted down a very simple GUI to do this one. And it’s as following:

FaceDetection1

If you want to have a closer look at the XAML it will look the following:

<Grid x:Name="LayoutRoot" Background="Transparent">
        <Grid.RowDefinitions>
            <RowDefinition Height="Auto"/>
            <RowDefinition Height="*"/>
        </Grid.RowDefinitions>

       
        <!--TitlePanel contains the name of the application and page title-->
        <StackPanel x:Name="TitlePanel" Grid.Row="0" Margin="12,17,0,28">
            <TextBlock Text="Face Detection in Windows Phone" Style="{StaticResource PhoneTextNormalStyle}" Margin="12,0"/>
            
        </StackPanel>

        <!--ContentPanel - place additional content here-->
        <Grid x:Name="ContentPanel" Grid.Row="1" Margin="12,0,12,0">
            <Button x:Name="CaptureImageButton" Content="Capture Image" HorizontalAlignment="Center" Margin="0" VerticalAlignment="Top" Width="267" Click="CaptureImageButton_Click"/>
            <Image Name="facesPic" HorizontalAlignment="Center" Height="388" Margin="0,170,0,0" VerticalAlignment="Top" Width="427"/>
        </Grid>

        
    </Grid>

Now, you can definitely see that this is a very basic UI. We have a Button with a click event CaptureImageButton_Click and a Image named facesPic.

Now, before we get our hands dirty, let’s go ahead and add reference to a library we will need. We will need WritableBitmapEx from here. This lib is already available on Nuget too, so you can get it from there too.

After you added that in your project reference, you will need a bunch of libraries from FaceDetectionWP8 to make this things work. You can get the classes on there from the following link too.

After you download the .zip , unzip it and include all the classes inside in your project. I added them under a separate folder named FaceDetector.

Let’s move to our MainPage.xaml.cs

Now, the first thing to do is to pick a picture and the best thing to use for that is PhotoChooserTask . Let’s hook up the following snippet in CaptureImageButton_Click event.

private void CaptureImageButton_Click(object sender, RoutedEventArgs e)
        {
            PhotoChooserTask photo = new PhotoChooserTask();
            photo.Completed += new EventHandler&lt;PhotoResult&gt;(photoChooserTask_Completed);
            photo.ShowCamera = true;
            photo.Show();
        }

Now, the next thing to write is definitely photoChooserTask_Completed event handler. Let’s go ahead and write it. First thing to do would be get the chosen photo into a  WritableBitmap as we are going to do some changes on it.

if(e.TaskResult==TaskResult.OK)
{
    BitmapImage SourceBitmap = new BitmapImage();
    SourceBitmap.SetSource(e.ChosenPhoto);
    WriteableBitmap SourceWritableBitmap = new WriteableBitmap(SourceBitmap);

}

Now, the next thing we need to do is downsample the image a bit as most of the Windows Phone devices pack a pretty powerful camera and often the pictures are oversampled. I personally suggest you downsize the image a bit too. I din’t do it in this demo but if you want a faster performance, you really should try that too. I added the following code segment inside the if block.

byte[] downsampledImage = new byte[SourceWritableBitmap.PixelWidth / _downsampleFactor * SourceWritableBitmap.PixelHeight / _downsampleFactor];

Utils.DownSample(SourceWritableBitmap.ToByteArray(), SourceWritableBitmap.PixelWidth, SourceWritableBitmap.PixelHeight, ref downsampledImage, _downsampleFactor);

SourceWritableBitmap = SourceWritableBitmap.FromByteArray(downsampledImage);

The code segment is pretty straight forward here now. The Utils class here is from the FaceDetectionWP8 library. The first argument for Utils.DownSample used here is a Byte Array of the SourceWritableBitmap and it used the WritableBitmapEx we added here before. The second one is the width of the source bitmap and the third one is the height. The last argument passed here is the downsample factor. This was defined as the following in the MainPage class.

int _downsampleFactor = 2;

And then the SourceWritableBitmap is reinitiazed with a downsampled version of it’s own.

The next thing to do would be getting the faces detected of course. 😀 So, why wait? I added the following sinppet for that.

List<FaceDetector.Rectangle> faces = new List<FaceDetector.Rectangle>();
faces = _detector.getFaces(SourceWritableBitmap, 2f, 1.25f, 0.1f, 1, false, true);

I used the defaults here except the last argument that determines whether it should detect multiple faces and I kept it true.  You can have fun with the other params if you want to tweak your haar cascade detection parameters here.

here comes the fun part, now we are going to replace the face/faces in the picture with the troll laugh picture. :P. We can see it returns the faces as a List<FaceDetector.Rectangle>. All we have to do now is paint the Troll laugh in the rectangles returned by the method. fun, huh?

Now, before replacing the Source Image with the Troll Laugh, we need to load it in another WritableBitmap so we can blend the both of them.

StreamResourceInfo MaskImageSri = Application.GetResourceStream(new Uri("Images/Troll.png", UriKind.Relative));
BitmapImage MaskImageBitmap = new BitmapImage();
MaskImageBitmap.SetSource(MaskImageSri.Stream);

WriteableBitmap MaskWritableBitmap = new WriteableBitmap(MaskImageBitmap);

As we got our Troll.png, why don’t we paste it on the source bitmap?

foreach (var r in faces)
{
   int x = Convert.ToInt32(r.X);
   int y = Convert.ToInt32(r.Y);
   int width = Convert.ToInt32(r.Width);
   int height = Convert.ToInt32(r.Height);                    

   System.Windows.Rect destRect = new Rect(x, y, width, height);
   System.Windows.Rect srcRect = new Rect(0, 0, MaskWritableBitmap.PixelWidth, MaskWritableBitmap.PixelHeight);

   SourceWritableBitmap.Blit(destRect, MaskWritableBitmap, srcRect);

}
   SourceWritableBitmap.Invalidate();
   facesPic.Source = SourceWritableBitmap;

Now, this is pretty straight forward too. All we need is we iterated over the faces and we created to separate rect structs. One is from the MaskWritableBitmap so we can get the rect of the portion of the image we are pasting, in this case, the full one and the destination rect is the face rectangle on the source image we are pasting this troll laugh on.

The next thing to do is invoke Blit() method as this one is responsible to blend these two WritableBitmaps. It comes with the WritableBitmapEx library we added before. The first parameter is the destination rectangle where the source rectangle will be pasted. In this case the face rectangle that will be replaced by the troll laughter image. The second parameter would be the WritableBitmap where the rect that would be posted in the source is found. Here this one is the Troll Image and the last one is the rect in the Troll Image that would be transferred to the main bitmap.

We called it on SourceWritableBitmap as we want to paste the troll Laugh on it. And when all is said and done we set facesPic source to the SourceWritableBitmap.

Now all we have to do is build and test the app. And the result is as following:

FaceDetectionScreenshot

So, what are waiting for? Test the demo project here of the article and have fun!

সোজা সাপ্টা ম্যাশিন লার্নিং – কে নিয়ারেস্ট নেইবর (K Nearest Neighbour)

সত্যি কথা বলতে কি, আমরা সবাই একটা বেশ লম্বা থিসিস করে আসি চতুর্থ বর্ষে, আমি জানিনা অন্যদের কথা, কিন্তু অনেক কিছুই আমি ঠিকমতো বুঝিনাই, তাই ঠিকমতো বোঝার ইচ্ছা টা যায়নাই। সেই চেষ্টায় ভাবলাম, যেটুকু বুঝি , লিখে ফেলি। ম্যাশিন লার্নিং জিনিসটা ভারিক্কী শোনালেও জিনিস টার কাজ একটাই, একটা গবেট প্রকৃতির ম্যাশিন কে আপনি কোন নির্দিষ্ট ব্যাপারে ঠিক যে ভাবে চিন্তা করেন সেভাবে তাকে ভাবতে শিখানো বা অন্তত কাছাকাছি কিছু একটা চেষ্টা করা।

ম্যাশিন লার্নিং এ আমার মতো যারা নবিশ তাদের জন্য কিছু বলতে হলে বলা লাগে, যদি ম্যাশিন লার্নিং কে একটু ক্ল্যাসিফাই করার চেষ্টা করি তাহলে দুটো বড়সড় ভাগ পাবেন। প্রথমটার নাম সুপারভাইজড লার্নিং, আরেকটা আনসুপারভাইজড লার্নিং। কোনটা কি এগুলোর সংজ্ঞা নিয়ে ভটভট করার মতো জ্ঞান আমার নাই। তাই সোজা সহজ ভাবে বলি। যদি একটা ম্যাশিন কে শুরু থেকে কিছু শেখানো হয়, তারপর সে কিছু ঠিকঠাক মতো করতে পারে, সেটা দাঁড়ায় সুপারভাইজড লার্নিং এর দলে। বাকিটা হচ্ছে আনসুপারভাইজড।

ম্যাশিন লার্নিং থেকে ম্যাশিন শব্দ টা সরিয়ে ফেলুন, মনে করুন আপনি একটা ম্যাশিন। একটু সুবিধাজনক একটা পরিবেশ চিন্তা করতে গেলে আপনাকে একটু বোকা হতে হবে। ম্যাশিন সাধারণত বোকাসোকা হয়। তাহলে কি করা? চলুন ফেরত যাই ছোটবেলায়। একদম যখন ছোট ছিলেন আপনি তখন নিশ্চই আপনি এতো কিছু জানতেন না। তো সেই হিসাবে সেই সময়টায় আপনি এখনকার একটা বোকা ম্যাশিন এর মতোই ছিলেন। এখন বাকি থাকলো লার্নিং শব্দটা। সহজ কথায় শিক্ষা। আসুন ছোটবেলার আপনাকে কিছু শেখানো যাক।

ভয় নেই। বেশিদূর যাওয়া লাগবেনা। আপনার মার কথাই মনে করুন। আপনার মাই সম্ভবত আপনাকে শিখিয়েছেন সব কিছু্। চিন্তা করুন, আপনার মা আপনাকে চিনতে শিখিয়েছে কোনটা কি? ধরে নিলাম আপনার মা আপনাকে চিনিয়েছে আপেল, ধরে নিলাম, প্রথম আপেলটির রং ছিলো হালকা লাল। পরেরদিন আপনার মা আপনাকে দিলো একটি হালকা সবুজ রঙের আপেল, পরেরদিন একটু গাড় রঙের আরেকটি। চিন্তা করুন একবার, খুবই সাধারণ মনে হওয়া এই ঘটনাটি আসলে ম্যাশিন লার্নিং এর একটি অসাধারন উদাহরণ। আপনি (ম্যাশিন) প্রতিদিন দেখেছেন একটি ভিন্ন আপেল, ভিন্ন রং, ভিন্ন আকার এবং হতে পারে একটু ভিন্ন স্বাদের। কিন্তু আপনি জেনেছেন সব ই আপেল। যদি এমন হতো, প্রতিদিন এক ই রঙের, আকারের আপেল দেখতেন, আপনি হয়তো কোনদিন বিশ্বাস করতে পারতেন নাম আপেল অন্য আকার বা রঙের হয়। আপনার মা খুব নিভৃতে আপনাকে শিখিয়েছেন একটি সাধারণ আপেল দেখতে কেমন হয়। এটাকে সহজ কথায় Generalization বলে। যে কারণগুলো একটা আপেল থেকে বাকিগুলোকে আলাদা করেছে সেগুলোই Feature. একটু ভেবে দেখুন, যদি আমরা গোলকার আকৃতি এবং লাল রং কে আপেলকে অন্য সব কিছু থেকে আলাদা করার Feature হিসেবে ঘোষনা করি, তাহলে আপেলটা দিনশেষে কিছু লাল বলের সাথে গিয়ে জমা হতে পারে। এটিকে বলে Over generalization. আবার উল্টোটি হলে under generalization  ও হয়ে যেতে পারে। 🙂

সুতরাং বোঝাই যাচ্ছে ঘাপলাটা কোথায়। আপনাকে আপেল থেকে অন্য কিছু আলাদা করার জন্যে ঠিক সেই Feature গুলোই গ্রহণ করতে হবে যেগুলো over বা under generalization তৈরী করবেননা। এর মানে হচ্ছে গোলাকার আকৃতি Feature হিসেবে খুব একটা সুবিধার না, অনেক কিছুই গোলাকার হতে পারে। কিভাবে ভালো Feature বের করতে হয় সেটা নিয়ে আমরা ভটভট পরে করবো কোন এক দিন। আসেন কোন কিছু নিয়ে ভটভট করি। আমাদের আজকের লক্ষ্য K-Nearest Neighbor Algorithm দেখা, এটি আসলে একটি Classification Algorithm, সহজ কথায় যেগুলো দিয়ে অনেক কিছু থেকে জিনিসপত্র ভিন্ন ভিন্ন প্রকারে ভাগ করা হয়।

K-Nearest Neighbor Algorithm

K-Nearest Neighbour এর নাম ই যথেষ্ট আসলে এটি কি করে সেটা বোঝানোর জন্যে। সহজ বাংলায় এটি কোন কিছুকে ক্ল্যাসিফাই করে অনেকটা সে জিনিসটার আশেপাশের জিনিসগুলো কোন প্রকারের তার উপর থেকে। ধরুন আপনি একটি গোলাকার জিনিস অনেকগুলো আপেল আর বলের মধ্যে রাখলেন । কে নিয়ারেস্ট নেইবর যেটা বলে সেটা হচ্ছে  আপনার রাখা নতুন বস্তুটি আশেপাশের অধিকাংশ বস্তু যে প্রকারের সেই প্রকারের মধ্যে পরে। যদি আশেপাশের অধিকাংশ জিনিস বল হয়, তাহলে সেটি বল অথবা সেটি আপেল। আজগুবি ঠেকলেও ভুলে যাবেন না, আপনি কিন্তু যে কোন জায়গায় আপনার অজানা জিনিসটি বসাতে পারবেন না। বসাবেন আসলে তার ফিচারের ভিত্তিতে। যদি সেটি সত্যি আপেল হয় এবং আপনার ফিচার ঠিকমতো নির্ণয় করা হয়ে থাকে তাহলে সেটি অবস্থান নেবে আপেলদের পাশেই। তার মানে এই নাম এই অ্যালগরিদম একেবারেই ভুল করেনা। তবে সেটা নিয়ে পরে কথা বলি না হয়।

ছোট্ট একটি উদাহরণ:

মনে করুন, আপনার কাছে এইরকম একটি ডাটাসেট আছে।

Rooms Area Type
1 350 apartment
2 300 apartment
3 300 apartment
4 250 apartment
4 500 apartment
4 400 apartment
5 450 apartment
7 850 house
7 900 house
7 1200 house
8 1500 house
9 1300 house
8 1240 house
10 1700 house
9 1000 house
1 800 flat
3 900 flat
2 700 flat
1 900 flat
2 1150 flat
1 1000 flat
2 1200 flat
1 1300 flat

দেখেই বোঝা যাচ্ছে এটি আকার এবং রুম সংখ্যার ভিত্তিতে আপনার বাসাটি অ্যাপার্টমেন্ট, ফ্ল্যাট না হাউজ সেটার প্রকারভেদ। তাহলে এখানে সহজ কথায় রুম সংখ্যা এবং আকার আমাদের ফিচার। এই স্যাম্পল সেটটি যদি আমরা কোন ম্যাশিন কে শিখাই, তাহলে এটার উপর ভিত্তি করে সে নতুন কোন নোড এই কোন ক্যাটাগরিতে পরে সেটা আপনাকে জানিয়ে দেবে। প্রশ্ন হচ্ছে কিভাবে। আমরা যেটা করবো এখন সেটি হচ্ছে একটি দ্বিমাত্রিক কার্তেসীয় স্থানাংক ব্যবস্হায় X অক্ষ বরাবর Room সংখ্যা এবং Y অক্ষ বরাবর বসাবো Area. এখন এই ছকে নতুন কোন বাসা যখন আসবে তখন সেটিও হবে আসলে একটি ডাটা পয়েন্ট মাত্র। আমরা সেটির আশে পাশের K সংখ্যক ডাটা পয়েন্ট গুলো থেকে দেখে নিবো সেটি কোন প্রকারে পরে। সহজ বাংলায় আমাদের অ্যালগরিদম টা দাঁড়ায় এরকম :

১. স্যাম্পল ডাটা সহ যে সকল Mystery Point (যেগুলো কোন প্রকারে পরে আমরা জানিনা)  বসিয়ে দিন ছকে
২. বের করে নিন Mystery Point গুলো থেকে সকল পয়েন্ট এর দূরত্ব। ৩. এরপর বেছে নিন কাছের K সংখ্যক প্রতিবেশী পয়েন্ট কে।
৪. k সংখ্যক প্রতিবেশীদের সর্বোচ্চ সংখ্যক প্রতিবেশী যে প্রকারের আপনার Mystery Point ও সেই প্রকারের।

আসুন আমরা ছোট্ট একটা কোডে চলে যাই।

কোড:

আমি কোড করার প্ল্যাটফরম হিসেবে নিয়েছি উইন্ডোজ ফোন ৮ এবং আমি চার্ট এর জন্যে ব্যবহার করছি আমার পছন্দের Telerik Rad Controls. আপনারা চাইলে স্প্যারো টুলকিট ব্যবহার করতে পারেন। এটি ফ্রি এবং চমৎকার। চাইলে যে কোন ল্যাংগুয়েজে কোড করে ফেলতে পারেন। আমি এখানে অসম্ভব crude code করে গেছি এবং চেষ্টা করে গেছি কোড বড় হলেও বোধগম্য রাখার। আপনি আপনার মতো সাজিয়ে নেবেন। 🙂

আমরা প্রথমে Node  এবং NodeList নামের দুটি ক্লাস নিয়ে কাজ করবো।

class Node শুরুতে দেখতে অনেকটাই এরকম:

public class Node
{
public int Rooms { get; set; }
public int Area { get; set; }
private NodeType _type = NodeType.unknown;
public NodeType Type {
get
{ return _type; }
set
{
_type = value;
SetForeground();

}
}

private void SetForeground()
{
if (_type == NodeType.apartment)
{
Foreground = new SolidColorBrush(Colors.Red);
}
else if (_type == NodeType.flat)
{
Foreground = new SolidColorBrush(Colors.Green);
}
else if (_type == NodeType.house)
{
Foreground = new SolidColorBrush(Colors.Blue);
}
else
{
Foreground = new SolidColorBrush(Colors.White);
}
}

public SolidColorBrush Foreground { get; set; }

public ObservableCollection Neighbours { get; set; }

public double Distance { get; set; }

public Node()
{

}

}

এখানে প্রথমে যেটা চোখে পরে, সেটা হচ্ছে শুরুতেই Rooms এবং Area বলে দেয়া শুরুতে। এই দুটো আমাদের ফিচার, একটি Node একটি বাসাকে প্রকাশ করে এখানে। সুতরাং এগুলো শুরুতেই ডিফাইন করা। এরপর দেখা যাচ্ছে NodeType বলে দেয়া এবং NodeType এর ভিত্তিতে একটি Foreground বলে দেয়া। এটি করা হয়েছে শুরু চার্ট তৈরী করার সুবিধার্থে। আসুন দেখে নেই NodeType enum টি কিরকম।

public enum NodeType
{
[Description("apartment")]
apartment,
[Description("house")]
house,
[Description("flat")]
flat,
[Description("unknown")]
unknown
}

স্পষ্টতই দেখা যচ্ছে টাইপ গুলো আমরা আমাদের স্যাম্পল ডাটার মতো বলে নিয়েছি। শুধু unknown টাইপটি আমাদের Mystery Point এর জন্যে। যাতে আমরা চার্টে আলাদা করতে পারি কোনটার টাইপ আমি জানিনা। এবার আসুন NodeList ক্লাসটি কিরকম দেখে নেই

public class NodeList
    {
        private int MinAreas { get; set; }
        private int MinRooms { get; set; }

        private int MaxAreas { get; set; }

        private int MaxRooms { get; set; }

        public ObservableCollection<Node> Nodes { get; set; }
        public int K { get; set; }

        public NodeList()
        {
            MinAreas = MinRooms = 100000;
            MaxAreas = MaxRooms = 0;
        }

    }

এখানে দেখা যাচ্ছে MinAreas, MaxAreas এবং MinRooms, MaxRooms নামের কয়েকটি প্রোপার্টি ডিফাইন করা। এগুলো আরো সহজেই করা যায়। কিন্তু কাজের এবং বোঝার সুবিধার্থে আলাদা করে লেখা। যে দুটি প্রোপার্টি জরুরী তা হচ্ছে Nodes এবং K . Nodes হচ্ছে আপনার ম্যাশিনের শেখা সমগ্র নোড গুলো (উপরের বাসার লিস্ট) এবং K হচ্ছে কতজন প্রতিবেশী নোড কে আমরা বিবেচনায় আনবো সেটির সংখ্যা। আপনি চাইলে Nodes কালেকশনটি কনস্ট্রাকটর ডিপেন্ডেন্সি তে ঢুকিয়ে দিতে পারেন। কিন্তু আমি আগেই বলেছি, এই পুরো লেখার উদ্দেশ্য বোঝানো, তাই কোডের এই দুরবস্থা। 😛
আসুন আর একটু আগানো যাক। এখন আমাদের Mystery Point থেকে সকল পয়েন্ট এর দূরত্ব বের করার কথা। কিন্তু তার আগে কিছু কথা বলা প্রয়োজন।

নরমালাইজেশন

একটু ভালো করে দেখুন, আমাদের দেয়া স্যাম্পল ডাটাতে রুম সংখ্যা ১ থেকে ১০ এর মধ্যে এবং রুম সাইজ ২৫০ তে ১৭০০ এর মধ্যে। তার মানে আমাদের x অক্ষ বরাবর বিন্দুগুলোর দূরত্ব Y অক্ষ বরাবর বিন্দুগুলোর দূরত্ব হতে গড়ে কম হবে। এটিতে যেটা হতে পারে, একটি বাসা ছকে তার সর্ব্বোচ্চ কাছাকাছি বিন্দু হতে অপেক্ষাকৃত দূরে সরে যেতে পারে এবং ভুল বিন্দুর কাছে X অক্ষ বরাবর কাছে চলে আসতে পারে। ফলে আপনার অ্যালগরিদম এর ফলাফল ক্ষতিগ্রস্ত হতে পারে। আসুন সব ভ্যালু গুলোকে আমরা ০ হতে ১ এর মধ্যে নিয়ে আসি। সহজ বাংলায় আমরা আমাদের গ্রাফটিকে বর্গাকার করে নিচ্ছি যাতে X অক্ষ এবং Y অক্ষ এর গুরুত্ব সমান থাকে। আপনি যদি চান আপনার ক্ল্যাসিফিকেশনে রুম সংখ্যা বেশি গুরুত্ব পাবে। তাহলে আপনি যেকোন অক্ষের দুরত্ব কমিয়ে আনতে পারেন। একে Weighting বলে। সেটা না হয় পরে।

দুই অক্ষের সকল ভ্যালু ০ হতে ১ এর মধ্যে আনতে হলে দুই অক্ষের সর্ব্বোচ্চ এবং সর্বনিম্ন মান আমাদের জানতে হবে এবং সেটাকে অক্ষভেদে মানের পার্থক্য দিয়ে ভাগ দিতে হবে। আসুন কোড দেখে বুঝে নেই:

        private void CalculateRanges()
        {
            if(Nodes!=null && Nodes.Count>0)
            {

                foreach (var node in Nodes)
                {
                    if (node.Rooms < MinRooms)
                        MinRooms = node.Rooms;
                    if (node.Rooms > MaxRooms)
                        MaxRooms = node.Rooms;

                    if (node.Area < MinAreas)
                        MinAreas = node.Area;
                    if (node.Area > MaxAreas)
                        MaxAreas = node.Area;
                }
            }
        }

CalculateRanges() মেথডটি NodeList ক্লাসে যোগ করা। দেখেই বোঝা যাচ্ছে খুবই আনাড়ি কোড কিন্তু বোঝার জন্যে এটি অসাধারণ। খেয়াল করে দেখুন CalculateRanges() শুধুমাত্র room এবং area (আমাদের x এবং y অক্ষ) এর সর্ব্বোচ্চ এবং সর্বনিম্ন মান খুঁজে বের করছে। আর কিছু নয়। এখন যেহেতু আমাদের হাতে দুই অক্ষের সর্ব্বোচ্চ এবং সর্বিনম্ন মান আছে সেহেতু আমরা মূল অ্যালগরিদমে প্রবেশ করতে পারি।

public void DetermineUnknown()
        {
            //start the calculation of range;
            this.CalculateRanges();

            foreach (var node in Nodes)
            {
                if(node.Type == NodeType.unknown)
                {
                    node.Neighbours = new ObservableCollection<Node>();
                    foreach (var NNode in Nodes)
                    {
                        if (NNode.Type == NodeType.unknown)
                            continue;
                        node.Neighbours.Add(NNode);

                    }

                    //Measure Distance Now

                    node.MeasureDistances(MaxRooms - MinRooms, MaxAreas - MinAreas);

                    //Sort it out
                    node.Neighbours = new ObservableCollection<Node>(node.Neighbours.OrderBy(x => x.Distance).ToList());

                    //Guess the type
                    node.GuessType(this.K);
                }
            }
        }

এক বস্তা জিনিস এক সাথে লিখে ফেললাম, এই তো? আসুন আস্তে আস্তে আগাই। আমরা CalculateRanges() আগেই দেখেছি। শুরুতেই লুপে ঘুরছে আমাদের সব স্যাম্পল ডাটা (যেখানে আমাদের Classification না জানা Mystery Points গুলো, মানে যে বাসাগুলো কোন প্রকারের আমরা জানিনা সেগুলোও আছে এবং অবশ্যই স্যাম্পল ডাটা সেট ও আছে)। দেখা হয়েছে NodeType unknown কিনা, হলে সেটিই সেই বাসা যেটির প্রকার আমরা জানিনা, তার মানে সেটি Mystery Point গুলোর একটি। আসুন সেটিকে classify এর ব্যবস্থা করি। শুরুতে ই লাগবে সকল প্রতিবেশী সকল নোড হতে দূরত্ব্। না হলে কাছের গুলো বের করবেন কিভাবে। সেজন্যে MeasureDistances() ব্যবহার করা। দেখে আসি মেথডটি দেখতে কেমন হতে পারে। খেয়াল করে দেখুন, আরগুমেন্ট দুটি হচ্ছে Rooms এবং Areas এর মানের পার্থক্য। এটি আমাদের Normalize করতে সাহায্য করবে।

        internal void MeasureDistances(int RoomRange, int AreaRange)
        {
            foreach (var neighbour in Neighbours)
            {
                double delta_rooms = neighbour.Rooms - this.Rooms;
                delta_rooms = delta_rooms / (double)RoomRange;

                double delta_area = neighbour.Area - this.Area;
                delta_area = delta_area / (double)AreaRange;

                neighbour.Distance = Math.Sqrt(delta_rooms * delta_rooms + delta_area * delta_area);

            }
        }

এখানে দূরত্ব বের করার আগে Normalization করো হয়েছে। তার মানে আমরা প্রতিটি প্রতিবেশীর Room এবং Area এর মানের পার্থক্য কে Room এবং Area এর সর্বোচ্চ এবং সর্বনিম্ন মানের পার্থক্য দিয়ে ভাগ দিয়ে এই মানগুলোকে ০ হতে ১ এর মধ্যে নিয়ে আসছি। এর পর আমরা পিথাগোরাসীয় দূরত্ব বের করছি। একটি জিনিস লক্ষ্য করে দেখুন। আমাদের ফিচার সংখ্যা দুইটি হওয়ায় আমরা দ্বিমাত্রিক কার্তেসীয় স্থানাংক ব্যবস্থায় আমরা বিন্দুগুলোকে X অক্ষ এবং Y অক্ষে আলাদা করে লিখেছি। এইজন্য দ্বিমাত্রিক দুটি বিন্দুর দূরত্ব বের করার সূত্র হচ্ছে Math.Sqrt(x * x + y * y)
যদি আপনার ফিচার তিনটি হতো তাহলে ছকটি ত্রিমাত্রিক স্থানাংক ব্যবস্থায় চলে আসতো। তখন দুই বিন্দুর দূরত্ব হতো Math.Sqrt(x * x + y * y+ z*z)
এইভাবে n সংখ্যক ফিচারের জন্য n মাত্রিক স্থানাংক ব্যবস্থায় দুই বিন্দুর দূরত্ব হতো Math.Sqrt(x * x + y * y+ z*z+ …..+ n*n)
আপনি চাইলে একটি n মাত্রিক স্থানাংক ব্যবস্থাকে কমিয়ে এনে দ্বিমাত্রিক ব্যবস্থায় প্রোজেক্ট করতে পারেন। তবে সেগুলো অন্য কোন দিন। যেটা আমি এখানে বোঝাতে চেয়েছিলাম সেটি হচ্ছে এটিই KNN এর ক্ষমতার পরিচায়ক, আপনার ফিচার সংখ্যা যাই হোক না কেন, সেটি আরামসে কাজ করতে পারে। তবে মনে রাখবেন বেশি ফিচার মানেই ভালো ক্ল্যাসিফিকেশন তা নয়। তাতে সেই generalization সংক্রান্ত জটিলতায় পড়তে পারেন।

তো MeasureDistances() এর পরে আমাদের কাজ হচ্ছে দূরত্বের ভিত্তিতে প্রতিটি নোডের প্রতিবেশীর লিস্ট কে সর্ট করা। কারণ আমরা k সংখ্যক কাছের প্রতিবেশী নিয়ে আগ্রহী। এর পরেই চলে আসে Mystery Point টি যেটির প্রকার আমরা জানিনা (যে বাসাটি ফ্ল্যাট, অ্যাপার্টমেন্ট না হাউজ আমরা জানিনা) সেটির প্রকার খুঁজে বের করা। সেই কাজটি করে GuessType()

internal void GuessType(int k)
        {
            int[] TypeVotes = new int[4]; //There are three types;

            var EligibleNeighbours = this.Neighbours.Take(k).ToList();

            foreach(var eligibleNode in EligibleNeighbours)
            {
                TypeVotes[(int)eligibleNode.Type] ++;

            }

            NodeType GuessedType = (NodeType)TypeVotes.Max();

            MessageBox.Show("Guessed type for node is " + GuessedType.ToString());

            this.Type = GuessedType;
        }

আমরা চলে এসেছি প্রায় শেষে, দেখুন এটি কোন নোডের প্রতিবেশী হতে খুঁজে বের করে সর্বোচ্চ কাছের k সংখ্যক প্রতিবেশী কে । এবং এদের থেকে সর্বোচ্চ সংখ্যক প্রতিবেশী যে প্রকারের আপনার Mystery Point টি ও সেই প্রকারের বলে ঘোষনা করে। মানে এখানেই আপনি জেনে যাবেন আপনার বাসাটি কোন প্রকারের।

উইন্ডোজ ফোনে উদাহরণ:

‌উইন্ডোজ ফোনে আমি একটি ছোট্ট MVVM অ্যাপ বানিয়ে পরীক্ষা করেছি অ্যালগরিদম টি। পুরো কোড শেষে দেয়া আছে। তাই MainviewModel এর কিছু অংশ আমি তুলে দিচ্ছি:

        public MainViewModel()
        {

            TestKnnCommand = new RelayCommand(TestKnnAction);
            LoadSamples();
            AddASample();
        }

        private void TestKnnAction()
        {
            NodeCollection.DetermineUnknown();
        }

        private void LoadSamples()
        {

            using(StreamReader reader= new StreamReader("SampleData.txt"))
            {
                var data = reader.ReadToEnd();
                List<Node> datArray = JsonConvert.DeserializeObject<List<Node>>(data, new StringToEnumConverter());
                var _sampleCollection = new ObservableCollection<Node>(datArray);

                NodeCollection = new NodeList();
                NodeCollection.K = 3;
                NodeCollection.Nodes = _sampleCollection;

            }

        }

        private void AddASample()
        {
            Node newNode = new Node() { Area = 500, Rooms = 2, Type = NodeType.unknown };
            NodeCollection.Nodes.Add(newNode);
        }

আমি শুধু শুরুতে লোড করে নিয়েছি আমার স্যাম্পল ডাটা গুলো। এরপর যোগ করে নিয়েছি একটি অজানা Mystery Point , মানে এমন একটি বাসা যেটি কোন প্রকারের আমি জানিনা। K এখানে ৩, তার অর্থ হচ্ছে আমি ৩ টি কাছের প্রতিবেশী ব্যবহার করবো classification এর জন্যে।
TestKnnAction() একটি action যেটি একটি বাটন হতে command এর সাহায্যে invoke করা হয়। এবং এটি অজানা পয়েন্ট টির ক্ল্যাসিফিকেশন বের করার জন্য DetermineUnknown() ব্যবহার করে। আপনি চাইলে একাধিক স্যাম্পল যোগ করে অ্যালগরিদম টি চালিয়ে দেখতে পারেন।

জেনে রাখা ভালো:

অন্য সকল ক্লাসিফিকেশন অ্যালগরিদম এর মতোই এটিতেও সমস্যা আছে। আপনার ডাটা সেট যদি পৃথক করার যোগ্য (Separable) হয় তবেই এটি বেশ ভালো কাজ করে। আর যদি তা না হয় আপনি এমন একটি ছক পাবেন যেটায় বিন্দু গুলো সব জায়গায় ছড়িয়ে আছে এবং ফলশ্রুতিতে আপনি ভালো ফলাফল পাবেন না। বরং আপনি যদি ছকে দেখেন বিন্দুগুলো cluster বা গুচ্ছে গুচ্ছে বিভক্ত তাহলে বুঝবেন এটি Separable বা পৃথক করার যোগ্য। আরেকটি জিনিস, নোডসংখ্যা বাড়লে আপনার ক্যালকুলেশন টাইম ও বাড়বে। তাই আপনি চাইলে Pruning করতে পারেন। যেমন যে বাসার Room সংখ্যা ২ তার জন্যে যে সকল বাসা যাদের room সংখ্যা ৬ এর অধিক তাদের সাথে দূরত্ব বের করা অর্থহীন।

আশা করি সবার ভালো লাগবে। অ্যাপ এর দুটি স্ক্রিনশট তুলে দিলাম।

Initial KNN Graph

classification result

কোডটুকু পাওয়া যাবে এখানে। যদিও আপনার Telerik Rad Controls for Windows Phone 8 এর লাইসেন্স থাকা লাগবে এটি বিল্ড করার জন্যে। তবুও দিয়ে দিলাম : http://1drv.ms/1DOTVu8