Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Start single access now
Request access for companies
EXTENDED SEARCH
Log in
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Introduction to Data Mining Read chapter Read first chapter

2016 | OriginalPaper | Chapter

22. Classifying Streaming Data II: Time-Dependent Data

Author : Prof. Max Bramer

Published in: Principles of Data Mining

Publisher: Springer London

Log in

Abstract

This chapter builds on the description in Chapter 21 of the H-Tree algorithm for classifying streaming data, i.e. data which arrives (generally in large quantities) from some automatic process over a period of days, months, years or potentially forever. Chapter 21 was concerned with stationary data generated from a fixed causal model; Chapter 22 is concerned with data that is time-dependent, where the underlying model can change from time to time, perhaps seasonally. This phenomenon is known as concept drift.
The algorithm given here, CDH-Tree, is a variant of the popular CVFDT algorithm which generates a type of decision tree called a Hoeffding Tree. The algorithm is described and explained in detail with accompanying pseudocode for the benefit of readers who may be interested in developing their own implementations. A detailed example using synthetic data is given to illustrate the way in which the classification tree evolves as more and more records are processed in the presence of concept drift.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Classifying Streaming Data
Footnotes
1
We will assume that each record comprises a set of attribute values together with a classification.
 
2
Figure 22.4 is identical to Figure 22.1. It is repeated for ease of reference.
 
3
This is a restriction imposed by the CDH-Tree algorithm. It would be possible to allow nodes in an alternate tree to have their own alternate nodes but at the risk of creating and needing to maintain an increasingly unwieldy structure, most of which will never form part of the main tree. It is only the current main tree that is used for prediction.
 
4
Although nodes 14, 15, 16, 29 and 30 were previously parts of an alternate tree they are now in the main tree and so potentially can have alternate tree structures attached to them.
 
5
Nodes 4 and 8 in Figure 22.8 and the subtrees hanging from them are not part of the revised structure and are no longer accessible. It may be possible for a practical implementation to reuse the memory they occupy but we will not pursue this here.
 
6
We will adopt the convention that the branches at each internal node correspond to attribute values 1 and 2 (or 1, 2 and 3 in the case of age) in that order, working from left to right. So, for example, node 6 corresponds to a rule with left-hand side IF \(\textit{tears}=2\) AND \(\textit{astig}=1\) AND \(\textit{age}=2\). (The corresponding classifications on the right-hand side are not shown.)
 
7
Up to the point where the sliding window is full, and provided \(D\) is greater than \(W\), CDH-Tree is effectively the same algorithm as H-Tree.
 
8
We have left attribute \(\textit{age}\) unchanged to avoid irrelevant complications. It has three attribute values whereas the other attributes all have only two.
 
9
Strictly, the nodes were numbered differently from Figure 22.15, but in the same order.
 
Literature
[1]
Domingos, P., & Hulten, G. (2000). Mining high-speed data streams. In Proceedings of the sixth ACM SIGKDD international conference on knowledge discovery and data mining (pp. 71–80). New York: ACM. CrossRef
[2]
Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining (pp. 97–106). New York: ACM. CrossRef
Metadata
Title
Classifying Streaming Data II: Time-Dependent Data
Author
Prof. Max Bramer
Copyright Year
2016
Publisher
Springer London
Book
Principles of Data Mining

Print ISBN: 978-1-4471-7306-9

Electronic ISBN: 978-1-4471-7307-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-1-4471-7307-6_22