Microsoft Technology Licensing, LLC

Revenue Science, Inc.

Usama M Fayyad

Paul S Bradley

Cory Alan Reina

Cheng Yong Yang

Neal Rothleder

Surajit J Chaudhuri

Stella Yick Chan

Jayavel Shanmugasundaram

Bassel Ojjeh

David Earl Heckerman

Christopher A Meek

David Maxwell Chickering

Radha Krishna Uppala

Christos Faloutsos

Dan Geiger

Demetrios Achlioptas

Jeff R Bernhardt

Kristin P Bennett

Goetz Graffe

Paul Bradley

Data mining for managing marketing resources is disclosed. In one embodiment, a method for managing a marketing campaign includes the following. First, the method provides a data mining engine capable of being trained with training data and capable thereof of performing inference relative to the training data and on future data. Next, the method provides a user database defining observed characteristics of each one of a set of users. The characteristics include at least one of one or more user's attributes, and one or more of the user's preferences. Finally, the data mining engine is trained with a set of training data comprising the user data base, and a predetermined characteristic pertaining to the market campaign is input to the engine, such that, in response to the input, a subset of the users in the database is obtained that have the highest correlation to the characteristic.

Data mining for managing marketing resources

A facility for identifying groups of items that co-occur in more than a threshold number of instances is described. Each such group of items has a size reflecting the number of items in the group. The facility uses a data structure comprising, for each of a plurality of group sizes, a single map identifying groups of that group size that co-occur in more than a threshold number of instances.

Optimized a priori techniques

A method, system, and computer-readable medium for identifying sequences of interaction events of interest that frequently occur is described. In particular, techniques are described for receiving multiple groups each having related interaction events in serial or sequential order, and for determining sequences of interaction events that frequently occur in the multiple groups. Reports can also be generated and provided that include information about the determined frequent sequences. The techniques can at times be used to provide a service to customers in which logs containing data about interaction events related to that customer (e.g., usage events for a provided service or of a provided Website) are received or obtained, in which frequent sequences in the log data are identified, and in which reports are provided to representatives of the customer about the frequent sequences (e.g., remotely over the Web based on interactive specifications).

Identifying and reporting on frequent sequences of events in usage data

A software facility for analyzing each of a plurality of groups of items is described. The facility retrieves information identifying, for each of a plurality of groups, items that are members of the group. For each group, the facility analyzes attributes of the items of the group to identify attributes that distinguish items that are members of the group from items that are not members of the group.

Visualizing automatically generated segments

Method of reducing dimensionality of a set of attributes used to characterize a sparse data set

Retrofitting recommender systems, so that they can scale to large data, is disclosed. The principal notion is to reduce data requirements of existing recommender engines by performing a type of data reduction that minimizes the loss of information given the engine. The reductions covered in this invention are designed to be easily implemented on a database system, and are intended to have minimal impact on an existing implementation of a recommender system. In one embodiment, a method repeats reducing the data by a number of records, until an accuracy threshold or a performance requirement is met. If the accuracy threshold is met first, the method repeats removing a highest-frequency dimension from the data, until the performance requirement is also met. The reduced data is provided to the recommender system, which generates predictions based on the reduced data, and a query. Any dimension previously removed from the data is subsequently added back to the predictions, if the dimension is not already part of the query. In other embodiments, clustering of the data and/or the query is also performed as an alternative mechanism for reduction. An associated method for post-processing recommendations to adjust for clustering is also presented.

Retrofitting recommender system for achieving predetermined performance requirements

Apparatus and method for use in querying a database containing data records. The database is characterized by a compression scheme to provide data clustering information. In accordance with a exemplary embodiment of the invention a functional representation of data clustering is a Gaussian and the queries are performing by integrating the Gaussian corresponding to each of the data clusters over the ranges to determine the sum or the count of data records from the database that fall within the selected ranges. The process chooses a value for the cluster number K. The cluster model is next broken up into areas (tiles) based on user defined parameters. Data from the database is then classified based on the tiling information. A sorted version of the classified data, ordered by cluster number and then by the tile number within the cluster is generated. This data is then evaluated to test the sufficiency of the model created during the clustering.

Multi-dimensional database record compression utilizing optimized cluster models

One exemplary embodiment of a scalable clustering algorithm accesses a database of records having attributes or data fields of both enumerated discrete and ordered values and brings a portion of the data records into a rapid access memory. A cluster model for the data includes a table of probabilities for the enumerated, discrete data fields of the data records. The cluster model for data fields that are ordered comprises a mean and spread of the cluster. The cluster model is updated from the database records brought into the rapid access memory. At least some of the database records in the rapid access memory are summarized and stored within the rapid access memory. A criteria is then evaluated to determine if further data should be accessed from the database to further cluster data records in the database. Based on the evaluating step, additional database records in the database are accessed and brought into the rapid access memory for further updating of the cluster model.

Scalable system for clustering of large databases having mixed data attributes

A generalization of frequent item sets to error-tolerant frequent item sets (ETF) is disclosed, together with its application in data clustering using error-tolerant frequent item sets to either build clusters or as an initialization technique for standard clustering algorithms. Efficient feasible computational algorithms for computing ETF's from very large databases is presented. In one embodiment, a method determines a plurality of weak ETF's, which are strongly tolerant of errors, and determines a plurality of strong ETF's therefrom, which are less tolerant of errors. The resulting clusters can be used as an initial model for a standard clustering approach, or may themselves be used as the end clusters. In one embodiment, the data covered by the strong clusters is removed from the data, and the process is repeated, until no more weak clusters can be found. Te invention includes methods for constructing ETF's from more general data types: data sets that include categorical discrete, continuous, and binary attributes.

Data clustering using error-tolerant frequent item sets

An apparatus and method for efficiently compressing contents of a database system to support ad hoc querying and OLAP type aggregation queries. This invention consists of a new compressed representation of the data cube that (a) drastically reduces storage requirements, (b) does not require the discretization hierarchy along each query dimension to be fixed beforehand and (c) treats each dimension as a potential target measure and supports multiple aggregation functions without additional storage costs. The tradeoff is approximate, yet relatively accurate, answers to queries. We outline mechanisms to reduce the error in the approximation. Our performance evaluation indicates that our compression technique effectively addresses the limitation of existing approaches. The basic method relies on representing the contents of the database by a probability distribution consisting of a mixture of Gaussians. Aggregation queries, be they multi-dimensional, conjunctive, or disjunctive, can be answered by performing integration over the probability distribution.

Multi-dimensional database and data cube compression for aggregate query support on numeric dimensions

Method and apparatus for displaying and navigating data organized in the form of a graph structure (hierarchy or network) is presented. The invention has application for displaying a system of interconnected nodes such as a graph, a network, an organizational chart, a flowchart etc. wherein data or information is associated with nodes of the system. A user interface is implemented as an ActiveX control having a viewer component for displaying and navigating graph structur (for example a data mining model over data records or a directory structure over a set of files). The viewer component updates the contents of related windows that display different aspects of the components (nodes) of the data structure. A thumbnail window presents the user with an overview of the data structure. A layout window presents a more detailed view of part of the graph structure. Other windows display context and detailed properties associated with particular selected nodes. One instance of the invention is used for displaying structure of a database classifier which organizes data in a tree. A tree viewer maintains a depiction of the entire graph (or tree) in the Thumbnail window and depicts a detailed portion of the graph in a larger layout window. The user can move the mouse pointer over either the thumbnail or the layout window and by mouse actuated inputs can control the manner in which the window depicts the tree structure. Color coding of properties of the structure being displayed, along with auxiliary detail windows for displaying values and histograms, can be used to quickly navigate a large structure and locates zones of interest within it.

Method and apparatus for visualizing and exploring large hierarchical structures

Iterative validation for efficiently determining error-tolerant frequent itemsets is disclosed. A description of the application of error-tolerant frequent itemsets to efficiently determining clusters as well as initializing clustering algorithms are also given. In one embodiment, a method determines a sample set of error-tolerant frequent itemsets (ETF's) within a uniform random sample of data within a database. This sample set of ETF's is independently validated, so that, for example, spurious ETF's and spurious dimensions within the ETF's can be removed. The validated sample set of ETF's, is added to the set of ETF's for the database. This process is repeated with additional uniform samples that are mutually exclusive from prior uniform samples, to continue building the database's set of ETF's, until no new sample sets can be found. The method is significantly more efficient than disk-based methods in the prior art, and the data clusters found are often not discovered by traditional clustering algorithm in the prior art.

Iterative validation and sampling-based clustering using error-tolerant frequent item sets

In one exemplary embodiment the invention provides a data mining system for use in finding cluster of data items in a database or any other data storage medium. A portion of the data in the database is read from a storage medium and brought into a rapid access memory buffer whose size is determined by the user or operating system depending on available memory resources. Data contained in the data buffer is used to update the original model data distributions in each of the K clusters in a clustering model. Some of the data belonging to a cluster is summarized or compressed and stored as a reduced form of the data representing sufficient statistics of the data. More data is accessed from the database and the models are updated. An updated set of parameters for the clusters is determined from the summarized data (sufficient statistics) and the newly acquired data. Stopping criteria are evaluated to determine if further data should be accessed from the database. Each time the data is read from the database, a holdout set of data is used to evaluate the model then current as well as other possible cluster models chosen from a candidate set of cluster models. The evaluation of the holdout data set allows a cluster model with a different cluster number K&prime; to be chosen if that model more accurately models the data based upon the evaluation of the holdout set.

Varying cluster number in a scalable clustering system for use with large databases

A data mining system for use in finding clusters of data items in a database or any other data storage medium. The clusters are used in categorizing the data in the database into K different clusters within each of M models. An initial set of estimates (or guesses) of the parameters of each model to be explored (e.g. centriods in K-means), of each cluster are provided from some source. Then a portion of the data in the database is read from a storage medium and brought into a rapid access memory buffer whose size is determined by the user or operating system depending on available memory resources. Data contained in the data buffer is used to update the original guesses at the parameters of the model in each of the K clusters over all M models. Some of the data belonging to a cluster is summarized or compressed and stored as a reduced form of the data representing sufficient statistics of the data. More data is accessed from the database and the models are updated. An updated set of parameters for the clusters is determined from the summarized data (sufficient statistics) and the newly acquired data. Stopping criteria are evaluated to determine if further data should be accessed from the database. If further data is needed to characterize the clusters, more data is gathered from the database and used in combination with already compressed data until the stopping criteria has been met.

Scalable system for clustering of large databases

Method and apparatus for efficiently performing nearest neighbor queries on a database of records wherein each record has a large number of attributes by automatically extracting a multidimensional index from the data. The method is based on first obtaining a statistical model of the content of the data in the form of a probability density function. This density is then used to decide how data should be reorganized on disk for efficient nearest neighbor queries. At query time, the model decides the order in which data should be scanned. It also provides the means for evaluating the probability of correctness of the answer found so far in the partial scan of data determined by the model. In this invention a clustering process is performed on the database to produce multiple data clusters. Each cluster is characterized by a cluster model. The set of clusters represent a probability density function in the form of a mixture model. A new database of records is built having an augmented record format that contains the original record attributes and an additional record attribute containing a cluster number for each record based on the clustering step. The cluster model uses a probability density function for each cluster so that the process of augmenting the attributes of each record is accomplished by evaluating each record's probability with respect to each cluster. Once the augmented records are used to build a database the augmented attribute is used as an index into the database so that nearest neighbor query analysis can be very efficiently conducted using an indexed look up process. As the database is queried, the probability density function is used to determine the order clusters or database pages are scanned. The probability density function is also used to determine when scanning can stop because the nearest neighbor has been found with high probability.

Growing community of inventors

Mercer Island, WA, United States of America

Usama M Fayyad