Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-19
2003-09-02
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06615211
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to data exploration and analysis techniques and, in particular, to systems and methods for ordering and visualizing categorical data for use in such data exploration and analysis techniques.
BACKGROUND OF THE INVENTION
Visual representation has become increasingly important in conveying and interpreting information from a large amount of data. This is because it is known that human visual perception is remarkably good at identifying interesting patterns and spatial relationships. Good, effective visual representation can present information in a way that maximally exploits our visual skills so as to reveal interesting trends and anomalies hidden in data. A large number of data attributes in real data sets are categorical. A categorical value conveys the category of an object. There is typically neither a natural order nor distances associated with categorical values. For example, consider a data set representing a temporal sequence of events with such attributes as host name, event name, event severity. Although we can arguably define a meaningful order of event severity, there is no natural way of defining distances and an order of host names and event names.
While considerable research has been done on visualizing numerical data by directly leveraging its inherent geometric properties in constructing a visualization, there has been much less work on visualizing and extracting a structure in categorical data. Clearly, the lack of an order of attribute values adds additional complexity. This is because there are exponentially many ways in which the categorical values can be totally ordered. However, it is unlikely that all such orders produce equally effective visualizations. Ma and Hellerstein identified the problem and showed that the quality of the ordering algorithm is crucial for effectively visualizing categorical data, see U.S. patent application identified by Ser. No. 09/422,708, filed on Oct. 21, 1999 in the names of S. Ma and J. L. Hellerstein and entitled “Systems and Methods for Ordering Categorical Attributes to Better Visualize Multidimensional Data,”; S. Ma and J. L. Hellerstein, “Ordering categorical data to improve visualization,” Proceedings of the IEEE Symposium on Information Visualization, 1999; and S. Ma and J. L. Hellerstein, “EventBrowser: exploratory analysis of event data for event management,” DSOM 1999, the disclosures of which are incorporated by reference herein.
To illustrate the importance of ordering categorical values, we consider the same data set as used by Ma and Hellerstein in the above-referenced disclosures. The data set contains over 10,000 events generated by 160 hosts with 20 event types over a three-day period.
FIG. 1
shows a scatter plot of the data set, in which the x-axis and the y-axis represent the time and the host name (e.g., an identifier (id) of a host in a network of computing devices) of an event, respectively. In this plot, since host names are categorical, they must somehow be mapped to geometric coordinates (on the y-axis). The order of host names in
FIG. 1
is a random permutation of host names. Unfortunately, the scatter plot of
FIG. 1
produces results that are not particularly revealing because of the random ordering scheme. Thus, it is evident that some better ordering or mapping is required to provide a higher quality visualization of the data set.
A key issue addressed by Ma and Hellerstein in the above-referenced disclosures, which is also a focus of the present invention, is how to find a mapping that results in an effective visualization. Clearly, a guiding principle behind the construction of such a mapping is to utilize the geometric proximity to capture relationships between objects. That is, we want similar, related objects to be placed close to each other.
Numerous research efforts and commercial products have applied visualization techniques to categorical data sets, e.g., M. O. Ward, “XmdvTool: Integrating multiple methods for visualizing multivariate data,” Proceedings of the Conference on Visualization (Los Alamitos, Calif., USA) IEEE Computer Society Press, pp. 326-336, October 1994; Diamond software from IBM Corporation; and U.S. patent application identified by Ser. No. 09/359,874, filed on July 27, 1999, and entitled “Systems and Methods for Exploratory Analysis of Data for Event Management,” the disclosures of which are incorporated by reference herein. Such efforts can be classified into four classes.
One simple approach is to order categorical values based on an auxiliary numerical attribute or to order the values alphabetically. In our previous example, we can order host names by the time of their first occurrence in the data set. This approach is based on the assumption that there is some causality in the order of events generated by a system. However, this approach is not related to a visual task, and thus can not, in general, provide the best visualization quality. The performance associated with this approach gets worse as the size and the complexity of the data set grows.
The second class is mostly focused on clustering-based approaches, see, e.g., V. Ganti et al., “CACTUS: Clustering categorical data using summaries,” Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM Press, pp. 73-83, August 1999; D. Gibson et al., “Clustering categorical data: An approach based on dynamic systems,” Proceedings of the 24th International Conference on Very Large Data Bases, VLDB, pp. 311-322, August 1998; S. Guha et al, “Rock: a robust clustering algorithm for categorical attributes,” Proc. of the 15th Int. Conf. on Data Eng., 1999; and S. Ma and J. L. Hellerstein, “Ordering categorical data to improve visualization,” Proceedings of the IEEE Symposium on Information Visualization, 1999, the disclosures of which are incorporated by reference herein.
Clustering is a natural way of getting an insight into the data set. However, three issues effect its value for visualization purposes. First, although clusters can be identified in the geometric space, cluster descriptions are still unordered, and some additional nontrivial methods are needed to order and visualize the clusters, and to order and visualize the elements within each cluster. Second, most clustering algorithms prefer certain, usually very structured cluster shapes (e.g., rectangular regions of the above-referenced CACTUS approach), and always tend to partition the data into clusters of such shapes even though there may be no clustering tendency in the data set at all. In particular, the CACTUS approach showed that the above-referenced Gibson approach is not able to discover several natural classes of clusters, such as clusters with overlapping projections on some subset of attributes. We feel that making any assumption about the clustering structure of the data defeats the whole purpose of using clustering algorithms to extract structures. The present invention is directed toward techniques for revealing the order without imposing any prior assumption on the data. To do so, the present invention formulates the problem using an optimization framework.
Related to the second class of algorithms, the third approach proposed in the above-referenced U.S. patent application identified by Ser. No. 09/359,874, is based on hierarchical ordering. The approach provides for iteratively grouping the closest pair of points (in respect to some similarity function) and replaces the pair by a single point. The points are thus fashioned into a strict hierarchy of nested ordered subsets. The length of the shortest path between any two subsets corresponds to the degree of their similarity. Constructing a global ordering reduces to locally ordering pairs of subsets recursively in a bottom-up fashion. In this approach, a strict hierarchical tree can not reflect the multiple different ways in which points can be related, and this situation gets more severe as the size and the complexity of the data grow. Second, the hierarchical ordering is determini
Beygelzimer Alina
Hellerstein Joseph L.
Ma Sheng
Perng Chang-shing
Amsbury Wayne
Ryan & Mason & Lewis, LLP
Zarick Gail H.
LandOfFree
System and methods for using continuous optimization for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and methods for using continuous optimization for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and methods for using continuous optimization for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3006602