Data processing: artificial intelligence – Fuzzy logic hardware
Reexamination Certificate
1998-05-13
2001-06-19
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Fuzzy logic hardware
C706S002000, C706S900000, C382S209000, C707S793000, C707S793000
Reexamination Certificate
active
06249779
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention related to pattern matching, and more specifically, to a method for recognizing and classifying a data pattern in a data stream by combining distance based functions and fuzzy logic techniques.
2. Related Art
Automation is becoming increasingly important in today's world and lifestyle. This is evidenced by the growth of computer networks, automatic transaction and service machines, and the vast number of daily business transactions handled electronically. All of these various business related events are typically monitored for various reasons, such as accuracy, security, marketing, inventory, scheduling, and the like. Therefore, there is a need for computer software to quickly, efficiently, and correctly identify patterns in data streams.
There are two principal methods for recognizing and classifying a data pattern in a single data stream. These methods are Fuzzy Adaptive Resonance Theory &Fuzzy ART) and Feature Mapping. Both methods are well-known and well published in the relevant arts. In summary, Fuzzy ART determines how close two patterns match each other by calculating the closeness, or fuzziness, of the fit, e.g., two patterns are a seventy-five percent (75%) match. With Fuzzy ART, a user can set the acceptable value, or degree, of fuzziness for determining a match. Thus, Fuzzy ART monitors a data stream for patterns and groups them together based on the percentage of similarity.
One disadvantage with Fuzzy ART is the fact that data patterns degrade over time. Conventional pattern matching systems, including Fuzzy ART, represent known data patterns as organized nodes wherein each organized node maintains a set of attribute coefficients defining a specific known data pattern. Therefore, when a new data pattern is identified in a new data stream, the new data pattern is compared against the known data patterns as represented by the organized nodes. If the new data pattern matches an organized node, the attribute coefficients of the matching organized node are updated to reflect the new data pattern. Because data patterns degrade overtime, the attribute coefficients of the organized node corresponding to the data pattern also degrade overtime until the organized node no longer accurately represents the data pattern. Eventually, the system must create a new organized node to represent the data pattern. Therefore, there is a need for a computer based system that identifies and classifies data patterns which minimizes the recreation of new organized nodes.
In contrast to fuzzy logic techniques, Feature Mapping is based on distance measurements. When a first pattern is identified, the pattern matching system of Feature Mapping assigns the patter to a point in N-dimensional space. A user then defines a radius around that point, thereby defining a perimeter of a cluster that corresponds to a specific data pattern wherein the first data pattern is the centroid of the cluster. Therefore, if a second pattern falls within the cluster as defined by the first pattern, then the second pattern matches the first pattern and belongs to the same cluster. If a point defining another pattern falls outside of the cluster, then a pattern is detected resulting in a new cluster being formed. As a cluster is defined by various points falling within the set radius, the detail of each data pattern is not lost because each pattern is maintained as a separate point in the cluster. Also, this method stabilizes the pattern identified by the cluster by moving the centroid of the circle according to the points defining the cluster. Thus, Feature Mapping monitors a data stream for patterns and groups them together based on the distance from the centroid of the cluster.
A disadvantage of Feature Mapping is the determination of a cluster's radius. Conventional systems use an arbitrary initial radius which is adjusted based on trial and error. Therefore, Feature Mapping may not accurately reflect a known data pattern because the chosen radius of the clusters may be incorrect.
A second disadvantage of Feature Mapping is the ease in which two data streams containing the same data pattern are misclassified as two different data patterns (each a separate cluster) due to a single simple difference between the data streams. For example, if there is one data stream containing a data pattern in which the signal has a spike up at the signal's end and there is a second data stream containing the same data pattern but the signal has a spike down at the signal's end, under Feature Mapping, these data patterns are classified in two different clusters, thereby determining that they are two separate data patterns. However, based on this scenario, the data patterns should be classified as the same data pattern. Therefore, there is a need for a computer based system that identifies and classifies data patterns which handles minor discrepancies between data patterns without identifying and classifying such minor differences as a new data pattern.
SUMMARY OF THE INVENTION
The present invention solves the problems associated with conventional methods of identifying and matching a new data pattern with known data patterns by combining distance based functionality and fuzzy logic techniques. Structurally, a known data pattern is represented by an organized node having one or more attribute coefficients which describe the known data pattern. A pattern map then groups together one or more such organized nodes. Therefore, in the present invention, when a new data pattern is received, the new data pattern is compared to each organized node (or known data patter) in a pattern map using distance measurement functions.
Once the comparisons are complete, the organized nodes are ranked within the pattern map according to their respective distance measurements. More specifically, the organized node having the shortest distance measurement received the highest ranking because that organized node is closest to matching the new data pattern. The order of ranking progresses according to the order of matching with the organized node having the longest distance measurement receiving the lowest ranking.
Once the ranking is complete, the new data pattern is again compared to the organized nodes of the pattern map. However, this time the comparison is performed according to the ranking of the organized nodes and using fuzzy logic techniques. The new data pattern is compared first to the organized node having the highest ranking, and so on in order, until the new data pattern is compared last to the organized node having the lowest ranking. If the new data pattern is determined to match an organized node during a comparison, the attribute coefficients for the corresponding organized node are updated to reflect the new data pattern. If the new data pattern does not match any of the organized nodes in the pattern map by using fuzzy logic techniques, a new organized node is created in the pattern map and assigned the attribute coefficients matching the new data pattern.
The principle advantage to the pattern matching technique of the present invention is the unique combination of using both distance measurement techniques and fuzzy logic functions in identifying and classifying a new data pattern. Further, the present invention requires less memory during operation and performs pattern matching with a high degree of accuracy.
REFERENCES:
patent: 5046019 (1991-09-01), Basehore
patent: 5127063 (1992-06-01), Nishiya et al.
patent: 5499319 (1996-03-01), Sultan et al.
patent: 5515477 (1996-05-01), Sutherland
patent: 5531227 (1996-07-01), Schneider
patent: 5537330 (1996-07-01), Damiano et al.
patent: 5606690 (1997-02-01), Hunter et al.
patent: 5638460 (1997-06-01), Nishimori et al.
patent: 5706497 (1998-01-01), Takahashi et al.
patent: 6018735 (2000-01-01), Hunter et al.
Liu et al, “Finding Interesting Patterns Using User Expectations”, IEEE Transactions on Knowledge and Data Engineering, Nov./Dec. 1999.*
Wu et al, “Facial Image Retrieval Identification and Interfere
Davis George B.
Steptoe & Johnson PLLC
LandOfFree
Adaptive fuzzy feature mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive fuzzy feature mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive fuzzy feature mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453789