The ChiMerge algorithm consists of an initialization
step and a bottom-up merging process, where inter-
vals are continuously merged until a termination con-
dition is met. Chimerge is initialized by first sorting
the training examples according to their value for the
attribute being discretized and then constructing the
initial discretization, in which each example is put into
its own interval (i.e., place an interval boundary before
and after each example). The interval merging process
contains two steps, repeated continuously: (1) com-
pute the x2 value for each pair of adjacent intervals,
(2) merge (combine) the pair of adjacent intervals with
the lowest x2 value. Merging continues until all pairs
of intervals have x2 values exceeding the parameter
x2-threshold (described below); that is, all adjacent in-
tervals are considered significantly different by the x2
independence test.
The formula for computing the x2 value is: