Machine discovery and rapid agglomeration of similar states

• US 10,346,756 B2
• Filed: 12/11/2017
• Issued: 07/09/2019
• Est. Priority Date: 01/25/2017
• Status: Active Grant

• Current Assignee: CenturyLink Intellectual Property LLC (Lumen Technologies, Inc.)
• Original Assignee: CenturyLink Intellectual Property LLC (Lumen Technologies, Inc.)
• Inventors: Kirk, Ryan, Sletten, Victor
• Primary Examiner(s): Vincent, David R
• Application Number:
  US15/838,098
• Publication Number:
  US 20180211172A1
• Time in Patent Office: 575 Days
• Field of Search: 706 15, 706 45
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Novel tools and techniques for the machine discovery and rapid agglomeration of similar states are provided. A system includes a plurality of network devices, and a decision system. The plurality of network devices may be configured to generate a respective data stream. The decision system may include a processor and a non-transitory computer readable medium including instructions executable by the processor. The system may obtain, via the plurality of network devices, one or more data streams, determine an anomaly has occurred on a data stream of the one or more data streams, determine a set of data streams of the one or more streams sharing at least one of a set of centroids associated with the data stream, and determine, based on the set of data streams, the occurrence of an incident.

Claims

1. A system comprising:

a plurality of network devices associated with a cloud platform, each network device of the plurality of network devices configured to generate a respective data stream in real-time, each data stream including a sequence of data points indicative of a value of a performance metric at an associated time;

a decision system in communication with the plurality of network devices, the decision system comprising;

a processor;

a non-transitory computer readable medium comprising instructions executable by the processor to;

obtain, via the plurality of network devices, one or more data streams, each of the one or more data streams comprising real-time time-series data indicative of a network activity generated by a respective network device;

determine a set of data streams of the one or more streams sharing at least one of a set of centroids associated with a data stream;

generate a search vector of the data stream; and

determine a match rate between the search vector a set of target vectors, wherein determining the match rate includes determining a number of times each target vector shares a centroid of the set of centroids with the search vector; and

determine, based on the set of data streams, the occurrence of an incident.

2. The system of claim 1, wherein the instructions are further executable by the processor to:

define one or more buckets;

associate each of the one or more data streams with a respective bucket, based on respective identifying information of each of the one or more data streams;

separate each of the one or more data streams into a respective set of one or more data stream segments, each data stream segment associated with a respective time interval; and

determine a respective set of centroids for each bucket of the one or more buckets during a first time interval, based on all data segments in a respective bucket associated with the first time interval.

3. The system of claim 1, wherein the instructions are further executable by the processor to:

determine the set of centroids associated with the data stream;

determine a centroid associated with a data segment of the data stream at the first time interval;

identify a set of target vectors sharing the centroid of the data stream at the first time interval.

4. The system of claim 3, wherein the instructions are further executable by the processor to:

determine an anomaly has occurred on the data stream of the one or more data streams;

wherein the anomaly occurs during the first time interval.

5. The system of claim 1, wherein the instructions are further executable by the processor to:

remove, from the set of target vectors, any target vector with a match rate below a threshold value.

6. The system of claim 5, wherein the instructions are further executable by the processor to:

determine a set of neighboring vectors for each target vector of the set of target vectors, wherein the set of neighboring vectors includes neighboring vectors with a match rate above the threshold value for each respective target vector of the set of target vectors.

7. The system of claim 1, wherein the instructions are further executable by the processor to:

determine one or more connections of the data stream to one or more neighbors, and from the one or more neighbors to one or more neighbors of neighbors, wherein the one or more neighbors are data streams associated with the set of target vectors, and the one or more neighbors of neighbors are data streams associated with the set of neighboring vectors;

establish a threshold for the one or more connections based on at least one of the match rate, a correlation coefficient, or statistical significance;

generate a directed graph of the one or more connections satisfying the threshold;

determine strongly connected components within the directed graph based, at least in part, on a breadth-first search with a backtracking search phase; and

remove connections of the one or more connections that are not between strongly connected components.

8. The system of claim 1, wherein the instructions are further executable by the processor to:

determine a type of incident based on the set of data streams; and

perform a remedial action based on the type of incident.

9. The system of claim 1, wherein the instructions are further executable by the processor to:

receive analyst feedback indicative of whether the presence of the at least one of the set of centroids is associated with the incident; and

determine whether to associate the presence of the at least one of the set of centroids within the set of data streams with the incident, based on the analyst feedback.

10. An apparatus comprising:

a processor;

a non-transitory computer readable medium comprising instructions executable by the processor to;

obtain, via the plurality of network devices, one or more data streams, each of the one or more data streams comprising real-time time-series data indicative of a network activity generated by a respective network device;

determine a set of data streams of the one or more streams sharing at least one of a set of centroids associated with a data stream;

generate a search vector of the data stream;

determine a match rate between the search vector a set of target vectors, wherein determining the match rate includes determining a number of times each target vector shares a centroid of the set of centroids with the search vector; and

remove, from the set of target vectors, any target vector with a match rate below a threshold value; and

determine, based on the set of data streams, the occurrence of an incident.

11. The apparatus of claim 10, wherein the instructions are further executable by the processor to:

define one or more buckets;

associate each of the one or more data streams with a respective bucket, based on respective identifying information of each of the one or more data streams;

separate each of the one or more data streams into a respective set of one or more data stream segments, each data stream segment associated with a respective time interval; and

determine a respective set of centroids for each bucket of the one or more buckets during a first time interval, based on all data segments in a respective bucket associated with the first time interval.

12. The apparatus of claim 10, wherein the instructions are further executable by the processor to:

determine a centroid of the set of centroids associated with a first time interval;

identify a set of target vectors sharing the centroid of the data stream at the first time interval.

13. The apparatus of claim 12, wherein the instructions are further executable by the processor to:

determine an anomaly has occurred on the data stream of the one or more data streams;

wherein the anomaly occurs during the first time interval.

14. The apparatus of claim 13, wherein the instructions are further executable by the processor to:

determine one or more connections of the data stream to one or more neighbors, and from the one or more neighbors to one or more neighbors of neighbors, wherein the one or more neighbors are data streams associated with the set of target vectors, and the one or more neighbors of neighbors are data streams associated with the set of neighboring vectors;

establish a threshold for the one or more connections based on at least one of the match rate, a correlation coefficient, or statistical significance;

generate a directed graph of the one or more connections satisfying the threshold;

determine strongly connected components within the directed graph based, at least in part, on a breadth-first search with a backtracking search phase; and

remove connections of the one or more connections that are not between strongly connected components.

15. A method comprising:

obtaining, via a decision support system, via the plurality of network devices, one or more data streams, each of the one or more data streams comprising real-time time-series data indicative of a network activity generated by a respective network device;

determining, via the decision support system, a set of data streams of the one or more streams sharing at least one of a set of centroids associated with the data stream;

generating, via the decision support system, a search vector of the data stream;

determining, via the decision support system, a match rate between the search vector a set of target vectors, wherein determining the match rate includes determining a number of times each target vector shares a centroid of the set of centroids with the search vector;

determining, via the decision support system, one or more connections of the data stream to one or more neighbors, and from the one or more neighbors to one or more neighbors of neighbors, wherein the one or more neighbors are data streams associated with the set of target vectors, and the one or more neighbors of neighbors are data streams associated with the set of neighboring vectors;

establishing, via the decision support system, a threshold for the one or more connections based on at least one of the match rate, a correlation coefficient, or statistical significance;

generating, via the decision support system, a directed graph of the one or more connections satisfying the threshold;

determining, via the decision support system, strongly connected components within the directed graph based, at least in part, on a breadth-first search with a backtracking search phase; and

removing, via the decision support system, connections of the one or more connections that are not between strongly connected components;

determining, via the decision support system, based on the set of data streams, the occurrence of an incident; and

performing, via the decision support system, a remedial action based on one of a type of the incident, the data stream, or the set of data streams.

16. The method of claim 15, further comprising:

defining, via the decision support system, one or more buckets;

associating, at the decision support system, each of the one or more data streams with a respective bucket, based on respective identifying information of each of the one or more data streams;

separating, via the decision support system, each of the one or more data streams into a respective set of one or more data stream segments, each data stream segment associated with a respective time interval; and

determining, via the decision support system, a respective set of centroids for each bucket of the one or more buckets during a first time interval, based on all data segments in a respective bucket associated with the first time interval.

17. The method of claim 15, further comprising:

determining, via the decision support system, a centroid of the set of centroids associated with a first time interval;

identifying, via the decision support system, a set of target vectors sharing the centroid of the data stream at the first time interval.