Scalable system and method for real-time predictions and anomaly detection

• US 10,846,610 B2
• Filed: 08/08/2016
• Issued: 11/24/2020
• Est. Priority Date: 02/05/2016
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kutzkov, Konstantin, Niepert, Mathias, Ahmed, Mohamed
• Primary Examiner(s): Lo, Ann J
• Assistant Examiner(s): Mang, Van C
• Application Number:
  US15/230,517
• Publication Number:
  US 20170228660A1
• Time in Patent Office: 1,569 Days
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06Q 30/0251 Targeted advertisements

Abstract

A method detects an event or anomaly in real-time and triggers an action based thereon. A stream of data is received from data sources. The data includes at least two categorical features and a real-value measurement. Sketching is performed on the features using min-wise hashing to create sketches of the data. A regression tree is learnt on the sketches so as to estimate a mean squared error. It is determined whether an event or anomaly exists based on the mean squared error. An action is triggered based on at least one of a type, location or magnitude of the determined event or anomaly.

Claims

1. A method for detecting an event or anomaly in real-time and for triggering an action based thereon, the method comprising:

receiving a stream of data from data sources, the data including at least two categorical features and a real-value measure;

performing sketching on the categorical features using min-wise hashing to create sketches of the data;

learning a regression tree on the sketches so as to minimize a desired loss function;

determining whether the event or anomaly exists; and

triggering the action based on at least one of a type, location or magnitude of the determined event or anomaly.

2. The method according to claim 1, wherein the desired loss function is a mean squared error, wherein the regression tree is built starting with a tree consisting of a single node which stores the data, wherein each leaf node comprises a mean of the real-value measures, and wherein the leaf nodes are split by partitioning the data based on the categorical features until a reduction of the mean squared error above a predetermined threshold is no longer achievable.

3. The method according to claim 2, wherein boosting is applied to the regression tree.

4. The method according to claim 1, further comprising updating the sketches and learning regression trees on the updated sketches.

5. The method according to claim 1, further comprising estimating, from the sketches, a generalized Jaccard similarity for a given profile and a size of a union sets that define the given profile.

6. The method according to claim 1, wherein the method is used in a crowd detection system, wherein the categorical features include at least a time and a location and the real-value measure includes a number of detected objects or persons, wherein the event or anomaly is a crowd, and wherein the action includes at least one of:

sending an alert to a public office or official;

automatically opening or closing a road, on-ramp or intersection;

remotely controlling traffic signals and traffic signs;

triggering an alarm;

or

sending alternative directions to a navigation-enabled device.

7. The method according to claim 1, wherein the method is used in a recommendation system, wherein the categorical features include at least a user category and a content-type category and the real-value measure includes a user rating, and wherein the action includes at least one of:

sending a targeted advertisement to a user;

making a recommendation to the user for a particular type of content;

or

triggering an alert.

8. The method according to claim 1, wherein the method is used in a flight management system, wherein the categorical features include at least a time and a location and the real-value measure includes a flight delay length, and wherein the action includes at least one of:

transmitting instructions to reroute a flight;

rescheduling flight departure times;

or

changing arrival gates.

9. The method according to claim 1, wherein the method is used in a weather station, wherein the categorical features include at least a time and a location and the real-value measure includes a temperature, and wherein the action includes transmitting a weather alert.

10. The method according to claim 1, wherein the regression tree is incrementally built by providing the sketches for each of the categorical features as input to a regression tree algorithm which splits leaf nodes depending on estimates of mean squared error from the sketches for each of the categorical features.

11. A system for detecting an event or anomaly in real-time and for triggering an action based thereon, the system comprising at least one server or processor configured to:

receive a stream of data from data sources, the data including at least two categorical features and a real-value measure;

perform sketching on the categorical features using min-wise hashing to create sketches of the data;

learn a regression tree on the sketches so as to minimize a desired loss function;

determine whether the event or anomaly exists; and

trigger the action based on at least one of a type, location or magnitude of the determined event or anomaly.

12. The system according to claim 11, wherein the system is a crowd detection system, wherein the categorical features include at least a time and a location and the real-value measure includes a number of detected objects or persons, wherein the event or anomaly is a crowd, and wherein the actions include at least one of:

sending an alert to a public office or official;

automatically opening or closing a road, on-ramp or intersection;

remotely controlling traffic signals and traffic signs;

triggering an alarm;

or

sending alternative directions to a navigation-enabled device.

13. The system according to claim 11, wherein the system is a recommendation system, wherein the categorical features include at least a user category and a content-type category and the real-value measure includes a user rating, and wherein the actions include at least one of:

sending a targeted advertisement to a user;

making a recommendation to the user for a particular type of content;

or

triggering an alert.

14. The system according to claim 11, wherein the system is a flight management system, wherein the categorical features include at least a time and a location and the real-value measure includes a flight delay length, and wherein the actions include at least one of:

transmitting instructions to reroute a flight;

rescheduling flight departure times;

or

changing arrival gates.

15. The system according to claim 11, wherein the system is part of a weather station, wherein the categorical features include at least a time and a location and the real-value measure includes a temperature, and wherein the action includes transmitting a weather alert.

16. A tangible, non-transitory computer medium having instructions thereon which when run on at least one processor or server cause the following steps to be performed:

receiving a stream of data from data sources, the data including at least two categorical features and a real-value measure;

performing sketching on the categorical features using min-wise hashing to create sketches of the data;

learning a regression tree on the sketches so as to minimize a desired loss function;

determining whether the event or anomaly exists; and

triggering the action based on at least one of a type, location or magnitude of the determined event or anomaly.