Method for making decision tree using context inference engine in ubiquitous environment

• US 7,685,087 B2
• Filed: 12/08/2006
• Issued: 03/23/2010
• Est. Priority Date: 12/09/2005
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute, The Industry & Academic Cooperation In Chungnam National University
• Original Assignee: Electronics and Telecommunications Research Institute, The Industry & Academic Cooperation In Chungnam National University
• Inventors: Kim, Dong-Hee, Shin, Gyung-Chul, Lee, Won-Don, Bae, Jung-Sook, Kim, Kyung-Sook
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Tran; Mai T
• Application Number:
  US11/635,794
• Publication Number:
  US 20070136223A1
• Time in Patent Office: 1,201 Days
• Field of Search: 706/46, 706/45
• US Class Current: 706/46
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

The present invention relates to a method for generating a decision tree using an inference engine in a ubiquitous environment. In the method, a data table for a data event set is generated based on information collected by at least one sensor. Subsequently, a weight value of the data event set is established, and an entropy is calculated based on the established weight value (here, the entropy is a scale for classifying the information collected by the sensor into respective classes). In addition, the decision tree for the collected information is formed based on the calculated entropy.

Claims

1. A computer-implemented method for forming a decision tree for use with an inference engine in a ubiquitous environment having a plurality of sensors, the method comprising:

a) generating a data table for a set of events based on information collected by at least one of the sensors;

b) establishing a weight value for each event in the set, and calculating an entropy based on the established weight value, wherein the entropy is a measure for classifying the information collected by the sensor into respective classes; and

c) forming the decision tree for the collected information based on the calculated entropy;

wherein the weight value in b) indicates importance of the event in the set;

wherein the decision tree infers a low level data context inputted from the sensors as a high level context to be entered into a knowledge system using the inference engine; and

wherein the entropy in b) is obtained by the following equation;

Gain_ratio (A)=Gain (A)/split_info (A)

where

Gain_ratio(A) is the entropy;

Gain(A) is a gain value of an attribute A, wherein the attribute A is a distinguisher for distinguishing the information collected by the at least one sensor; and

split_info(A) is a partitioning information value of the attribute A.

2. The method of claim 1, wherein the gain value Gain(A) of the attribute A is a difference between an information value info(T) of a set T of p events and an information value info_A(T) of the attribute A in the entire set T, wherein information on the p events of the set T is collected by the at least one sensor.

3. The method of claim 2, wherein the information value info(T) of the set T is obtained by the following equation:

$\mathrm{info}<br><br>\left(T\right)=-\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br><br><br>\mathrm{freq}<br><br>\left(C_i,T\right)/<br><br>T<br><br>\times <br><br>{\log }_2<br><br>\left(\mathrm{freq}<br><br>\left(C_i,T\right)/<br><br>T<br><br>\right)$

where

freq(C_i, T) is the number of samples in class C_i, among k classes C₁ through C_k of the set T, wherein the samples are events having a weight value of 1, and

|T| is the number of all samples in the set T.

4. The method of claim 3, wherein the information value info_A(T) of the attribute A in the entire set T is determined as follows:

${\mathrm{info}}_A<br><br>\left(T\right)=\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br><br><br>T_{\mathrm{Aj}}<br><br>/<br><br>T<br><br>\times <br><br>\mathrm{info}<br><br>\left(T_{\mathrm{Aj}}\right)$

where

T_Aj is a subset of events having an outcome value j for the attribute A in the set T,

|T_Aj| is the number of samples in T_Aj, and

info(T_Aj) is the information value of the subset T_Aj.

5. The method of claim 3, further comprising defining at least one of:

a class membership value C_i(m) indicating a probability of class C_i among k classes C₁ though C_k of the set T at an m^th event;

an outcome membership value O_Aj(m) indicating a value of an outcome j of the attribute A at the m^th event.

6. The method of claim 5, wherein

$\sum _{}^{}$

i = 1 k ⁢

C i ⁡

( m ) = 1.

7. The method of claim 5, wherein freq(C_i, T) is obtained as

$\sum _{}^{}$

m = 1 p ⁡

( T ) ⁢

⁢

Weigh ⁡

( m ) ×

C i ⁡

( m )

where weight(m) is the weight value assigned to the m^th event.

8. The method of claim 7, wherein the number |T_Aj| of samples in T_Aj, which is a subset of events having an outcome j for the attribute A in the set T, is obtained as follows:

$<br><br>T_{\mathrm{Aj}}<br><br>=\underset{m=1}{\overset{p<br><br>\left(T_{\mathrm{Aj}}\right)}{\sum <br><br>}}<br><br><br><br>\mathrm{Weight}<br><br>\left(m\right)\times <br><br>O_{\mathrm{Aj}}<br><br>\left(m\right).$

9. The method of claim 2, wherein the partitioning information value split_info(A) of the attribute A is obtained as follows:

$\mathrm{split\_info}<br><br>\left(A\right)=-\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br><br><br><br><br>T_{\mathrm{Aj}}<br><br>/<br><br>T<br><br>\times <br><br>{\log }_2<br><br>\left(<br><br>T_{\mathrm{Aj}}<br><br>/<br><br>T<br><br>\right)$

where

|T| is the number of all samples in the set T, wherein the samples are events having a weight value of 1,

T_Aj is a subset of events having an outcome j for the attribute A in the set T, and

|T_Aj| is the number of samples in T_Aj.