<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Hafidz Jazuli on Medium]]></title>
        <description><![CDATA[Stories by Hafidz Jazuli on Medium]]></description>
        <link>https://medium.com/@bladefidz?source=rss-e25dd3616749------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*QvO26GjkSdn8H5p3.</url>
            <title>Stories by Hafidz Jazuli on Medium</title>
            <link>https://medium.com/@bladefidz?source=rss-e25dd3616749------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 17:57:00 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@bladefidz/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Using Decision Tree Method for Car Selection Problem]]></title>
            <link>https://medium.com/machine-learning-guy/using-decision-tree-method-for-car-selection-problem-5272675451f9?source=rss-e25dd3616749------2</link>
            <guid isPermaLink="false">https://medium.com/p/5272675451f9</guid>
            <category><![CDATA[c50-algorithm]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[decision-tree]]></category>
            <dc:creator><![CDATA[Hafidz Jazuli]]></dc:creator>
            <pubDate>Fri, 16 Mar 2018 09:49:33 GMT</pubDate>
            <atom:updated>2018-03-16T21:37:27.947Z</atom:updated>
            <content:encoded><![CDATA[<p>In this tutorial, I will show you how to use C5.0 algorithm in R. If you just came from nowhere, it is good idea to read <a href="https://medium.com/machine-learning-guy/an-introduction-to-decision-tree-learning-id3-algorithm-54c74eb2ad55">my previous article about Decision Tree</a> before go ahead with this tutorial. I designed this tutorial within practical statistic approach, so you can think the practical implementation after learned this tutorial. But in general, everybody (at least at high school) can interpreted this tutorial without any difficulties.</p><p>In order to build a high quality tutorial, I was crafted this tutorial based on proved <a href="http://kt.ijs.si/MarkoBohanec/pub/Avignon88.pdf">research paper</a> and <a href="http://archive.ics.uci.edu/ml/datasets/Car+Evaluation">high quality data set</a>. If you want to get more insight from this tutorial, then it is good idea to complete all prerequisites below before read this tutorial.</p><h4>Prerequisites</h4><ol><li>Understand the <a href="https://medium.com/machine-learning-guy/an-introduction-to-decision-tree-learning-id3-algorithm-54c74eb2ad55">basic concept of Decision Tree</a>.</li><li>In this tutorial, I used <strong>C5.0 algorithm</strong> which is latest improved version of ID3 algorithm. If you are not familiar with this algorithm, its good idea to read resource [4] or go to <a href="http://saiconference.com/Downloads/SpecialIssueNo10/Paper_3-A_comparative_study_of_decision_tree_ID3_and_C4.5.pdf">this link</a>.</li><li>Skim <a href="http://kt.ijs.si/MarkoBohanec/pub/Avignon88.pdf">this</a> [1] and <a href="https://www.researchgate.net/profile/Ivan_Bratko/publication/2820632_Machine_Learning_by_Function_Decomposition/links/0fcfd508bb1f4468b3000000/Machine-Learning-by-Function-Decomposition.pdf">this</a> [2] research paper because this tutorial based on them. They are seriously <em>easy-to-read</em> papers, but if you are hate math, just skip all the math, I will provides you <em>easy-to-follow</em> problem solving art in this tutorial (as for large audiences, we look math as art of problem solving or tool for engineering). For information, the first paper is taking decision theory approach, while second paper is taking linear programming approach.</li><li>Go to this <a href="http://archive.ics.uci.edu/ml/datasets/Car+Evaluation">UCI data set repository</a> to get more insight about data set which I used in this tutorial. By understand high quality post-processed data set, you can get more insight of how to build your own data set in the future.</li></ol><p>Yes, that’s all. <strong>No prior programming experience required for this easy tutorial</strong>. Enjoy the tutorial!</p><h3>Get Know The Data Set</h3><p>This dataset contains 1728 data about car’s criteria. All criteria has been labeled, so we used <a href="https://en.wikipedia.org/wiki/Unsupervised_learning">unsupervised learning method</a> to infer from the data. The data contains categorical values, so we conduct <a href="https://en.wikipedia.org/wiki/Statistical_classification">Classification task </a>to acquire knowledge from the data. This data set has been used by two research papers: [1] and [2].</p><p>This data set also known as “The Car Evaluation Database” contains examples with the structural information removed. The knowledge representation of this data set illustrated in an image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/822/1*8l1EeYnPyKNGi3rtHx7mtQ.png" /><figcaption>Criteria tree</figcaption></figure><p>According to the criteria tree above, the quality of cars is measured by two main groups of criteria: price (<strong>PRICE</strong>) and technical characteristics (<strong>TECH</strong>). The price is determined by buying and maintenance price. Technical characteristic are decomposed into safety and comfort, which further depends on number of doors, size of car (measured as number of persons that fit in the car) and size of the luggage boot.</p><p>The concept structure of the data described below:</p><p><strong>CAR</strong> car acceptability<br> —<strong> PRICE</strong> overall price<br> — — <em>buying</em> buying price<br> — —<em> maint</em> price of the maintenance<br> —<strong> TECH</strong> technical characteristics<br> — —<em> COMFORT</em> comfort<br> — — —<em> doors</em> number of doors<br> — — — <em>persons</em> capacity in terms of persons to carry<br> — — —<em> lug_boot</em> the size of luggage boot<br> — — <em>safety</em> estimated safety of the car</p><p>Each attribute described below:</p><ul><li><strong>buying</strong>: v-high, high, med, low</li><li><strong>main</strong> (maintenance): v-high, high, med, low</li><li><strong>door</strong>: 2, 3, 4, 5-more</li><li><strong>persons</strong> (number of passengers fit in a car): 2, 4, more</li><li><strong>lug_boot</strong> (size of luggage capacity): small, med, high</li><li><strong>safety</strong>: low, med, high</li></ul><p>The quality of car labeled as unaccepted<strong> </strong>(<strong>unacc</strong>),<strong> </strong>accepted (<strong>acc</strong>), good (<strong>good</strong>) and very good (<strong>vgood</strong>). While class distribution of each label is given below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/1*bb60yk-HAhW-E6Yhw4mhxg.png" /><figcaption>Attribute class distributions</figcaption></figure><p>Based on the class distribution, it’s look like we have skewed data. That’s means we have right choice using classification model to infer from this data set. Although, some more advanced method such as ensemble learning can be used, in this tutorial we only focus on basic implementation of Decision Tree as for learning purpose.</p><h3>R Programming Environment</h3><p>R is popular open source statistical software which can be downloaded at <a href="https://www.r-project.org/">here</a>. The main advantage by using R is memory and storage efficiency. In my opinion from programming point of view: R is easy to use; has similar syntax with Python; and highly optimized to handling large data set. The main difference from general purpose programming language is, R provides better way to slice large list into pointer of segmented lists.</p><h3><strong>Production Method Used in This Tutorial</strong></h3><p>There are two production method used in this tutorial: implementation and evaluation method. The step-by-step implementation method described below:</p><ol><li>Analyzing attribute of each criteria.</li><li>Apply randomized splitting data set into training set and test set.</li><li>Apply C50 algorithm on training set.</li><li>Using test set to predict classification accuracy.</li><li>Infer decision tree from the model.</li></ol><p>While evaluation method described below:</p><ol><li>Evaluate model fitting using model summary.</li><li>Evaluate model prediction error using confusion matrix.</li><li>Evaluate model prediction error using precision-recall and F1 score.</li><li>Evaluate splitting rule using learning curve.</li></ol><h3>Implementation</h3><p>You can found the source code of this implementation at <a href="https://github.com/Bladefidz/machine-learning-tutorials/blob/master/decision-tree/car.r">my github repository</a>. In this tutorial, I have stressed on analysis aspect, not on the source code. If you are find any difficulties in reading or running the source code, make some effort to search your problem using search engine or access the help feature in R studio by pressing <strong>F1</strong> on selected function name.</p><h4>Analyzing attribute distribution of each criteria</h4><p>This is first and most important step because in this step we evaluate the quality of the data. As if you working with some statistician, you may suggested that the goodness of inferential deduction is not depend so much on the algorithm, but the quality of the data. Another advantage by evaluate the data is we can make presumption about the result will be. In more advance Decision Tree implementation, there is known a technique called as pre-prunning technique which the goal is remove unreliable features, thus will improve learning performance. But, pre-prunning technique need some experience or expertise, so we not concert about pre-prunning technique at this step.</p><p>As to minimizing the assumption as small as possible, we need to look each criteria independently distributed at first. If we look that way, then the explanation of each distribution described as follow:</p><p>What buying histogram tells us are the distribution tend to be uniformly distributed, while with very high and high buying price will likely caused a car to be unaccepted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*9kcHvaA9K_gAJ0nqL0brig.png" /><figcaption>Buying histogram</figcaption></figure><p>What maintenance histogram tells us are the distribution tend to be uniformly distributed, while with very high and high maintenance price will likely caused a car to be unaccepted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*GzSHnboxovWZP-OJlVUdhQ.png" /><figcaption>Maintenance histogram</figcaption></figure><p>What doors histogram tells us are the distribution tend to be uniformly distributed, while with 2 doors will likely caused a car to be unaccepted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*hmGUHcZYEMiRI7B3ExWuIA.png" /><figcaption>Door histogram</figcaption></figure><p>What persons histogram tells us are the distribution tend to be positive skewed, while it is almost absolutely that a car with 2 persons capacity will be unaccepted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*hXzjuo4O6Xhd180RbQP4-w.png" /><figcaption>Persons histogram</figcaption></figure><p>What luggage boots histogram tells us are the distribution tend to be negative skewed, while with small luggage boots will likely caused a car being unaccepted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*3EF2pIxfoG-JBtdyC198VA.png" /><figcaption>Luggage boots histogram</figcaption></figure><p>What safety histogram tells us are the distribution tend to be normally distributed, while with low safety will likely caused a car being unaccepted. Since in statistic point of view normal distribution is a nature in almost real-world cases, then we can decide that safety is most significant feature in our decision tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*mEVtCZisP5PsrPwxzze2Iw.png" /><figcaption>Safety histogram</figcaption></figure><h4>Apply randomized splitting data set into training set and test set</h4><p>In this tutorial, I used 75% for training set and 35% for test set splitting rule after applied randomized algorithm. In statistic we call this technique as random sampling. Because the randomization, each execution will produce different error rate. So, result in this tutorial and your execution result may slightly different with confident interval 95%. If you confused or need proof about random sampling and confidence interval, then try to read <a href="https://en.wikipedia.org/wiki/Central_limit_theorem">central limit theorem</a> and <a href="https://rpubs.com/hmgeiger/370407">confidence interval</a>.</p><p>In evaluation method, we will used incremental percentage splitting rule to produce learning curve. By using learning curve, we will know which is better splitting rule to be used.</p><h4>Apply C50 algorithm on training set</h4><p>This is easiest step because in R, we only need to type a line of code to apply C50 algorithm. By calling an object <strong>decTree</strong> directly will tells us about number of decision nodes (tree size).</p><h4>Using test set to predict classification accuracy</h4><p>This is also easiest step because in R, we only need to type a line of code to make prediction using C50 algorithm. The prediction will produce a row factor called as <strong>y_pred</strong> which is the model prediction of the car criteria.</p><h4>Infer decision tree from the model</h4><p>Since our model produced a decision tree with size in about 40–55 leaves, then our decision tree will be likely complicated. For example, an image below is a decision tree with 83 nodes which has 53 leaves.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qwK8vOehLGmEPNWua2g5Kw.png" /><figcaption>Car decision tree</figcaption></figure><p>A better way to infer decision tree is by read a model’s summary. Here a sample of decision tree summary used in this tutorial:</p><pre># Format: [criteria] = [atribute]:[classification] (number of<br>#         valid decision node/number of invalid decision node)<br># ... is connection or edge</pre><pre>safety = low: unacc (435)<br>safety in {high,med}:<br>:...persons = 2: unacc (279)<br>    persons in {4,more}:<br>    :...buying in {high,vhigh}:<br>        :...maint = vhigh: unacc (74)<br>        :   maint = high:<br>        :   :...buying = vhigh: unacc (41)<br>        :   :   buying = high:<br>        :   :   :...safety = high: acc (20/1)<br>        :   :       safety = med:<br>        :   :       :...lug_boots in {big,med}: acc (10/3)<br>        :   :           lug_boots = small: unacc (6)<br>        :   maint in {low,med}:<br>        :   :...safety = high: acc (68/2)<br>        :       safety = med:<br>        :       :...lug_boots = big: acc (24)<br>        :           lug_boots = small: unacc (24)<br>        :           lug_boots = med:<br>        :           :...doors = 2: unacc (6)<br>        :               doors in {4,5more}: acc (12)<br>        :               doors = 3:<br>        :               :...persons = 4: unacc (3)<br>        :                   persons = more: acc (4)<br>        buying in {low,med}:<br>        :...maint in {high,vhigh}:<br>            :...safety = med:<br>            :   :...lug_boots in {big,med}: acc (50/6)<br>            :   :   lug_boots = small:<br>            :   :   :...maint = vhigh: unacc (14)<br>            :   :       maint = high:<br>            :   :       :...buying = low: acc (5/1)<br>            :   :           buying = med: unacc (5)<br>            :   safety = high:<br>            :   :...buying = med: acc (38/1)<br>            :       buying = low:<br>            :       :...maint = vhigh: acc (19)<br>            :           maint = high:<br>            :           :...lug_boots = big: vgood (4)<br>            :               lug_boots = small: acc (7/1)<br>            :               lug_boots = med:<br>            :               :...doors = 2: acc (2)<br>            :                   doors in {3,4,5more}: vgood (4)<br>            maint in {low,med}:<br>            :...safety = high:<br>                :...lug_boots in {big,med}:<br>                :   :...lug_boots = big: vgood (25)<br>                :   :   lug_boots = med:<br>                :   :   :...doors in {4,5more}: vgood (12)<br>                :   :       doors = 2:<br>                :   :       :...buying = low: good (2)<br>                :   :       :   buying = med: acc (3/1)<br>                :   :       doors = 3:<br>                :   :       :...persons = 4: good (3/1)<br>                :   :           persons = more: vgood (4)<br>                :   lug_boots = small:<br>                :   :...doors = 2:<br>                :       :...persons = 4: good (2)<br>                :       :   persons = more: unacc (4)<br>                :       doors in {3,4,5more}:<br>                :       :...maint = low: good (11)<br>                :           maint = med:<br>                :           :...buying = low: good (4)<br>                :               buying = med: acc (2)<br>                safety = med:<br>                :...lug_boots = small:<br>                    :...persons = 4: acc (12)<br>                    :   persons = more:<br>                    :   :...doors = 2: unacc (2)<br>                    :       doors in {3,4,5more}: acc (7)<br>                    lug_boots in {big,med}:<br>                    :...maint = med:<br>                        :...buying = low: good (13/3)<br>                        :   buying = med: acc (13)<br>                        maint = low:<br>                        :...lug_boots = big: good (13)<br>                            lug_boots = med:<br>                            :...doors in {2,3}: acc (5/1)<br>                                doors in {4,5more}: good (6)</pre><h3>Evaluation</h3><p>Basically, we can used only the model’s summary to evaluate model prediction error. But, in order to provide comprehend proof, we need another validation such us confusion matrix to computer true positive (tp), true negative (tn), false positive (fp), and false negative (fn).</p><h4>Evaluate model fitting using model summary</h4><p>An image below is a sample of model summary. It is look like that our model doing a good job where classification error only in about 1.2%, or in other word from 53 available decision node, we are predict 16 correctly decision node. At detail, the summary tells us that there are 8 <em>unaccepted</em> node classified as <em>accepted</em> node, 1 <em>good</em> node classified as <em>accepted</em> node, 1 <em>unaccepted</em> node classified as <em>good</em> node, 1 <em>accepted</em> node classified as <em>good</em> node, 4 <em>accepted</em> node classified as <em>very good</em> node, and 1 <em>good</em> node classified as <em>very good</em> node.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/493/1*WEYQKD5VNwzs8YgnAHhnvw.png" /><figcaption>C50 model summary of car</figcaption></figure><p>Another information that provided from this summary is <em>attribute usage </em>which tells us about the distribution of attributed used to produce decision nodes. As explained in the image above, <em>safety</em> attribute is most used attribute followed by <em>persons</em> and <em>buying</em>.</p><h4>Evaluate model prediction error using confusion matrix</h4><p>An image below is sample confusion matrix of our model. It’s look like our model fit good enough on test set where there are 14 miss classified decision node.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/269/1*QW5Z-QcXGuuRCfPhVJIabg.png" /><figcaption>Confusion matrix</figcaption></figure><h4>Evaluate model prediction error using precision-recall and F1 score</h4><p>In order to get better insight of measuring prediction error, we used another measurements: <em>precision, recall</em>,<em> </em>and<em> F1 score</em>. An image below is sample of that measurements of our model.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/1*5zyzBUsj_Jlozm7RxtxjCg.png" /><figcaption>Precision, recall, and F1 score</figcaption></figure><p>Since F1 score is the measurement combination of precision and recall, then we can used F1 score to measure our model performance. In image above, show us that our model has high F1 score on classify <em>unacc</em>,<em> acc</em>,<em> </em>and<em> vgood </em>label<em>.</em></p><h4>Evaluate splitting rule using learning curve</h4><p>In this tutorial, we used <em>cross-validation</em> method and <em>accuracy</em> measurement to produce learning curve. An image below is learning curve produced using five iterations on each cross-validation step.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/1*gteNKohhvfIBMmV6NsTg6g.png" /><figcaption>Learning curve</figcaption></figure><p>Learning curve on image above tells us that splitting rule from range 60:40 until 80:20 give us significant performance.</p><h3>Conclusion</h3><p>As we see in model’s summary, the criteria distribution making enough contribution in order to construct decision tree. The <em>safety</em> criteria which is distributed normally and 100% used split decision tree into two, while <em>persons </em>criteria which is positively skewed and 66.31% used became root node.</p><p>Our splitting rule which is 75:35 seems performs good enough, but we may still need to tune the splitting rule in range 60:40 to 80:20 if necessary.</p><p>[*] Assume that we worked on a car factory and want to produce a car. By using decision tree produced C50 algorithm, we need to know which car criteria is likely will be pass the evaluation. After some amount of time analyzing the decision tree, we are decide to pick some most seven significant decision node:</p><pre># Format: (criteria valid/miss-classified) -&gt; statement<br>(vgood 24) -&gt; car has capacity 4 or more persons, low or medium buying pring, low or medium maintenance price, high safety, and has big luggage boots.<br>(vgood 14/3) -&gt; car has capacity 4 or more persons, high safety, low buying price, high maintenance price, and medium or big luggage boots.<br>(good 14) -&gt; car has capacity 4 or more persons, low or medium buying price, medium safety, low maintenance price and big luggage boots.<br>(good 12/3) car has capacity 4 or more persons, medium safety, has medium or big luggage boots, medium maintenance price and low buying price.<br>(acc 51) -&gt; car has capacity 4 or more persons, medium or high safety, high or very high buying price, low or medium maintenance price and big luggage boots.<br>(unacc 77) -&gt; car has capacity of 2 persons, medium or high safety, very high maintenance price.<br>(unacc 35) -&gt; car has capacity of 2 persons, high and very high buying price, low or medium or high maintenance price, small luggage boots and medium safety.</pre><p>Then, by using picked decision node above you want to test this statement:</p><pre>persons = 4<br>buying = ’med’<br>maint = ’low’<br>lug_boots = ’med’<br>safety = ’med’<br>doors = 4</pre><p>[*] The model will classified that statement as ‘good’.</p><h3>Suggestion</h3><p>If you are looking for current implementation of Decision Tree learning, then try read resource [3]. At resource [3], you will find out that Decision Tree learning model has equally performance to Neural Network in case predicting building energy demand in Japan.</p><h3>Resources</h3><ol><li><a href="http://kt.ijs.si/MarkoBohanec/pub/Avignon88.pdf">Knowledge acquisition and explanation for multi-attribute decision making</a></li><li><a href="https://www.researchgate.net/profile/Ivan_Bratko/publication/2820632_Machine_Learning_by_Function_Decomposition/links/0fcfd508bb1f4468b3000000/Machine-Learning-by-Function-Decomposition.pdf">Machine learning by function decomposition</a></li><li><a href="https://www.sciencedirect.com/science/article/pii/S0378778810001350">A decision tree method for building energy demand modeling</a></li><li><a href="http://saiconference.com/Downloads/SpecialIssueNo10/Paper_3-A_comparative_study_of_decision_tree_ID3_and_C4.5.pdf">A compararive study of decision tree ID3 and C4.5</a></li><li><a href="http://hunch.net/~coms-4771/quinlan.pdf">Induction of decision tree</a></li><li><a href="https://rpubs.com/hmgeiger/370407">Foundations for statistical inference — Confidence intervals</a></li><li><a href="https://cran.r-project.org/web/packages/C50/C50.pdf">Package C50</a></li><li><a href="http://archive.ics.uci.edu/ml/datasets/Car+Evaluation">Car evaluation data set</a></li><li><a href="https://en.wikipedia.org/wiki/Substitute_good">Substitute good</a></li><li><a href="https://en.wikipedia.org/wiki/Utility">Utility</a></li><li><a href="https://en.wikipedia.org/wiki/Unsupervised_learning">Unsupervised learning method</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5272675451f9" width="1" height="1" alt=""><hr><p><a href="https://medium.com/machine-learning-guy/using-decision-tree-method-for-car-selection-problem-5272675451f9">Using Decision Tree Method for Car Selection Problem</a> was originally published in <a href="https://medium.com/machine-learning-guy">Machine Learning Guy</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An Introduction to Decision Tree Learning: ID3 Algorithm]]></title>
            <link>https://medium.com/machine-learning-guy/an-introduction-to-decision-tree-learning-id3-algorithm-54c74eb2ad55?source=rss-e25dd3616749------2</link>
            <guid isPermaLink="false">https://medium.com/p/54c74eb2ad55</guid>
            <category><![CDATA[decision-tree]]></category>
            <category><![CDATA[id3-algorithm]]></category>
            <category><![CDATA[decisions]]></category>
            <category><![CDATA[entropy]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Hafidz Jazuli]]></dc:creator>
            <pubDate>Mon, 12 Mar 2018 13:38:28 GMT</pubDate>
            <atom:updated>2018-05-13T23:54:00.376Z</atom:updated>
            <content:encoded><![CDATA[<p>This model is very simple and easy to implement. But, if you like to get more insight, below I give you some important prerequisite related to this model.</p><p>Prerequisite:<br>- Data structure (Tree)<br>- Searching algorithms (greedy algorithm, heuristic search, hill climbing, alpha-beta pruning)<br>- Logic (OR, AND rules)<br>- Probability (Dependent and Independent)<br>- Information Theory (Entropy)</p><p>Applications:<br>- Operational Research<br>- <a href="https://www.investopedia.com/articles/financial-theory/11/decisions-trees-finance.asp">Finance</a><br>- Scheduling problems<br>- etc</p><p>In this episode of Decision Tree, I will give you complete guide to understand the concept behind Decision Tree and how it work using an intuitive example. In the next episodes, I will show you the easiest way to implement Decision Tree in Python using <strong>sklearn</strong> library and <a href="https://medium.com/machine-learning-guy/using-decision-tree-method-for-car-selection-problem-5272675451f9">R using <strong>C50</strong> library (an improved version of ID3 algorithm)</a>.</p><h4>Motivation</h4><p>Decision Tree is very very very simple model. It is widely known and used in many businesses to support decision making process and risk analysis. It is also one of legendary learning model which is heavily used in ’60–80’s to build expert systems. One of very popular expert systems which adopt decision tree ( almost cs and informatics student knew about) is <a href="https://en.wikipedia.org/wiki/Mycin">Mycin</a> which developed at 1970 by Buchanan and Cohen. But, like another classic expert systems, Mycin is not fully automatic operated. At that years, human experts still needed to input hard coded rules into expert systems. After 80’s, this model has been lost popularity since it’s seems can not be extended using more sophisticated mathematics.</p><p>But now, Decision Tree learning start gaining popularity since some machine learning practitioners proved that <a href="http://anand.typepad.com/datawocky/2008/03/more-data-usual.html">inferior algorithm with bigger data may beats sophisticated algorithm</a>. Beside that, it is worth to learn Decision Tree learning model at first place, before jump into more abstract models, such as, Neural Network and SVM (Support Vector Machine). By learning Decision Tree, you will have better insight how to implement basic probability theory and how to transform basic searching algorithm into machine learning algorithm.</p><p>In this episode, I will introduce you <strong>ID3</strong> method which is one of widely used decision tree algorithm.</p><h4>What is Decision Tree in One Sentence?</h4><p>Simply, it is enhanced greedy search algorithm that implement heuristic function using probability as comparison values, but does not implement <a href="https://en.wikipedia.org/wiki/Backtracking"><em>backtracking</em></a><em> </em>(because it is greedy!).</p><h4>Why Decision Tree in Two Sentences?</h4><p>Suppose, you want to make a strategy which is contains many decisions, then it is <em>not</em> <em>good</em> <em>idea</em> to use brute force algorithm to decide which is best decision combination. So, it is <em>good idea</em> to implement decision tree algorithm which use heuristic function to choose good decision combination.</p><h4><strong>When Use Decision Tree Learning?</strong></h4><ol><li>The most commonly reasonable reason to used Decision Tree is when you realized that <em>Naive Bayes</em> will not satisfy your goal. Everybody knew that it is <em>naive</em> to seeing all features as independent variables.</li><li>If we have categorical data, for example: hot, mild, and cold.</li><li>If we have attribute-value pairs data, for example: an attribute ‘temperature’ may has some discrete values ‘hot’, ‘mild’, and ‘winter’.</li><li>If objective value has discrete output values, for example ‘yes’, or ‘no’.</li></ol><h4><strong>Mathematical Tool to Use</strong></h4><p>Basically, we only need two mathematical tool to implement complete ID3 algorithms:</p><ul><li><strong>Entropy</strong><br>It is a fundamental theorem which commonly used in information theory to measure important of information relative to its <em>size</em>. Let x is our training set contains positive and negative examples, then the entropy of x relative to this classification is:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/308/1*EMDZhAKWMqvhvqm6cVnuYg.png" /><figcaption>Entropy function</figcaption></figure><ul><li><strong>Information Gain<br></strong>In multivariate calculus, we have learn how to use a partial derivative of each variable relative to all other variables to find local optimum. In information theory, we used similar concept, we derive the original entropy of population to measure information gain of each attribute.<br>For training set x and its attribute y, the formula of Information Gain is:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/1*0X3NZWAITz7pRgo_HWcpGw.png" /><figcaption>Decision tree</figcaption></figure><p>I will give you an easy example in order to make sense the formula above. Suppose we face with binary classification ‘yes’ or ‘no’, then we label of bit 1 for yes, and label of bit 0 for no. One of our feature’s attributes is ‘Outlook’ (O) which has three possible values ‘Sunny’ (Os), ‘Overcast’ (Oo), and ‘Rain’ (Or). Then, the information gain of Outlook is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/753/1*HzOga7ugAjFHDriKSt4tTw.png" /></figure><h4>ID3 Algorithm</h4><p>For simplicity, I choose to write ID3 algorithm using pseudo code because it is more efficient and cleaner. Actually pseudo code format easier to read, although for who not learn algorithm before.</p><pre># x is examples in training set<br># y is set of attributes<br># labels is labeled data<br># Node is a class which has properties values, childs, and next<br># root is top node in the decision tree</pre><pre># Declare:<br>x = # Multi dimensional arrays<br>y = # Column names of x<br>labels = # Classification values, for example {0, 1, 0, 1}<br>         # correspond that row 1 is false, row 2 is true, and so on<br>root = ID3(x, y, label, root)</pre><pre># Define:<br>ID3(x, y, label, node)<br>  initialize node as a new node instance<br>  if all rows in x only have single classification c, then:<br>    insert label c into node<br>    return node<br>  if x is empty, then:<br>    insert dominant label in x into node<br>    return node<br>  bestAttr is an attribute with maximum information gain in x<br>  insert attribute bestAttr into node<br>  for vi in values of bestAttr:<br>    // For example, Outlook has three values: Sunny, Overcast, and Rain<br>    insert value vi as branch of node<br>    create viRows with rows that only contains value vi<br>    if viRows is empty, then:<br>      this node branch ended by a leaf with value is dominant label in x<br>    else:<br>      newY = list of attributes y with bestAttr removed<br>      nextNode = next node connected by this branch<br>      nextNode = ID3(viRows, newY, label, nextNode)<br>  return node</pre><p>The python version of pseudo code above can be found at <a href="https://github.com/Bladefidz/machine-learning-tutorials/blob/master/decision-tree/decision_tree.py">github</a>. If you struggle with how to implement ID3 algorithm, then it worth to play with python version of pseudo code above. I also provides a data set that can be used for testing purpose.</p><h4>An Intuitive Example: What the best day to Play Tennis?</h4><p>Consider a table of data set below. Given the column “Play Tennis” as <strong>target attribute</strong>, and example of days which such conditions as attributes: <em>Outlook</em>; <em>Temperature</em>; <em>Humidity</em>; and <em>Wind</em>. We want to know what the best day to play tennis.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/494/1*82jxlyISGWEe4MQ62FKNPg.png" /><figcaption>Training set contains 14 examples</figcaption></figure><p>We want to construct a decision tree of the training set above using ID3 algorithm which has been described before.</p><p># Declaration<br>For simplicity, we will give name of each attribute in data set:</p><pre>O is Outlook attribute<br>T is Temperature attribute<br>H is Humidity attribute<br>W is Wind attribute</pre><p># First iteration<br>At first iteration, we need to know which is best attribute to be chosen as top root in our decision tree. To do that, ID3 will find the <em>best attribute</em> which is has maximum information gain. Given the information gain for each attribute:</p><pre>attributes = [O, H, W, T]<br>G(x, O) = 0.246<br>G(x, H) = 0.151<br>G(x, W) = 0.048<br>G(x, T) = 0.029</pre><p>So, based on the information gains calculated above, we choose attribute <em>Outlook</em> as first root node which has three branches <em>Sunny</em>, <em>Rain</em>, and <em>Overcast</em>. Our decision tree will look like an image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/224/1*95SVZsvCAUUjbog9waU_tA.png" /><figcaption>Initial decision tree</figcaption></figure><p>For the next iterations, we remove <em>O</em> from attribute list.</p><p># Second iteration<br>We want examine which the best attribute for branch of <em>Sunny</em>. Remember, that new x is rows contains values of <em>Sunny</em>.</p><pre>x = [x[0], x[1], x[7], x[8], x[10]]<br>attribute= [H, W, T]<br>G(x, H) = .970 - (3/5) * 0 - (2/5) * 0 = .970<br>G(x, T) = .970 - (2/5) * 0 - (2/5) * 1 = .570<br>G(x, W) = .970 - (2/5) * 1 - (3/5) * .918 = .019</pre><p>So, based on the information gains calculated above, we choose attribute <em>Humidity</em> as attribute in branch <em>Sunny</em>. Our decision tree will look like an image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/299/1*HTFeAlPOfYzrVW7Q9Cdn2A.png" /><figcaption>Add new attribute Humidity</figcaption></figure><p>For the next iterations, we remove <em>H</em> from attribute list.</p><p># Third iteration<br>Next node is an attribute <em>Humidity</em> which has two possible values {<em>High, Normal</em>}. A branch <em>High </em>dominated by single label which is <em>No</em>, caused this branch ended with a leaf contains label <em>No</em>. Same case with branch <em>Normal</em> which ended with a leaf contains label <em>Yes</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*s5d28tQs6F6u0EYJsiCvBw.png" /><figcaption>Humidity’s Leafs</figcaption></figure><p># Four iteration<br>All rows contains value <em>Outcast</em> are dominated by single label <em>Yes</em>, so branch of <em>Overcast</em> ended with a leaf contains label <em>Yes.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*VXLdDindmHmD1iGYJ0zFYg.png" /><figcaption>Overcast’s leaf</figcaption></figure><p># Fifth iteration<br>We want examine which the best attribute for branch of <em>Rain</em>. Remember, that new x is rows contains values of <em>Rain</em>.</p><pre>x = [x[3], x[4], x[5], x[9], x[13]]<br>attribute = [W, T]<br>G(x, W) = .970 - (2/5) * 0 - (3/5) * 0 = .970<br>G(x, T) = .970 - (0/5) * 0 - (3/5) * .918 - (2/5) * 1.0 = .019</pre><p>So, based on the information gains calculated above, we choose attribute <em>Wind</em> as attribute in branch of <em>Rain</em>. Our decision tree will look like an image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/366/1*kOlv-9bp-Y-WtgB7EA087g.png" /><figcaption>Add new attribute Wind</figcaption></figure><p>For next iteration, we remove attribute <em>W</em> from attribute list</p><p># Sixth iteration<br>Next node is an attribute <em>Wind</em> which has two possible values {<em>Weak, Strong</em>}. A branch <em>Strong </em>dominated by single label which is <em>No</em>, caused this branch ended with a leaf contains label <em>No</em>. Same case with branch <em>Weak</em> which ended with a leaf contains label <em>Yes</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*hyNHuC9L-POy28eSdCubEQ.png" /><figcaption>Wind’s leafs</figcaption></figure><p># Seven iteration<br>Actually, there is no iteration left, since all branches in our decision tree ended with leafs. In other word, we prune attribute <em>Temperature</em> from our decision tree.</p><h4>Conclusion</h4><p>Decision tree is a very simple model that you can build from starch easily. One of popular Decision Tree algorithm is ID3. Basically, we only need to construct tree data structure and implements two mathematical formula to build complete ID3 algorithm. The complete implementation of ID3 algorithm in Python can be found at <a href="https://github.com/Bladefidz/machine-learning-tutorials/blob/master/decision-tree/decision_tree.py">github</a>.</p><h4>Suggestion</h4><p>This article not intended to go deeper into analysis of Decision Tree. My goal in this tutorial is just to introduce you an important concept of ID3 algorithms which first introduced by <a href="http://hunch.net/~coms-4771/quinlan.pdf">John Ross Quinla at 1989</a>. Later, he developed C4.5 algorithm which is improved version of ID3 algorithm. Then, the improved version of C4.5 algorithm is C5.0 algorithm. There is also another popular algorithm called as CART (<a href="https://machinelearningmastery.com/classification-and-regression-trees-for-machine-learning/">Classification And Regression Trees</a>).</p><h4>Resources</h4><ol><li><a href="http://www.cs.bham.ac.uk/~mmk/Teaching/AI/l3.html">Introduction to AI by Carnegie Melon University</a></li><li><a href="http://www.cs.princeton.edu/courses/archive/spr07/cos424/papers/mitchell-dectrees.pdf">Decision Tree Learning by Pricenton University</a></li><li><a href="https://www.amazon.com/Artificial-Intelligence-Modern-Approach-3rd/dp/0136042597/ref=sr_1_3?s=books&amp;ie=UTF8&amp;qid=1520768466&amp;sr=1-3&amp;keywords=Artificial+Intelligence%3A+A+Modern+Approach">Artificial Intelligence: A Modern Approach</a></li><li><a href="http://hunch.net/~coms-4771/quinlan.pdf">Induction of Decision Tree</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=54c74eb2ad55" width="1" height="1" alt=""><hr><p><a href="https://medium.com/machine-learning-guy/an-introduction-to-decision-tree-learning-id3-algorithm-54c74eb2ad55">An Introduction to Decision Tree Learning: ID3 Algorithm</a> was originally published in <a href="https://medium.com/machine-learning-guy">Machine Learning Guy</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Statistical Interpretation Of Term Specificity And Its Application In Retrieval]]></title>
            <link>https://medium.com/classic-information-retrieval/sparck-jones-k-e2b8d1647351?source=rss-e25dd3616749------2</link>
            <guid isPermaLink="false">https://medium.com/p/e2b8d1647351</guid>
            <category><![CDATA[term-weighting]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[automatic-term-weighting]]></category>
            <category><![CDATA[zipf-law]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <dc:creator><![CDATA[Hafidz Jazuli]]></dc:creator>
            <pubDate>Sun, 10 Sep 2017 03:19:33 GMT</pubDate>
            <atom:updated>2017-09-10T03:26:03.347Z</atom:updated>
            <content:encoded><![CDATA[<h4>Sparck Jones, K.</h4><p>Easy to understand and awesome explanation of problems and solutions by Mrs. Jones. Her explanations make me sure that we should treated each each term in postings list as statistic product. Despite by its semantic meaning, we could built term weight variances measured by its level of important in specific collection. For example, a term “farm-” should have weight 2.0 for agriculture collection and 1.0 for computer science collection.</p><h3><strong>Old Definition of Exhaustivity and Specificity</strong></h3><p><strong>Exhaustivity</strong> represent coverage of document’s various topics defined by the assigned terms. In the case, if more term assigned into document caused its exhaustivity increased, but size of indexing vocabulary is constant, then the chance of document matched to the various query is increased. Intuitively, this problem could break our relevance rank calculation because some new terms that have been added may not have reasonable level of important. A solution is define <em>optimum</em> <em>level of indexing¹</em> exhaustivity for a given document collection. The idea is the average numbers of descriptors per document should be adjusted and avoid <em>false drops²</em> to maximize retrieved relevance documents.</p><p><strong>Specificity</strong> represent level of detail of a specific term or semantic property of index terms: a term is more or less specific as its meaning is more or less detailed precise. Intuitively we know that general term “Computational statistics” should has larger collection distribution then specific terms, such as: “Monte carlo”, “Markov chain”, or “Local regression”. But, to decide which best fitted term based on most assumption is not enough.</p><h3>New Definition of Exhaustivity and Specificity</h3><p>Our job would be complicated if we interpreted index of terms as semantic property because this effort needed very skilled resources and required high quality assumption based on experienced. Our job would be easier if we could built controlled framework that capable to do natural language analysis in any document category based on statistic. Some researchers have been did this very well, for examples: Salton (1968), Zunde and Slamecka (1967), and more.</p><p>So, we need to redefine exhaustivity and specificity:</p><p><strong>Exhaustivity</strong> is how many <em>significant terms</em> contains in a document. Significant terms are any terms that have very high contribution to describe main content of a document specifically. For example, we should not count such as: terms like ‘a’ and ‘the’ clearly are not significant term.</p><p><strong>Specificity</strong> is how good the discriminant value of a term. Intuitively, a good term should not belong as common terms in a document collection. For example: terms like ‘inform-’ and ‘comput-’ are meaningless in the computer science document collection because they are very common used and distributed broadly.</p><h3>Problems</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/825/1*LtNu0bAG2Ti91oIlCElIfQ.png" /><figcaption>Statistic results of Cranfield, Inspec and Keen documents collections.</figcaption></figure><p>Table 1 show the statistical result of three documents collection. We could conclude that:</p><ul><li>Query tend to be used frequent term combination. This fact proved by “number of documents per term” is likely less than “number of documents per request term”.</li><li>We need to provide alternative substitutions for given terms in the query through classification or by statistic analysis to find associated term. This solution is needed to solve problem that “Number of retrieving terms per document” is likely less than “Number of terms per request”.</li><li>We need to do controlled term identification by exploited the good features from both very frequent and non-frequent terms, while remove bad terms that produced from them. This solution based on recall/precision graph (figure 1) of frequent and non-frequence terms of Cranfield document collection.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/629/1*6yeoWRtIqyuWlZCyPNRKxw.png" /></figure><h3>Term weighting as General Solution</h3><p>The idea of term weighting is not new, there are some great research conducted by Salton (1968) and Artandi Wolfe (1969). Both of them showed that automatically assigned term weight perform at least as well as manually assigned weights. Unfortunately, both of them not included the relative weight of the term across the entire collection. To calculate term weight related to its relative frequency, we need to follow Zipf law, then our term weighting calculation will be <strong>log_2(N) - log_2(n) + 1</strong>, where <strong>N</strong> is total number of documents and <strong>n</strong> is total documents that has given term.</p><h3>Experiment Results</h3><p>Figure 2 showed recall/precision graph of terms and weighted term in Cranfield document collection. From the figure 2, we could conclude that precision could be increased if we applied weighting scheme based on relative frequent of term to its collection.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*5oh6dXX7IH2ycsk5nkmH9w.png" /></figure><p>___</p><p>¹ optimum level of indexing could be achieved by determine averaged value of any possible term combination that expected appeared in query.</p><p>² false drop related to relative level of important of certain terms. For example, a term ‘programming’ may be not important for ‘computer science’ documents, but may be important for ‘mathematic’ documents.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e2b8d1647351" width="1" height="1" alt=""><hr><p><a href="https://medium.com/classic-information-retrieval/sparck-jones-k-e2b8d1647351">A Statistical Interpretation Of Term Specificity And Its Application In Retrieval</a> was originally published in <a href="https://medium.com/classic-information-retrieval">Classic Information Retrieval</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Statistical Approach to Mechanized Encoding and Searching of Literary Information]]></title>
            <link>https://medium.com/classic-information-retrieval/h-p-luhn-a-statistical-approach-to-mechanized-encoding-and-searching-of-literary-information-521d2f2e7fc3?source=rss-e25dd3616749------2</link>
            <guid isPermaLink="false">https://medium.com/p/521d2f2e7fc3</guid>
            <category><![CDATA[semantics]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <dc:creator><![CDATA[Hafidz Jazuli]]></dc:creator>
            <pubDate>Sat, 02 Sep 2017 08:58:41 GMT</pubDate>
            <atom:updated>2017-09-10T03:27:01.024Z</atom:updated>
            <content:encoded><![CDATA[<h4>Luhn, H. P</h4><p>Very brief introduction of implementing statistic on mechanical (computer) in the literature searching by <a href="https://en.wikipedia.org/wiki/Hans_Peter_Luhn">Hans Peter Luhn</a>. In this paper, he was not provide any mathematical formulation to describe his idea, but using a novel narration about any problems related to literature searching. The main reason why he was introduced mechanized encoding using statistical approach is the intelligent of experts could be wasted by did repetitive work such as encoding many documents into related topic of information. If the expert could translate their knowledge of specific field into thesaurus and stored it into programmed computer to do literature search, than the work could be more efficient and the expert would be more on the creative task such as configuring computer to do better job.</p><p>Although Luhn used statistical approach, he saw the representation of information into <strong>author’s point of view</strong> (figure 1). He assumed that the author’s idea could be represented as how many a word used in the document. Since different author has different language style, two document or more could be <strong>represented same idea described by different words</strong>. To resolve that, Luhn described a <strong>notion</strong> as element that emphasised documents into ‘same communicative idea’. Notions should be related to each other within the sentence. In the other word, we could identify similarity between document based on distribution of notions. To identify notion, an expert built thesaurus-type dictionary that identify a group of terms based on their relationship or meaning (semantic).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xJl_Cy0n2wERHLqx8RaLig.png" /><figcaption>Figure 1. Communication of idea</figcaption></figure><p>Luhn suggested that a computer has internal memory to store thesaurus and already programmed to do linear searching task. The computer could be operated by non expert user which economically advantage. The scanning result will be stored in magnetic tape and saved desired data such as distribution of term (notion) in the collection. After scan was ended, the experts should analyzed the result, then command to repeat scanning after modify some configuration if needed, or judge the scanning result is good enough.</p><p>Sometimes, using only thesaurus not enough to identify similarity between any documents. Such of configuration needed to produce better result. That is, the intelligent of expert needed to judged a term is a good discrimination or not, if not, they should find another similar term which has higher discriminant. For example, in the electrical engineering field, a term (notion) ‘electricity’ could be used as common term in all document collection which worthless as discriminant or a term ‘cortex’ could be rare. The solution are by expanding general term ‘electricity’ into specific related term such as ‘power’, ‘generator’, ‘motor’, etc; and unify a very specific term ‘cortex’ into bigger semantic group such as ‘brain’, ‘neural’, etc.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=521d2f2e7fc3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/classic-information-retrieval/h-p-luhn-a-statistical-approach-to-mechanized-encoding-and-searching-of-literary-information-521d2f2e7fc3">A Statistical Approach to Mechanized Encoding and Searching of Literary Information</a> was originally published in <a href="https://medium.com/classic-information-retrieval">Classic Information Retrieval</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simplified Vector Space Model in Information Retrieval]]></title>
            <link>https://medium.com/@bladefidz/simplified-vector-space-model-in-information-retrieval-a0b5c40c0916?source=rss-e25dd3616749------2</link>
            <guid isPermaLink="false">https://medium.com/p/a0b5c40c0916</guid>
            <category><![CDATA[space-vector-model]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <dc:creator><![CDATA[Hafidz Jazuli]]></dc:creator>
            <pubDate>Mon, 28 Aug 2017 22:07:23 GMT</pubDate>
            <atom:updated>2017-08-28T22:14:48.906Z</atom:updated>
            <content:encoded><![CDATA[<p>37 years ago, Gerard Salton introduced a new way to represent words into dimensional space <a href="http://dl.acm.org/citation.cfm?id=361220">1</a>. Since then, more researcher interested in information retrieval subject after stagnant for a period. Why this model so interesting?</p><p>The first time i knew Salton’s model when i read Grossman’s book: <a href="https://books.google.co.id/books?hl=en&amp;lr=&amp;id=65oACAAAQBAJ&amp;oi=fnd&amp;pg=PP12&amp;dq=information+retrieval+algorithms+and+heuristics&amp;ots=NJEcfEnXFb&amp;sig=gtU9JVKE568Q0F-7vyhJriWS2qc&amp;redir_esc=y#v=onepage&amp;q=information%20retrieval%20algorithms%20and%20heuristics&amp;f=false">Information Retrieval: Algorithm and Heuristics</a>. Although, this book not quietly comfortable for beginner, but the very fast explanation provided by Grossman will at least challenge your intuition through writer’s view into lot of significant and recent publication. You will found the vector space model in the second chapter as first sub chapter. Likely, Grossman explained the vector model space very similar like was Salton explain the model in his paper. <strong>“The intuition…”</strong>, he said, <strong>“.. if we can show any words as trajectory in the space, then we can calculate the similarity between them”</strong>. Like one of fundamental concept in classical physic, a vector represent a physical object by its <em>magnitude</em> in the space dimensional manner. But, rather than <em>magnitude</em>, we used a <em>weight</em> in the concept of language. The intuition of <em>weight</em> is how many <strong>important</strong> <strong>words</strong> used in a document that <strong>matched</strong> with the search of information (<em>query</em>). For example, let say we need to search information “vector space” and have three documents in the collection: D1, D2, and D3. Each of them has two matched words: “… vector … model …”, “… language … model …”, and “… vector … space …”. Since a query consisted by two words, the we have two dimensional space (see image below). By looking into our drawing of vectors, we conclude that vector D3 is matched with our ‘information need’. Our drawing of vector still worked if we have thousand or even million documents, but it just difficult to draw at least four dimensional space defined by only four term. So, if we represented a query and any documents as vectors in the space, then we can assumed that closer any document’s vector into the query’s vector than higher their similarity to the query.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/240/1*e8Sb_kYQlF9v56raoG887g.png" /></figure><p>If we continued by given many possible query into the space, then naively, we can created indexes defined by any document which its vector passed by any term’s magnitudes. We can still extend this model to find how much likely a document similar to the query (relevance ranking) by calculate distance between their vector to the query’s vector. You may use dot product (Manhattan distance) or relative angle to calculate the distance between vector. Another case which we can still use this model is document clustering, simply by implementing the similarity concept between vector to find centroid and maximum distance for each group.</p><p>Event vector space model have been good enough to visualize similarity, but this model rarely used in the modern information retrieval. The calculation of angle is not good enough to used as proper <strong>term weighting</strong>. Once again, the exhaustive calculation like statistic proved as better solution to find proper term weighting in the application of Natural Language Processing (NLP) as Information Retrieval (IR) should be stand for.</p><p>:)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a0b5c40c0916" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>