Data classification system and method for building classification tree for the same

• US 7,930,311 B2
• Filed: 03/12/2008
• Issued: 04/19/2011
• Est. Priority Date: 12/28/2007
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Huang, Tsung-Jen, Liaw, Yi-Ching, Feng, Shih-An, Chang, Chih-Tang
• Primary Examiner(s): Le; Debbie
• Assistant Examiner(s): MENG, JAU SHYA
• Application Number:
  US12/046,471
• Publication Number:
  US 20090172010A1
• Time in Patent Office: 1,133 Days
• Field of Search: None
• US Class Current: 707/758
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

A data classification system is provided. The data classification system includes a fetch unit, a classification tree module, and a data repository. The fetch unit is adapted for receiving data including at least one datum, and fetching a data information contained in the data. The classification tree module is adapted for classifying the data in a manner of a tree structure according to the data info illation, and building a classification tree thereby. The data repository is adapted for storing the classification tree and the data.

Claims

1. A data classification system, comprising:

a fetch unit, for receiving data including at least one datum, and fetching a data information contained in the data, wherein the data information comprises a coordinate information, and the coordinate information comprises a longitude and a latitude;

a classification tree module, for classifying the data in a manner of a tree structure according to the data information, and building a classification tree, wherein the classification tree comprises a plurality of nodes, each comprising a center position, a maximum distance of the data in the node to the center position; and

a data repository, for storing the classification tree and the data,

wherein the classification tree module obtains the data and adds it into a node, then calculates the center position of the node according to the coordinate information corresponding to the data, a distance of the coordinate information of each of the data to the center position, and obtains the maximum distance, thereafter determines whether the maximum distance is greater than a predetermined distance, if the maximum distance is greater than the predetermined distance, the classification tree module calculates a maximum longitude difference and a maximum latitude difference of the data according to the longitude and the latitude of each of the data, if the maximum longitude difference is greater than the maximum latitude difference the classification tree module arranges all data according to the longitudes thereof, and takes a longitude median of the data as a center to divide the node into a first sub-node and a second sub-node, and if the maximum longitude difference is smaller than the maximum latitude difference, the classification tree module arranges all data according to the latitudes thereof, and takes a latitude median of the data as a center to divide the node into the first sub-node and the second sub-node.

2. The data classification system according to claim 1, wherein the data information of the data comprises a building time, a type, a description, an importance ranking and a storage position reference information of the data.

3. The data classification system according to claim 1, wherein the classification tree comprises a data amount in the node, an importance ranking of the node, data listing in the node, a description of the node, and sub-nodes of the node.

4. The data classification system according to claim 1, wherein the data amount in the data is represented by a size of the node, and an importance ranking of the data is represented by different colors.

5. A method for building the classification tree, preformed by a data classification system configured with a classification tree module, the method comprising:

obtaining, by a processor, data including at least one datum, each of the data corresponding to a coordinate information, and the coordinate information comprises a longitude and a latitude of each of the data;

adding the data into a node;

calculating a center position of the node according to the coordinate information corresponding to the data;

calculating a distance of the coordinate information of each of the data to the center position, and obtaining a maximum distance;

determining whether the maximum distance is greater than a predetermined distance; and

dividing the node into a first sub-node and a second sub-node if the maximum distance is greater than the predetermined distance, and adding the data to one of the first sub-node and the second sub-node according to the coordinate information corresponding to each of the data, wherein the step of dividing the node into the first sub-node and the second sub-node comprises;

calculating a maximum longitude difference and a maximum latitude difference of the data according to the longitude and the latitude of each of the data;

arranging all data according to the longitudes thereof if the maximum longitude difference is greater than the maximum latitude difference, and taking a longitude median of the data as a center to divide the node into the first sub-node and the second sub-node; and

arranging all data according to the latitudes thereof if the maximum longitude difference is smaller than the maximum latitude difference, and taking a latitude median of the data as a center to divide the node into a first sub-node and a second sub-node.

6. The method for building the classification tree according to claim 5, wherein the step of determining whether the maximum distance is greater than the predetermined distance comprises a step of directly outputting a classification result if the maximum distance is not greater than the predetermined distance.

7. The method for building the classification tree according to claim 5, further comprising:

putting the node into an operation stack;

detecting whether there is a node in the operation stack; and

picking up a node from the operation stack if it is detected that there is the node in the operation stack, and conducting the step of calculating a center position of the node according to the coordinate information corresponding to the data.

8. The method for building the classification tree according to claim 7, wherein after the step of dividing the node into the first sub-node and the second sub-node further comprises a step of putting the first sub-node and the second sub-node into an operation stack.

9. The method for building the classification tree according to claim 7, further comprising:

adding a new datum into a node, wherein the new datum corresponds to a new coordinate information;

refreshing contents of the node;

determining whether the node includes a sub-node;

adding the new datum into the node if the node dose not include a sub-node;

calculating a new center position of the node after adding the new datum therein according to the coordinate information of each of the data and the new coordinate information corresponding to the new datum;

calculating distances from the coordinate information of each of the data and the new coordinate information corresponding to the new datum to the new center position, to obtain a new maximum distance;

determining whether the new maximum distance is greater than the predetermined distance;

dividing the node into the first sub-node and the second sub-node if the new maximum distance is greater than the predetermined distance, and putting the first sub-node and the second sub-node into the operation stack, and adding each of the data and the new datum into one of the first sub-node and the second sub-node according to the coordinate information of each of the data and the new coordinate information corresponding to the new datum;

determining whether there is a node in the operation stack; and

completing the adding of the new datum if there is no node in the operation stack.

10. The method for building the classification tree according to claim 9, wherein the step of determining whether the node includes a sub-node further comprises:

searching for a sub-node which is nearest to the new datum according to the new coordinate information if it is determined that the node includes a sub-node; and

returning to refreshing contents of the sub-node.

11. The method for building the classification tree according to claim 9, wherein the step of determining whether the new maximum distance is greater than the predetermined distance further comprises a step of completing the adding of the new datum if it is determined that the new maximum distance is not greater than the predetermined distance.

12. The method for building the classification tree according to claim 9, wherein the step of determining whether there is a node in the operation stack further comprises:

picking up the node from the operation stack if there is a node in the operation stack;

calculating a center position of the picked node according to the coordinate information corresponding to each of the data of the picked node;

calculating a distance of the coordinate information of each of the data to the center position of the picked node, so as to obtain the maximum distance;

determining whether the maximum distance is greater than the predetermined distance;

entering the step of dividing the node into the first sub-node and the second sub-node if it is determined that the maximum distance is greater than the predetermined distance, and putting the first sub-node and the second sub-node into the operation stack; and

entering the step of determining whether there is a node in the operation stack if it is determined that the maximum distance is not greater than the predetermined distance.

13. The method for building the classification tree according to claim 7 further comprising:

providing a restriction condition;

putting a node into an operation queue;

detecting whether there is a node in the operation queue;

picking up the node if there is the node in the operation queue;

detecting whether the node satisfies the restriction condition;

detecting whether the node includes a sub-node if it is detected that the node satisfies the restriction condition;

detecting whether the sub-node satisfies the restriction condition if it is detected that the node includes a sub-node; and

putting the sub-node of the node into the operation queue.

14. The method for building the classification tree according to claim 13, wherein the step of detecting whether the node includes a sub-node further comprises putting the node into a node listing if it is detected that the node does not include a sub-node.

15. The method for building the classification tree according to claim 13, wherein the step of detecting whether the sub-node satisfies the restriction condition further comprises a step of adding the node into a node listing if it is detected that the sub-node does not satisfy the restriction condition.

16. The method for building the classification tree according to claim 13, wherein the step of detecting whether there is a node in the operation queue further comprises a step of outputting nodes of a node listing if it is detected that there is no node in the operation queue.

17. The method for building the classification tree according to claim 7, further comprising:

putting a current node into an operation queue;

picking up a node from the operation queue;

putting a sub-node of the picked node into the operation;

detecting whether there are M nodes in the operation queue, wherein M is an integer greater than 0;

outputting all nodes in the operation queue to a node listing if there are M nodes in the operation queue; and

returning back to a step of picking up a node having most data from the operation queue if there are less than M nodes in the operation queue.

18. The method for building the classification tree according to claim 7, further comprising:

receiving a predetermined restriction condition;

fetching a data listing of a current node;

putting the data listing into a operation queue;

detecting whether there is a datum in the operation queue;

picking up the datum from the operation queue if it is detected that there is a datum in the operation queue;

detecting whether the datum satisfies the predetermined restriction condition; and

putting the datum into the data listing if the datum satisfies the predetermined restriction condition.

19. The method for building the classification tree according to claim 18, wherein the step of detecting whether there is a datum in the operation queue further comprises a step of completing a data listing if it is detected that there is no datum in the operation queue.

20. The method for building the classification tree according to claim 18, wherein the step of detecting whether the datum satisfies the predetermined restriction condition further comprises detecting whether there is a datum in the operation queue if it is detected that the datum does not satisfy the predetermined restriction condition.