THE LUCS-KDD DATA DISCRETISATION/NORMALISATION (DN) JAVA SOFTWARE FOR CLASSIFICATION ASSOCIATION RULE MINING (VERSION 2)

1. INTRODUCTION

The LUCS-KDD (Liverpool University Computer Science - Knowledge Discovery in Data) DN (Discretisation/ Normalisation) software has been developed to convert data files available in the UCI data repository ([1]) into a binary format suitable for use with Classification Association Rule Mining (CARM) applications. The software can, of course, equally well be used to convert data files obtained from other sources. We define discretisation and normalisation as follows:

Discretisation

The process of converting the range of possible values associated with a continuous data item (e.g. a double precision number) into a number of sub-ranges each identified by a unique integer label; and converting all the values associated with instances of this data item to the corresponding integer labels.

Normalisation

The process of converting values associated with nominal data items so that they correspond to unique integer labels.

CARM requires "binary valued" input data sets where each record represents an itemset which in turn is a subset of the available set of attributes. Thus:

N = The number of available attributes
A = A set of attributes = {a | 0 < a <= N}
D = A data set comprising M records (R)
R = {r | r subset A}

For example if A={1 2 3 4} then we might have a data set of the form:

1 2 3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2
1 3
1 4
2 3
2 4
3 4
1
2
3
4

which may be used as the input to an ARM software system. The distinction between the data sets used for ARM and those used for CARM is that in the latter case one of the attributes in each record represents a class to which the record is said to "belong". Usually, to facilitate identification, either the last or first attribute in each record in the input data represents the class. Thus we might have a CARM data set of the following form where the last item in each record represents the class (either 3 or 4):

1 2 4
1 2 3
1 4
2 4
1 3
2 3

(Note that records in a CARM input set must have at least one attribute as well as a class).

Generally speaking real data sets do not comprise only binary fields. Typically such data sets comprise a mixture of nominal, continuous and integer fields. Thus real data will require disacretization/ normalisation, i.e. convertion into a binary valued format, before it can be used for CARM. How this is done using the LUCS-KDD DN software will depend on the nature of each field in the data:

Nominal Data (nominal):

A nominal data field has a value selected from an available list of values, for example we may have a nominal data item colour which can have a value taken from the set {blue, green, red, yellow}. Such data items can be normalised by allocating a unique column number to each possible value. For example in the above case we might assign the column numbers {1, 2, 3, 4} to the possible values. This was the approach taken by Version 1 of the LUCS-LDD-DN software; in Version 2 if a two or more nominal values were generally associated (typically in 90% of all records) with the same class the columns were merged.

Continuous Data (double):

Continuous data fields take values that are real numbers within some range defined by minimum and maximum limits. In such cases we divided the given range into a number of sub-ranges and allocate a unique column number to each sub-range. For example we might have a data item average which takes a real number within the range 0.0 to 100.0. In Version 1 of thge software this range of values might be divided into three sub-ranges (divisions): 0.0 <= n <= 33.3 , 33.3 < n <= 66.6 and 66.6 < n <= 100.0 (where n is some instance of the field average), and assign each range to a column number (say) {5, 6, 7} respectively. In Version 2, instead of dividing the range into equally sized divisions the range was divided so as the take account of the probability that a particular value was associated with a particular class (see below for further detail).

Integer Data (int):

Integer data fields can be treated as either continuous data items or as nominal data items. For example if we have a field age which can take a value from 1 to 120 we might treat this as a continuous data item and represent it as a sequence of (say) 4 ranges: 0 <= n <= 30 , 31 <= n <= 60 , 61 <= n <= 90 and 91 <= n <= 120 (where n is some instance of the field age), and assign each range to a unique column number (say) {8, 9, 10, 11} respectively. Alternatively we may have a field gender which can have the value 0 or 1 (i.e. a boolean data item), in which case this could be treated as a nominal data item with one column (say 12) allocated to the value 0 and another (say 13) to the value 1. Whether to treat an integer data item as a nominal or a continuous item depends on the number of attributes the user of an CARM programme is prepared to tolerate --- usually the time complexity of these programmes (at least in part) is proportional to the number of columns (attributes) in the input data. It would therefore not be a good idea to discretise the above age field in terms of 120 individual colums!

. In Version 2 of the software integer fields are treated in the same way as doubles.

Unused (unused):

unused data fields generally describe fields such as "record number" or "TID". Data fields of "type" unused are entirely ignored by the LUCS-KDD DN software and thus play no part in the discretization/ normalisation process.

Thus given a (space separated) data set with the schema {colour (nominal), average (double), age (int), class (int)} such as:

red    25.6  56 1
green  33.3   1 1
green   2.5  23 0
blue   67.2 111 1
red    29.0  34 0
yellow 99.5  78 1
yellow 10.2  23 1
yellow  9.9  30 0
blue   67.0  47 0
red    41.8  99 1

This would be discretised/ normalised as follows:

3 5  9 13
2 5  8 13
2 5  8 12
1 7 11 13
3 5  9 12
4 7 10 13
4 5  8 13
4 5  8 12
1 7  9 12
3 6 11 13

The entire data set is now presented by 13 binary valued attributes and can be mined using appropriate CARM software.

The LUCS-KDD DN software has been implemented in Java using the Java2 SDK (Software Development Kit) Version 1.4.0, which should therefore make it highly portable. In the interest of "user freindliness" the user interface has been implemented as a GUI. The source code is available at:

The code does not require any special packages and thus can be compiled using the standard Java compiler:

javac LUCS_KDD_DN.java

Before the LUCS-KDD DN software can convert a data file into the desired binary valued format it needs to know the schema for the data to be converted. The schemas for the data files in the UCI repository are described (usually) in free text format within a .names file. Users of the LUCS-KDD DN software will thus have to create their own schema files before any convertion can take place.

LUCS-KDD DN Schema files comprise three lines of text each containing a sequence of N literals separated by white space (not carriage returns) where N is the number of attributes in the data set to be converted:

1. The first line is used to describe the "type" of each field, permitted options are: unused, nominal, integer and double.
2. The second line gives the names of the fields, this is not used in the discretisation/ normalisation itself, but may be useful when the time comes to match the column numbers contained in ARs and CARs to the output schema.

3. The third line contains the possible "legal" values for each nominal data item; in the case of "unuseds", "doubles" and "ints" the literal null is used. Nominal values are seperated by a '/' charcater.

The schema file for the above example data set would be:

nominal double int nominal
colour average age class
blue/green/red/yellow null null 0/1

The schema file for the Pima Indians UCI data set might be:

int int int int int double double int nominal
NumberPregnacies PlasmaGluConcent
		DiastolicBldPress TricepsSkinFold
		2-HourSerumIns BodyMassIndex
		DiabPedFunc Age Class
null null null null null null null null 0/1

(Remember that data fields of "type" unused are ignored by the LUCS-KDD DN software and do not appear in the output.)

When compiled the software can be invoked in the normal manner using the Java interpreter:

java LUCS_KDD_DN.java

If you are planning to process a very large data set, such as covertype, it might be an idea to grab some extra memory. For example:

java -Xms600m -Xmx600m LUCS_KDD_DN

Once invoked you will see an interface of the form presented in Figure 1. Note that in Figure 1 all but one of the interface buttons are "greyed out"; this is because, at this stage, we have no data to work with. The one functional button is:

1. Input Schema: Selecting this button will bring up a second GUI to allow the user to load the identified schema file.

Note also, in Figure 1, that some instructions are presented in the main window of the GUI.

A schema file is loaded by selecting the "Input Schema" button. Once the schema has been "read" three more buttons become active:

1. Input Data ('/nbsp/nbsp' separated): Raw data files in the UCI repository are either space or comma separated. This button allows the user to select and load a space separated data file to be discretised/normalised.
2. Input Data (',' separated): Button to allow the user to select and load a comma separated data file.
3. List Schema: Button to allow the user to list the contents of the current schema file. In the case of the Pima Indians data set the schema will be presented as follows.

(1) int: NumberPregnacies
(2) int: PlasmaGluConcent
(3) int: DiastolicBldPress
(4) int: TricepsSkinFold
(5) int: 2-HourSerumIns
(6) double: BodyMassIndex
(7) double: DiabPedFunc
(8) int: Age
(9) nominal: Class { 0 1 }

Figure 2 shows the LUCS-KDD DN interface once a schema file (the example for the Pima Indians data set given above) has been loaded and listed using the "Input Schema" and "List Schema" buttons respectively.

A data file can be loaded using either the "Input Data ('/nbsp/nbsp' separated) or "Input Data (',' separated" buttons. Some example raw data (the first few lines from the Pima Indians comma separated data set) is given below:

6,148,72,35,0,33.6,0.627,50,1
1,85,66,29,0,26.6,0.351,31,0
8,183,64,0,0,23.3,0.672,32,1
1,89,66,23,94,28.1,0.167,21,0
0,137,40,35,168,43.1,2.288,33,1
5,116,74,0,0,25.6,0.201,30,0
3,78,50,32,88,31.0,0.248,26,1
10,115,0,0,0,35.3,0.134,29,0
2,197,70,45,543,30.5,0.158,53,1
8,125,96,0,0,0.0,0.232,54,1
4,110,92,0,0,37.6,0.191,30,0
10,168,74,0,0,38.0,0.537,34,1
10,139,80,0,0,27.1,1.441,57,0
1,189,60,23,846,30.1,0.398,59,1
5,166,72,19,175,25.8,0.587,51,1
......

Figure 3 shows the LUCS-KDD DN interface once a data set has been loaded (the Pima Indians data set in this case). Note that seven more buttons have now become active:

1. Input Num. Divs: To normalise a continuous attribute the LUCS-KDD discretisation software divides the values for the attribute into a number of sub-ranges. Using the "Input Num. Divs" button the user can specify the desired number of sub-ranges. It is usually a good idea to select a low value; this will have the effect of producing less columns in the output data which in turn will provide computation efficiency benefits. It is usually not a good idea however to enter a value which is less than the number of classes to be represented by the input data, unless the number of classes is relatively high (>5). Values of 3, 4 or 5 have all been successfully used.
2. List Input Data: This button allows the user to list the input data; note that the data will be listed using the LUCS-KDD DN internal representation where nominal values are represented as index values. Some sample output for the Pima Indians set is given below:

6.0 148.0 72.0 35.0 0.0 33.6 0.627 50.0 1.0
1.0 85.0 66.0 29.0 0.0 26.6 0.351 31.0 0.0
8.0 183.0 64.0 0.0 0.0 23.3 0.672 32.0 1.0
1.0 89.0 66.0 23.0 94.0 28.1 0.167 21.0 0.0
0.0 137.0 40.0 35.0 168.0 43.1 2.288 33.0 1.0

5.0 116.0 74.0 0.0 0.0 25.6 0.201 30.0 0.0
3.0 78.0 50.0 32.0 88.0 31.0 0.248 26.0 1.0
10.0 115.0 0.0 0.0 0.0 35.3 0.134 29.0 0.0
2.0 197.0 70.0 45.0 543.0 30.5 0.158 53.0 1.0
8.0 125.0 96.0 0.0 0.0 0.0 0.232 54.0 1.0
4.0 110.0 92.0 0.0 0.0 37.6 0.191 30.0 0.0
10.0 168.0 74.0 0.0 0.0 38.0 0.537 34.0 1.0
10.0 139.0 80.0 0.0 0.0 27.1 1.441 57.0 0.0
1.0 189.0 60.0 23.0 846.0 30.1 0.398 59.0 1.0
5.0 166.0 72.0 19.0 175.0 25.8 0.587 51.0 1.0
....

3. List Min Max Data: Button to list the minimum and maximum values for the current data set. For The Pima Indians data set this will be as follows:

   Range col. 1: 0.0 to 17.0 (range of 17.0)
   Range col. 2: 0.0 to 199.0 (range of 199.0)
   Range col. 3: 0.0 to 122.0 (range of 122.0)
   Range col. 4: 0.0 to 99.0 (range of 99.0)
   Range col. 5: 0.0 to 846.0 (range of 846.0)
   Range col. 6: 0.0 to 67.1 (range of 67.1)
   Range col. 7: 0.078 to 2.42 (range of 2.342)
   Range col. 8: 21.0 to 81.0 (range of 60.0)
   Range col. 9: 0.0 to 1.0 (range of 1.0)
   

4. Move N to End: Most CARM algorithms require the class for each record to be the last value listed (the alternative is to require the class to be the first value listed). Not all of the UCI, and other, raw data sets do this (in some cases there are a number of possible fields that may be used as the class). This button allows the user to specify a column to be moved to the end of each record.
5. Move N to before M: Similarly it is sometimes required to move a column to a position in the data set other than the end. Typically this might be required where a CARM algorithm requires the class to be listed at the start of each record.
6. Remove Col N: Some of the UCI raw data sets (and other such sets) include redundant columns. For example it is not uncommon for data sets to include an identifying incremental number for each record. This button allows the user to remove a column from the input data.
7. Randomise Rows: Some data sets are ordered in some way, sometimes on the class variable, sometimes according to a particular attribute or attributes. The effect of this will be that any CARM software applied to the data will produce a "skewed" result. This button causes the input data to be randomised (note that randomisation is not the same as distribution --- see Section 4.5 below).

The desired number of divisions is entered using the "Input Num. Divs" button. With respect to the Pima Indians data set the minimum number of ranges setting for this class could be 2 as there are two classes ---- "NoSignsOfDiabetes" and "SignsOfDiabetes". However, experiments have shown that even with two classes it is a good idea to have at least 3 divisions. An even better classifier will usually be produced using a greater number of divisions, a value of 5 has been found to give a good trade of between accuracy and computational efficiency with respect to the mining algorithm used.

Remember that the higher the number of divisions the more output attributes will be generated during the discretisation/normalisation process, which in turn will have an effect on the computational efficiency of any CARM algorithm that may be applied to the data.

Where an integer data field has a range less than the user specified number of sub-ranges the LUCS KDD DN software will assign a number of columns to the integer field equivalent to the size of the range. For example if we have an integer field which can take values in the range of 99 to 102 inclusive (i.e. a range size of 4) and the number of divisions value is 5 then 4 columns would be assigned to the integer field. If, however, the number of sub-ranges value was set to 3, the 99 to 102 range would be divided into three divisions each with its own unique column number assigned to it (how this is done is described blow.

Once a value for the number of divisions has been successfully entered the "Normalisation" button becomes available:

1. Normalisation: Button to cause discretisation/normalisation to be carried out.

To discretise/normalise the data set the user simply selects the "Normalisation" button. Note that for some data sets this process may take a few seconds. The result in the case of the Pima Indians data set will be of the following form:

1 6 9 14 19 23 27 33 38
1 5 9 14 19 23 27 32 37
1 8 9 14 19 23 27 32 38
1 5 9 14 19 23 27 32 37
1 5 9 14 19 23 31 32 38
1 5 9 14 19 23 27 32 37
1 5 9 14 19 23 27 32 38
3 5 9 14 19 23 27 32 37
1 8 9 17 22 23 27 34 38
1 5 10 14 19 23 27 35 38
1 5 9 14 19 23 27 32 37
3 8 9 14 19 23 27 32 38
3 5 9 14 19 23 31 36 37
1 8 9 14 22 23 27 36 38
1 8 9 14 19 23 27 33 38
............

Once normalisation is complete a further five (output) buttons become active (Figure 4) as follows:

1. Distribute Classes: So as to improve the accuracy of CARM algorithms it is usually beneficial to ensure that each class is distributed evenly across the entire data set --- this is achieved using the "Distribute Classes" button.
2. List Parameters: The "List Parameters" button outputs statistics relating to the processed data set. In the case of the Pima Indians set this will be:
   

   Number of records             = 768
   Number of cols (input data) = 9
   Number of cols (schema)     = 9
   Num. missing values           = 0
   Max num. divisions             = 5
   Number of attributes         = 38
   Density (%)                          = 23.68
   Number of classes              = 2
   Number of records per class:
   	Class 42 = 268 records (34.9%)
   	Class 41 = 500 records (65.1%)
   

3. List Attribute Labels: This button produces a set of labels, one for each column, for the discretised/normalised data which may be used when explaining the results of CARM exercises. Some example output in the context of the Pima Indians set is given below:
   

   (1) NumberPregnacies <= 9
   (2) 9 < NumberPregnacies <= 10
   (3) 10 < NumberPregnacies <= 11
   (4) 11 < NumberPregnacies
   (5) PlasmaGluConcent <= 142
   (6) 142 < PlasmaGluConcent <= 150
   (7) 150 < PlasmaGluConcent <= 152
   (8) 152 < PlasmaGluConcent
   (9) DiastolicBldPress <= 94
   (10) 94 < DiastolicBldPress <= 103
   (11) 103 < DiastolicBldPress <= 107
   (12) 107 < DiastolicBldPress <= 117
   (13) 117 < DiastolicBldPress
   (14) TricepsSkinFold <= 40
   (15) 40 < TricepsSkinFold <= 41
   (16) 41 < TricepsSkinFold <= 42
   (17) 42 < TricepsSkinFold <= 48
   (18) 48 < TricepsSkinFold
   (19) 2-HourSerumIns <= 341
   (20) 341 < 2-HourSerumIns <= 376
   (21) 376 < 2-HourSerumIns <= 444
   (22) 444 < 2-HourSerumIns
   (23) BodyMassIndex <= 44.733
   (24) 44.733 < BodyMassIndex <= 45.411
   (25) 45.411 < BodyMassIndex <= 46.767
   (26) 46.767 < BodyMassIndex
   

(27) DiabPedFunc <= 0.93
(28) 0.93 < DiabPedFunc <= 0.953
(29) 0.953 < DiabPedFunc <= 1.001
(30) 1.001 < DiabPedFunc <= 1.379
(31) 1.379 < DiabPedFunc
(32) Age <= 47
(33) 47 < Age <= 53
(34) 53 < Age <= 54
(35) 54 < Age <= 55
(36) 55 < Age
(37) Class=0
(38) Class=1

4. List Output Data: The "List Output Data" button is used to output the results of discretisation/ normalisation to the screen thus allowing the user to "eye ball" the data before saving it to file. The first few lines of the discretised, normalised and distributed Pima Indians set are given below. Note that in the case of the Pima Indians sets the ratio of "NoSignsOfDiabetes" (41) and "SignsOfDiabetes" (42) is roughly 2:1 therefore (as a result of distribution) every third record is a "SignsOfDiabetes" record.
   

   1 6 9 14 19 23 27 33 38
   1 5 9 14 19 23 27 32 37
   1 8 9 14 19 23 27 32 38
   1 5 9 14 19 23 27 32 37
   1 5 9 14 19 23 31 32 38
   1 5 9 14 19 23 27 32 37
   1 5 9 14 19 23 27 32 38
   3 5 9 14 19 23 27 32 37
   1 8 9 17 22 23 27 34 38
   1 5 10 14 19 23 27 35 38
   1 5 9 14 19 23 27 32 37
   3 8 9 14 19 23 27 32 38
   3 5 9 14 19 23 31 36 37
   1 8 9 14 22 23 27 36 38
   1 8 9 14 19 23 27 33 38
   ............
   

5. Save Normalisation: Finally the "Save Normalisation" button allows the user to specify a file name and directory in which to store the discretised/ normalised (and possibly distributed) data set. It is a good idea to include information concerning: (i) the number of columns (attributes), (ii) the number of records and (iii) the number of classes; in the output file name. For example the Pima Indians output data set might be stored in the file pimaIndians.D38.N768.C2.num (where D is the number of attributes, N the number of records and C the number of classes).

5. HOW IT WORKS

6. COMPARISON WITH VERSION 1

7. LITERATURE REVIEW

8. CONCLUSION

The LUCS-KDD DN software has been in use successfully within the LUCS-KDD group for some time. The software is available for free, however the author would appreciate appropriate acknowledgement. The following reference format for referring to the software is suggested:

Coenen, F. (2003), LUCS-KDD DN Software (Version 2), http://www.csc.liv.ac.uk/~frans/KDD/Software/LUCS_KDD_DN/, Department of Computer Science, The University of Liverpool, UK.

Should you discover any "bugs" or other problems within the software (or this documentation), or have suggestions for additional features, please do not hesitate to contact the author.

Some additional notes on processing a number of example data sets from the UCI repository, together with example schema files are available at:

A number of example discretised/normalised data sets, taken from the UCI library, are available at: