System and method for load shedding in data mining and knowledge discovery from stream data
View Patent ↗Load shedding schemes for mining data streams. A scoring function is used to rank the importance of stream elements, and those elements with high importance are investigated. In the context of not knowing the exact feature values of a data stream, the use of a Markov model is proposed herein for predicting the feature distribution of a data stream. Based on the predicted feature distribution, one can make classification decisions to maximize the expected benefits. In addition, there is proposed herein the employment of a quality of decision (QoD) metric to measure the level of uncertainty in decisions and to guide load shedding. A load shedding scheme such as presented herein assigns available resources to multiple data streams to maximize the quality of classification decisions. Furthermore, such a load shedding scheme is able to learn and adapt to changing data characteristics in the data streams.
1. A method of providing load shedding in mining data streams, said method comprising the steps of:
accepting streams of data to be mined, the streams of data containing data stream elements;
ranking the importance of data stream elements;
investigating data stream elements of higher importance; and
thereafter shedding a plurality of data stream elements;
wherein the plurality of data stream elements shed have a higher quality of decision value than the data stream elements of higher importance and the quality of decision value is based on the predicted distribution of feature values in a next time unit; and
wherein the quality of decision value is
Q
1
=
E
x
log
(
f
k
(
x
)
f
k
_
(
x
)
)
.
2. The method according to claim 1 , further comprising the step of predicting the feature distribution of at least one data stream.
3. The method according to claim 2 , wherein said predicting step comprises employing a Markov model.
4. The method according to claim 2 , further comprising the step of rendering classification decisions based on the predicted feature distribution of at least one data stream.
5. The method according to claim 4 , wherein said step of rendering classification decisions comprises rendering classification decisions with a view to maximizing expected benefits.
6. The method according to claim 1 , wherein said ranking step comprises employing a quality of decision metric to assist in classification decisions.
7. The method according to claim 6 , wherein said step of employing a quality of decision metric comprises measuring uncertainty in classification decisions.
8. The method according to claim 7 , wherein said step of employing a quality of decision metric comprises applying the quality of decision metric to multiple data streams.