Systems and methods for real-time determination of the semantics of a data stream
AssigneeFair Isaac Corporation
InventorsJohn Byrnes, Richard Rohwer
Life of this patent
Estimating the term…
Abstract
The present invention is directed to a method and method which analyzes large amounts of information on a real-time basis with no previous static data set. Attributes of the data, which can be thought of as data concepts, that are present in the data stream are detected and isolated. These concepts are referred to as clusters and are used to ultimately determine the semantics of the data stream. The streaming clusters have no “current membership” in the existing state of the clustering and thus the cluster sets, and their relationship to each other, must be generated and updated as the data is being received.
Claims23
A method for determining the semantics of a data stream, said determining performed by a computer, comprising:
- determining in real-time clusters of similar data flows in a data stream;
- determining simultaneously in real-time a word mapping table (WMT) defining clusters of data objects used similarly by said clustered data flows by simultaneously finding a partition with respect to said similarly used clustered data objects and a partition with respect to said similar data stream;
- wherein said simultaneous partition defines a cluster of similar data flows as containing similarly used data objects and defines similarly used data objects as occurring in similar data flows;
- using a score table to compute a change in mutual information resulting from adding a set of input data to a particular cluster;
- adding the set of input data to the particular cluster based on the change in mutual information;
- updating the score table in response to adding the set of input data to the particular cluster;
- wherein adding the set of input data to the particular cluster comprises:
- assigning the input data to a best cluster with probability AA and assigning said data to a second best cluster with the probability of BB, where AA and BB are determined by the mutual information that would result from insertion into the best or second best clusters, respectively, and
- determining the semantics of said data stream using said computed WMT and said flow clusters.
A system for organizing data streams into clusters, said system comprising:
- means for receiving a data stream;
- means for converting each document to a vector;
- means for placing each document in at least one proper document cluster having a particular profile, based, at least in part, on an agreement between the document vector and an existing cluster profile, wherein the agreement is assessed based on a change in mutual information resulting from placing the document in the at least one proper document cluster,
- wherein placing each document in at least one proper document cluster comprising:
- assigning each document to a best cluster with probability AA and assigning said document to a second best cluster with the probability of BB, where AA and BB are determined by the mutual information that would result from insertion into the best or second best clusters, respectively,
- wherein said cluster profile is continually updated in real-time with information from newly arrived documents in said data stream to reflect existing documents in said at least one cluster and newly arrived documents;
- said clusters developed in real-time as said documents are being received such that the number of clusters is based, at least, on documents in the data stream.
A method for separating data streams into clusters, said separating performed by a computer, said method comprising:
- assembling real-time data from a received data stream into a document representation;
- converting each document representation to a vector;
- computing an inner product for each said document vector;
- determining scores for each computed inner value of said document vector;
- storing said computed inner products and said determined scores by a score table;
- developing real-time document clusters of similar data received from said data stream in real-time, wherein said developing is based at least in part on said score table;
- placing in real-time each document in a proper document cluster based on a change in mutual information resulting from adding the document to the proper document cluster;
- wherein placing in real time each document in at least one proper document cluster comprising:
- assigning each document to a best cluster with probability AA and assigning said document to a second best cluster with the probability of BB, where AA and BB are determined by the mutual information that would result from insertion into the best or second best clusters, respectively;
- updating said score table in response to placing each document into its respective proper cluster;
- and
- determining whether to downscale said clusters, wherein said downscale determination comprises comparing the determined scores in said score table to a pre-defined condition to reduce data in use by said score table.
Dependencies are inferred from the claim text.