Constructing Decision Tree using WEKA

Introduction

Decision tree learning is a method for assessing the most likely outcome value by taking into account the known values of the stored data instances. This learning method is among the most popular of inductive inference algorithms and has been successfully applied in broad range of tasks such as assessing the credit risk of applicants and improving loyality of regular customers.

Information, Entropy and Information Gain

There are several software tools already available which implement various algorithms for constructing decision trees which optimally fit the input dataset. Nevertheless it is useful to clarify the underlying principle.

Information

First let's briefly discuss the concept of information. In simplified form we could say that the information is a measure of uncertainty or surprise; the more we are surprised about the news the bigger is the information. If there was a newspaper which pubblished a news about the morning sunrise certainly none of the readers would be interested in such story because it doesn't hold any information - the sunrise is a fact and we know it will happen tomorrow again. On the other hand if a story in a newspaper is about something noone expected it's a big news. An example is Michael Jackson's death. It happened during the time of one of the worst recessions which affected the whole world but according to the statistics the news about Michael Jackson were far more interesting than the economic facts of the time.

Entropy

In General entropy is the measure of the uncertainty associated with random variable. In case of stored instances entropy is the measure of the uncertainty associated with the selected attribute.

where is the probability mass function of outcome .

Information Gain

Information gain is the expected reduction in entropy caused by partitioning the examples according to the attribute. In machine learning this concept can be used to define a preferred sequence of attributes to investigate to most rapidly narrow down the state of the selected attribute. Such a sequence (which depends on the outcome of the investigation of previous attributes at each stage) forms a decision tree. Usually an attribute with high information gain should be preferred to other attributes.

An Example

The process of decision tree construction is described by the following example: There are 14 instances stored in the database described with 6 attributes: day, outlook, temperature, humidity, wind and playTennis. Each instance describes the facts of the day and the action of the observed person (played or not played tennis). Based on the given record we can assess which factors affected the person's decision about playing tennis.

For the root element an attribute with the highest entropy is selected. In the case of this example it is the outlook because it is the most uncertain parameter.
After the root parameter is selected the information gain for every possible combination of pair is calculated and then the branches are selected upon the information gain value; the higher is the information gain the more reliable the branch is.

Entropy(S) is the entropy of classificator PlayTennis - there are 14 instances stored in the dataset from which a person decides do play tennis 9 times (9+) and not to play 5 times (5-).

The above example shows the calculation of the information gain value of classificator Wind: There are 8 instances of value Weak. In case of weak wind a person decides to play tennis 6 times and not to play 2 times [6+, 2-]. In case of strong wind (6 instances) the user decides to play 3 times and not to play 3 times as well. Considering the given instances the calculated value of information gain of attribute wind is 0.48.

Information gain values of all attributes are calculated in the same way and the results are the following:

Gain(S, Outlook) = 0.246
Gain(S, Humidity) = 0.151
Gain(S, Wind) = 0.048
Gain(S, Temperature) = 0.029

Using WEKA

The example is taken from the Book Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems)

The .arff file

One of possible options for importing the record in WEKA tool is writing records in .arff file format. In this example the file looks like the following:

@relation PlayTennis  

@attribute day numeric
@attribute outlook {Sunny, Overcast, Rain} 
@attribute temperature {Hot, Mild, Cool} 
@attribute humidity {High, Normal}
@attribute wind {Weak, Strong} 
@attribute playTennis {Yes, No}  

@data  
1,Sunny,Hot,High,Weak,No,? 
2,Sunny,Hot,High,Strong,No,?
3,Overcast,Hot,High,Weak,Yes,? 
4,Rain,Mild,High,Weak,Yes,? 
5,Rain,Cool,Normal,Weak,Yes,? 
6,Rain,Cool,Normal,Strong,No,?
7,Overcast,Cool,Normal,Strong,Yes,?
8,Sunny,Mild,High,Weak,No,?
9,Sunny,Cool,Normal,Weak,Yes,?
10,Rain,Mild,Normal,Weak,Yes,? 
11,Sunny,Mild,Normal,Strong,Yes,? 
12,Overcast,Mild,High,Strong,Yes,? 
13,Overcast,Hot,Normal,Weak,Yes,? 
14,Rain,Mild,High,Strong,No,?

The file can then be imported using WEKA explorer. When the above file is imported the interface looks like the following:

Figure: Available attributes (left) and graphical representation (right) from the file data

after the data is imported there is a set of classification methods available under the classification tab. In this case the c4.5 algorithm has been chosen which is entitled as j48 in Java and can be selected by clicking the button choose and select trees->j48.

Figure: after running Start The decision tree is created in this case using c4.5 algorithm

The tree is then created by selecting start and can be displayed by selecting the output from the result list with the right-mouse button choosing the option "Visualize Tree".

Figure: The decision tree constructed by using the implemented C4.5 algorithm

The algorithm implemented in WEKA constructs the tree which is consistent with the information gain values calculated above: the attribute Outlook has the highest information gain thus it is the root attribute. Attributes Humidity and Wind have lower information gain than Outlook and higher than Temperature and thus are placed below Outlook. The information gain of a specific branch can be calculated the same way as the example above. For example if we were interested what is the information gain of branch (Outlook, Temperature) the attributes Outlook and Temperature should be placed in the equation for calculating the information gain.

References

Data Mining and KnowledgeDiscovery; Prof. Dr. Nada Lavrač

Data Mining: Practical Machine Learning Tools and Techniques, Second Edition; Ian H. Witten, Eibe Frank

LDPC Block Code Simulator: GUI Preview

In the past days I've created a LDPC Block Code Simulator in Matlab. It is possible to enter the parity matrix H, the information sequence D which is encoded into codeword C and then add Gaussian Noise of a chosen variance which simulates the transmission channel charcteristics.

The simulator then calculates the original codeword and enables user to switch between the steps of the iterative decoding process. Each step displays the current message values that are passed between symbol and parity nodes and the next step operation.

Below are the screenshots of three steps. In this example H is 4 x 8 parity-check matrix ([1 0 1 0 1 0 0 0; 0 0 0 1 0 1 0 0; 1 0 0 1 0 0 1 0; 0 1 1 0 0 0 0 1]). The information sequence D ([1 0 1 1]) is encoded into codeword C (1 0 1 1 0 1 0 1). The original unipolar codeword is transformed to bipolar code (1 is transformed to -1 and 0 is transformed to 1) and the noise of variance 0.5 is added to the transformed code which results Y (-1.0371 0.12971 -1.1976 -1.808 1.3784 -1.3998 1.0451 -1.2452), the simulated received sequence. After 5 steps the algorithm determines the codeword C' (1 0 1 1 0 1 0 1) which is equal to the original codeword.

Communication Between WCF Service and Android Client

Overview of REST in WCF

Windows Communication Foundation (WCF), part of the .NET Framework, provides the first unified programming model for rapidly building service-oriented applications. It enables the development of secure, reliable, transacted services that interoperate with current Microsoft investments and non-Microsoft platforms.

With the .NET Framework 3.5 release, WCF added support for building REST style services. REST, an architectural style for building distributed hypermedia driven applications, involves building resource-oriented services by defining resources that implement uniform interfaces using standard HTTP verbs (GET, POST, PUT, and DELETE), and that can be located/identified by a URI.

REST support within WCF was enhanced with the release of .NET Framework 3.5 SP1 to add make REST development easier and to support the ADO.NET Entity Framework entities in WCF contracts. Improvements were made around UriTemplate flexibility and the Visual Studio tooling to increase developer productivity.

Code example

A good tutorial on how to create RESTful Service using Visual Studio can be found here.

First we need to define the structure (class) which will be used for data exchange between server and client. In this case I created a base class named Response and extended classes named ActivityStatusResponse and ConnectionStatusResponse:

public class Response
{
private bool successful;
private string comment;

public bool Successful
{
get
{
  return successful;
}
set
{
  successful = value;
}
}

public string Comment
{
get
{
  return comment;
}
set
{
  comment = value;
}
}
}

public class ActivityStatusResponse : Response
{
private string activity;

public string Activity
{
get
{
  return activity;
}
set
{
  activity = value;
}
}
}

Next we need to define the methods, message formats and URI templates in the interface:

[OperationContract]
[WebGet(ResponseFormat = WebMessageFormat.Json, UriTemplate = "/{strSessionString}/activityStatus")]
ActivityStatusResponse GetActivityStatus(string strSessionString);

[OperationContract]
[WebGet(ResponseFormat = WebMessageFormat.Json,
UriTemplate = "/{strSessionString}/time={time}&lat={latitude}&long={longitude}")]
Response StoreLocation(string strSessionString, string time, string latitude, string longitude);

WebMessageFormat parameter defines the data exchange format. In this example JSON format is used.

UriTemplate parameter defines the URI template.

The parameters within curly braces represent variable values. Everything else in the URI (not enclosed within curly braces) is considered a static part of the URI.

After the definition we have to implement the methods. The following code shows the implementation of StoreAcceleration method:

public Response StoreAcceleration(string strSessionString, string strMeasurementTime, string strAccelerationX, string strAccelerationY, string strAccelerationZ)
      {
SQLWorks sqlWorks = new SQLWorks();
Response response = new Response();
try
{
  string strTime = strMeasurementTime.Replace("_", " ");
  DateTime measurementTime = DateTime.ParseExact(strTime, "yyyy-MM-dd HH:mm:ss:fff", null);
  double accelerationX = Convert.ToDouble(strAccelerationX.Replace(".", ","));
  double accelerationY = Convert.ToDouble(strAccelerationY.Replace(".", ","));
  double accelerationZ = Convert.ToDouble(strAccelerationZ.Replace(".", ","));

  sqlWorks.StoreAcceleration(strSessionString, measurementTime, accelerationX, accelerationY, accelerationZ);

  response.Successful = true;
  response.Comment = "Stored!";
}
catch(Exception ex)
{
  string sDummy = ex.ToString();
  response.Comment = "an error occured!";
  response.Successful = false;
}

return response;
}

The service Endpoint and other properties are defined in .config file:

<configuration>
<system.web>
<compilation debug="true">
</compilation>
<system.servicemodel>
<bindings>
<webhttpbinding>
<binding name="DefaultBinding">
</binding>
</webhttpbinding>
<behaviors>
<endpointbehaviors>
<behavior name="RESTFriendly">
<webhttp>
</webhttp>
<behavior name="RESTServer.JsonServiceAspNetAjaxBehavior">
<enablewebscript>
</enablewebscript>
</behavior>
<servicebehaviors>
<behavior name="RESTFriendly">
<servicemetadata httpgetenabled="true">
<servicedebug includeexceptiondetailinfaults="false">
</servicedebug>
</servicemetadata>
</behavior>
<services>
<service name="RESTServer.GaitLinkService">
<endpoint address="" behaviorconfiguration="RESTFriendly" binding="webHttpBinding" bindingconfiguration="DefaultBinding" contract="RESTServer.IGaitLinkService">
<identity>
<dns value="localhost">
</dns>
</identity>
</endpoint>
</service>
<servicehostingenvironment aspnetcompatibilityenabled="true">
</servicehostingenvironment>
</services></servicebehaviors></behavior></endpointbehaviors></behaviors></bindings></system.servicemodel></system.web></configuration>

At this point everything is ready to host the service in the windows application:

public void StartRestService()
{
try
{
   WebHttpBinding binding = new WebHttpBinding();
   RESTServiceHost = new ServiceHost(typeof(GaitLinkService), new Uri("http://localhost:8000/GaitLink"));
   RESTServiceHost.AddServiceEndpoint(typeof(IGaitLinkService), binding, "GaitLink");
   RESTServiceHost.Open();
}
catch(Exception ex)
{
   string sDummy = ex.ToString();
   //TODO: notify user about the error!
            }
}

Client application

On client side there is a service called CommunicationService and additional class RestClient. Function arguments are sent to the server by generating the url address which has to be the same format as the template specified in the service interface on the server side.

Class RestClient.java:

package com.client.gaitlink;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

import org.apache.http.HttpEntity;
import org.apache.http.HttpResponse;
import org.apache.http.client.ClientProtocolException;
import org.apache.http.client.HttpClient;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.impl.client.DefaultHttpClient;
import org.json.JSONArray;
import org.json.JSONException;
import org.json.JSONObject;

import android.util.Log;

public class RestClient {

private static String loginParameters;
private static String accelerationParameters;
private static String activityRequestParameters;
private static String locationParameters;
private static String serviceAddress = "http://testserver:8000/GaitLink/";

private static String convertStreamToString(InputStream is) {
BufferedReader reader = new BufferedReader(new InputStreamReader(is));
StringBuilder sb = new StringBuilder();

String line = null;
try {
while ((line = reader.readLine()) != null) {
  sb.append(line + "\n");
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
  is.close();
} catch (IOException e) {
  e.printStackTrace();
}
}
return sb.toString();
}

public static void connect(String url) {

HttpClient httpclient = new DefaultHttpClient();

HttpGet httpget = new HttpGet(url);

//HttpPost httppost = new HttpPost(url);

HttpResponse response;
try {

response = httpclient.execute(httpget);

Log.i("REST:Response Status line", response.getStatusLine().toString());

HttpEntity entity = response.getEntity();

if (entity != null) {

  InputStream instream = entity.getContent();
  String result = convertStreamToString(instream);
  Log.i("REST: result", result);

  JSONObject json = new JSONObject(result);
  Log.i("REST", "<jsonobject>\n" + json.toString()
          + "\n</jsonobject>");

  // Parsing
                JSONArray nameArray = json.names();
  JSONArray valArray = json.toJSONArray(nameArray);
  for (int i = 0; i < valArray.length(); i++) {
      Log
              .i("REST", "<jsonname" + i + ">\n"
                      + nameArray.getString(i) + "\n</jsonname"
                      + i + ">\n" + "<jsonvalue" + i + ">\n"
                      + valArray.getString(i) + "\n</jsonvalue"
                      + i + ">");
  }

  json.put("sample key", "sample value");
  Log.i("REST", "<jsonobject>\n" + json.toString()
          + "\n</jsonobject>");


  instream.close();
}

} catch (ClientProtocolException e) {
// TODO Auto-generated catch block
            e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
            e.printStackTrace();
} catch (JSONException e) {
// TODO Auto-generated catch block
            e.printStackTrace();
}
}

public class Response
{
public boolean isSuccessful() {
return successful;
}

public void setSuccessful(boolean successful) {
this.successful = successful;
}

public String getComment() {
return comment;
}

public void setComment(String comment) {
this.comment = comment;
}

private boolean successful;
private String comment;

public Response()
{
this(false, null);
}

public Response(boolean successful, String comment)
{
this.successful = successful;
this.comment = comment;
}
}

public class LoginResponse extends Response
{
private String strSessionString;

public LoginResponse()
{
this(false, null, "LoginFailed");
}

public LoginResponse(boolean successful, String strSessionString, String comment)
{
super(successful, comment);
this.strSessionString = strSessionString;
}

public String getStrSessionString() {
return strSessionString;
}

public void setStrSessionString(String strSessionString) {
this.strSessionString = strSessionString;
}
}

public class ActivityStatusResponse extends Response
{
private String activity;

public String getActivity() {
return activity;
}

public void setActivity(String activity) {
this.activity = activity;
}

public ActivityStatusResponse(boolean successfull, String activity, String comment)
{
super(successfull, comment);
this.activity = activity;
}

public ActivityStatusResponse()
{
this(false, null, "activity request failed");
}
}

private static void SetLoginParameters(String username, String password)
{
loginParameters = "Login?username=" + username + "&password=" + password;
}

public LoginResponse Login(String username, String password)
{
SetLoginParameters(username, password);

HttpClient httpclient = new DefaultHttpClient();
HttpGet httpget = new HttpGet(serviceAddress + loginParameters);

HttpResponse response;

LoginResponse loginResponse = null;

try
{
response = httpclient.execute(httpget);

HttpEntity entity = response.getEntity();

if(entity != null)
{
  InputStream instream = entity.getContent();
  String result = convertStreamToString(instream);
  JSONObject json = new JSONObject(result);

  // Parsing
                JSONArray nameArray = json.names();
  JSONArray valArray = json.toJSONArray(nameArray);

  loginResponse = new LoginResponse(valArray.getBoolean(1), valArray.getString(0), valArray.getString(2));


  instream.close();
}

}
catch(Exception e)
{
loginResponse = new LoginResponse();
String sDummy = e.toString();
}
return loginResponse;
}

public Response SendAccelerations(String sSession, String measurementTime, double ax, double ay, double az)
{
setAccelerationParameters(sSession, measurementTime, ax, ay, az);

HttpClient httpclient = new DefaultHttpClient();
HttpGet httpget = new HttpGet(serviceAddress + accelerationParameters);

HttpResponse response;

Response accelerationResponse = null;

try
{
response = httpclient.execute(httpget);

HttpEntity entity = response.getEntity();

if(entity != null)
{
  InputStream instream = entity.getContent();
  String result = convertStreamToString(instream);
  JSONObject json = new JSONObject(result);

  // Parsing
                JSONArray nameArray = json.names();
  JSONArray valArray = json.toJSONArray(nameArray);

  accelerationResponse = new Response(valArray.getBoolean(0), valArray.getString(1));


  instream.close();
}

}
catch(Exception e)
{
accelerationResponse = new Response();
String sDummy = e.toString();
}
return accelerationResponse;
}

private static void setAccelerationParameters(String sSession, String measurementTime, double ax, double ay, double az)
{
accelerationParameters = sSession + "/measurementTime=" + measurementTime + "&accelerationX=" + ax + "&accelerationY=" + ay + "&accelerationZ=" + az;
accelerationParameters = accelerationParameters.replaceAll(" ", "_");
}

public Response SendLocation(String sSession, String locationTime, double latitude, double longitude)
{
setLocationParameters(sSession, locationTime, latitude, longitude);

HttpClient httpclient = new DefaultHttpClient();
HttpGet httpget = new HttpGet(serviceAddress + locationParameters);

HttpResponse response;

Response locationResponse = null;

try
{
response = httpclient.execute(httpget);

HttpEntity entity = response.getEntity();

if(entity != null)
{
  InputStream instream = entity.getContent();
  String result = convertStreamToString(instream);
  JSONObject json = new JSONObject(result);

  // Parsing
                JSONArray nameArray = json.names();
  JSONArray valArray = json.toJSONArray(nameArray);

  locationResponse = new Response(valArray.getBoolean(0), valArray.getString(1));


  instream.close();
}

}
catch(Exception e)
{
locationResponse = new Response();
String sDummy = e.toString();
}
return locationResponse;
}

private static void setLocationParameters(String sSession, String locationTime, double latitude, double longitude)
{
///{strSessionString}/time={time}&lat={latitude}&long={longitude}
        locationParameters = sSession + "/time=" + locationTime + "&lat=" + latitude + "&long=" + longitude;
locationParameters = locationParameters.replaceAll(" ", "_");
}

public ActivityStatusResponse GetActivity(String sSession)
{
setActivityRequestParameters(sSession);

HttpClient httpclient = new DefaultHttpClient();
HttpGet httpget = new HttpGet(serviceAddress + activityRequestParameters);

HttpResponse response;

ActivityStatusResponse activityStatusResponse = null;

try
{
response = httpclient.execute(httpget);

HttpEntity entity = response.getEntity();

if(entity != null)
{
  InputStream instream = entity.getContent();
  String result = convertStreamToString(instream);
  JSONObject json = new JSONObject(result);

  // Parsing
                JSONArray nameArray = json.names();
  JSONArray valArray = json.toJSONArray(nameArray);

  activityStatusResponse = new ActivityStatusResponse(valArray.getBoolean(0), valArray.getString(1), valArray.getString(2));


  instream.close();
}

}
catch(Exception e)
{
activityStatusResponse = new ActivityStatusResponse();
String sDummy = e.toString();
}
return activityStatusResponse;
}

private static void setActivityRequestParameters(String sSession)
{
activityRequestParameters = "/" + sSession + "/activityStatus";
}
}

RestClient methods are called from CommunicationService class. The following example shows the method which retrieves the activity status:

private void requestActivity()
{
try
{
if(strSessionString != null)
{
  ActivityStatusResponse response = restClient.GetActivity(strSessionString);
  connectionAvailable = response.isSuccessful();
  strActivity = response.getActivity();
  if(strActivity != null && strActivity != "")
  {
      announceActivityStatus();
  }

}
}
catch(Exception e)
{
connectionAvailable = false;
}
}

The example above is just a brief overview of practical RESTful service realization using WCF and data exchange with Android client. More detailed explanations of each segment could be found at the given addresses.

References

A Guide to Designing and Building RESTful Web Services with WCF 3.5
Windows Communication Foundation Architecture
What Is Windows Communication Foundation?