Finding It Now: Construction and Configuration of Networked Classifiers in Real-Time Stream Mining Systems - Signal Processing Systems - page 107

2.1.3 Throughput and Goodput of a Chain of Classifiers

The forwarded output of a classifier C i cons ists of both correctly labelled data from
class

H i .Weuse g i to represent the goodput
(portion of data correctly labelled) and t i to represent the throughput (total forwarded
data, including mistakes). And we will note t 0 to represent the input rate of data.
We can derive t i and g i recursively as
t i
g i

H i as well as false alarms from class

⎧
⎨

a i b i
0 c i

t i − 1
g i − 1

p i +( p i − p i ) φ

=

a i

i

p i − p i )( φ

= , where b i =( − φ ) (1)

i i

⎩

p i φ

=

c i

T i − 1
i

i

For a set of i nd ependent classifiers, the positive and negative a-priori selectivities
are equal: φ i = φ i = P ( X ∈H ) . As a consequence, the transition matrix is diagonal:

p i φ i +( .

p i 1 − φ i ) 0

T i − 1
i

=

p i φ i 0

P X ∈H k , . Using Bayes formula: ∈H k − 1 and X Proof. Define p ++ = ∈H k , X

P ( ) ∈H k − 1 P ( ) ∈H k − 1

X X X

p ++ = X , ) ∈H k | ( X , X ,

P X ) ∈H k − 1

X

= ∈H k | X ∈H k and ( X ,

P X ) ∈H k − 1 P ( ) ∈H k − 1

X X

∈H k | ( X , X ,

P X ∈H k P X ∈H k − 1 P ( ) ∈H k − 1

X

= ∈H k | X ∈H k | X X ,

g k − 1

p D

φ k

P X ∈H k , = ∈H k − 1 and X Likewise p + − = p D

∈H k , X φ k ( t k − 1 − g k − 1 )

P X ∈H k , = and X p − + = ∈H k − 1 p F ∈H k , X ( 1 − φ k ) g k − 1

P X ∈H k , =

p −− = ∈H k − 1 and X p F ∈H k , X ( 1 − φ k )( t k − 1 − g k − 1 )

p ++ and t k = p ++ + p + − + p − + − p −− . Finally, we can observe that g k =

2.2 Optimization Objective

The global utility function of the stream mining system can be expressed as a
function of misclassification and delay cost, under resource constraints.

2.2.1 Misclassification Cost

The misclassification cost, or error cost, may be computed in terms of the two types
of accuracy errors—a penalty c M per unit rate of missed detection, and a penalty