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

• US 20070136223A1
• Filed: 12/08/2006
• Published: 06/14/2007
• Est. Priority Date: 12/09/2005
• Status: Active Grant

• 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, Kyung-Sook, Bae, Jung-Sook, Kim, Dong-Hee, Lee, Won-Don, Shin, Gyung-Chul
• Granted Patent: US 7,685,087 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• 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 method for forming a decision tree by using an inference engine in a ubiquitous environment having a plurality of sensors, the method comprising:

a) generating a data table for a data event set based on information collected by the at least one sensor;

b) establishing a weight value of the data event set, and calculating an entropy based on the established weight value (here, 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.

2. The method of claim 1, wherein the weight value in b) indicates importance of data collected by the sensor compared to a data event set to have a weight value 1.

3. The method of claim 1, wherein the entropy in b) is obtained by dividing a gain value of an attribute A (here, the attribute A is a distinguisher for distinguishing the information collected by the sensor) by a partitioning information value of the attribute A.

4. The method of claim 3, wherein the gain value of the attribute A is a difference between information values of a set T (here, the set T has information collected by the sensor) and information values of the attributes A in the entire set T.

5. The method of claim 4, wherein the information value of the set T is obtained by a sum of values (freq(C_i, T)/|T|) obtained by dividing the number of samples in classes of the set T by the number of events having a weight value 1, and logarithmic values of the values (freq(C_i, T)/|T|).

6. The method of claim 4, wherein attribute event values indicating a plurality of event values in the attribute of the set T are divided by the set T, which are multiplied by information values for the attribute event values indicating a plurality of event values in the attribute of the set T, and which are then added to obtain the information value of the attribute A for the set T.

7. The method of claim 3, wherein the partitioning information value of the attribute A is obtained by a sum of values (|T_Aj|/|T|) obtained by dividing the number of subsets having a predetermined outcome value for a single attribute A among the set T by the number of events having the weight value 1, and logarithmic values of the value (|T_Aj|/|T|).

8. The method of claim 3, further comprising:

a class membership value C_k(m) indicating a probability of a predetermined event class;

an outcome membership value O_An(m) indicating a result of the attribute A;

an event value p indicating the number of events in the entire set T;

a sample number value freq(C_i, T) indicating the number of samples in the class of the entire set T; and

an attribute event value |T_Aj| indicating a plurality of event values in the attribute A of the entire set T.

9. The method of claim 8, wherein a sum of the plurality of outcome membership values is 1.

10. The method of claim 8, wherein the sample number value is obtained by a sum of values obtained by multiplying the weight values by classes.

11. The method of claim 8, wherein the attribute event value is obtained by a sum of values obtained by multiplying the weight values by the outcome membership values of the event in the attribute A of the entire set T.

12. The method of claim 3, further comprising:

a subset value T_Aj having an output value for a single attribute A among the entire set T; and

a value |T| indicating the number of samples having the weight value 1.

13. A method for updating a decision tree by using an inference engine in a ubiquitous environment having a plurality of sensors, the method comprising:

a) collecting data from at least one second sensor while a first decision tree is formed based on attributes of data collected from at least one first sensor;

b) when a new attribute is generated from the data collected from the second sensor, establishing a weight value for the new attribute;

c) generating a data table for the data collected from the second sensor having the attribute having the established weight value;

d) generating a final data table based on the data table generated in c) and a data table for the first decision tree; and

e) generating a second decision tree for the data collected from the first and second sensors based on the final data table.

14. The method of claim 13, wherein, when the data table for the first decision tree is not provided, d) it comprises:

generating a first data table based on the first decision tree; and

generating the final data table based on the data table generated for the data collected from the second sensor and the first data table.

15. The method of claim 13, wherein a data entry of the final data table is formed as probability values between 0 and 1 (here, the data entry is an outcome value for an attribute of the data collected from the sensor).