Array Based Naïve Bayesian Machine Learning Program: A J Implementation
Vector 16:2, page 47
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 47
Description of Problem¶
Machine Learning¶
The data to be processed within a machine learning program consists, normally, of several tables of values. This potentially lends itself to array based processing rather than the more common incremental approach. The naïve Bayesian approach used has been found to be quite effective within certain domains. The particular implementation handles nominal domains with the nominal values of attributes and classes assumed to be consecutive integers from 0.
Naive Bayesian Learning¶
The naïve Bayesian approach to machine learning is based on the extension to classical probability made by Thomas Bayes in the 18th Century. The aim is to use the class with the highest probability given a particular instance. This is represented as P(Ci|I) where C represents the possible classes and I is the instance being classified. Bayes theorem gives us the formula P(Ci|I) = P(Ci) P(I|Ci)/P(I). As P(I) is the same for all possible classes this does not need to be calculated as the relative size of probabilities is sufficient for classification purposes. In order to calculate P(I|Ci) the naïve Bayes approach assumes independence of attributes. Although this simplification may be based on invalid assumptions for some datasets it simplifies the process for the calculation of P(I|Ci). This allows us to use the product of the probabilities that I is of the class Ci given the value vj in order to calculate the probability P(I|Ci).
Thus the approach used calculates the probability of class C given instance I as being:
P(Ci|I)=P(Ci)∏jP(vj|Ci)
This leaves the problem of obtaining the values for P(Ci) and P(vj|Ci). In order to calculate these this particular implementation uses a Laplace measure to estimate the probabilities with a numerator correction of 1 and a denominator correction as the number of alternative values. Thus to determine the probability of the class we use:
P(C) = number of records of class C + 1/total records plus number of classes
and for the probability of attribute j having a specific value x given class C we use:
P(vj|C) = number of items of class C with attribute j of value x + 1/number of items with class C + number of alternative values of j.
These estimated probabilities from the Laplace measures are inserted into the naïve Bayes equation in order to find P(Ci|I). The instance is classified as the class with the highest probability rating.
The Laplace Measure¶
The Laplace measure is utilised in the calculation of the attribute and class probabilities. The Laplace measure consists of adding one to the numerator and the number of values to the denominator (in this case either the number of different classes or the number of attributes).
Overview of Algorithm¶
Learning¶
The learning phase consists of several steps:
- Read in the learning and description files and convert them to appropriate formats.
- Get overall information (number of records, number of attributes etc.) from learning and description files.
- Count the number of occurrences of each class in the learning data.
- Calculate the base probabilities of the occurrence of each class using the Laplace measure as detailed above. NB These are only relative probabilities as noted earlier.
- Count the number of occurrences of each value of each attribute for each class.
- Calculate the probabilities of the occurrence of each value of each attribute given each class using the Laplace measure.
Testing¶
The steps for the checking of the test data are:
- For each record of the test data the probabilities for the values of each attribute are obtained for each possible class.
- The Bayesian equation is applied to each record to find the class with the greatest relative probability.
- Each record is classified according to the best value from the equation.
- The classification of each record is compared with the actual class value recorded in the test data and the subsequent accuracy percentage is evaluated.
Classification¶
The classification procedure is the same as the initial steps of the testing procedure. The only difference in this phase is that no comparison is made with actual class values (as they do not exist in the classification data).
A J Implementation¶
Assumptions & File Format Requirements¶
Like most Machine Learning implementations fairly strict assumptions are made regarding the format and existence of the necessary data.
Filebase¶
The filebase (the base name and location of the files) are given in the command line when running the program. This filebase must be exactly the same for all required files. The filebase should include information regarding which drive and folder in a format suited to the operating system. (e.g. ‘Macintosh HD:waves’ for MacOS or ‘a:\waves’ for DOS/Windows)
Description file (filebase.des)¶
This file consists of one line for each attribute and a final line for the class. Each line contains the numbers (consecutive integers from 0) of the possible values for each attribute or class. These are separated by a comma. Unlike other similar machine learning programs the lines are not to begin with a name or type of attribute/class.
Learning data (filebase.dat)¶
The learning data file consists of each record on one line with the values separated by commas. The order of these should match the order in the description file. The last item on each line is assumed to be the class value.
Test data (filebase.tst)¶
The format for the test data is exactly the same as that of the learning data.
Classification data (filebase.cls)¶
The format for the classification data is the same as that for the learning and test data except that it will not contain a class value (therefore each line will have one less value than the other two files).
The learning, testing and classification data can contain differing numbers of records. The maximum number of records is limited by memory requirements due to the potential size of arrays with large number of attributes, classes and records.
J Implementation¶
Basic and Common functions¶
Firstly some basic functions that are used at various places in the program are defined.
read is used to load the four sets of data.
sum gives the sum over the array at rank 1.
get is used to strip the frets from the incoming file and open the data as a string table (this is then converted at different times to an table of integers).
from is used to extract values from a table or array at rank 1.
grd is used to obtain the index (as 0) of the highest probability from the possible classes.
NB. Basic loading function
read=:1!:1@<
NB. Sum array at rank 1
sum =: +/ "1
NB. strip frets and open as string array
get =: > @ <;._2
NB. From at rank 1
from=: {"1
NB. Get grades of array (index of sorted array)
grd =:( i. ~/:~)
The Learning Phase¶
The first of the major sections of the program is to learn from the learning data. This section consists of four subsections.
The first subsection consists of loading the learning data, converting it to a numeric array and extracting some basic information from the array.
lrnfile adds the appropriate extension (.dat) to the filebase.
lrndata loads the learning data using the read function, strips the frets using the get function, opens it to a string table and then converts the string table to a numeric table.
swapped swaps the dimensions of the table in preparation for further processing.
class extracts the line containing the class information from the learning array.
atts then removes the class data from the learning array.
recno obtains the number of records (instances) in the learning data.
inclrndata increments the values in the learning array. This is necessary because when the array is converted to a 3 dimensional array, separated on classes, the array is padded by zeros. This avoids the problem of class 0 matching on non-existent records.
lrnclsdta extracts the class data from the incremented learning array ready for later matching.
NB. Add file extension to filebase
lrnfile=: ,&'.dat'
NB. Load learning data, strip frets and convert to array
lrndata =: ". @ get @ read @ lrnfile
NB. swap dimensions of array of learning data
swapped =: |: @ lrndata
NB. extract class data from learning array
class =: {: @ swapped
NB. remove class data from learning array
NB. leaving attribute data for processing
atts =: }: @ swapped
NB. Number of records in learning data
recno=: # @ lrndata
NB. Increment data to remove problem of zero values
inclrndata=:>: @ lrndata
NB. Extract incremented class data from learning data
lrnclsdta=: attno from inclrndata
The second subsection consists of loading the description data, converting it to a numeric array and extracting some basic information from the array.
descfile adds the appropriate extension (.des) to the filebase.
getdesc loads the description data using the read function, strips the frets and opens it to a string array. Unlike the learning data this can not be immediately converted to a numeric array as the class information needs to be removed first to prevent possible corruption of values extracted from the data.
classdesc extracts the class description information from the description table.
classno obtains the number of different classes.
attno obtains the number of different attributes.
attvals removes the class information and converts the attribute information to a numeric table.
maxvals obtains the largest number of values for an attribute.
NB. Add file extension for description file
descfile=: , & '.des'
NB. load description file into array
getdesc =: get @ read @ descfile
NB. extract class description from description array
classdesc=: ". @ {: @ getdesc
NB. Get number of different classes
classno=:# @ classdesc
NB. get number of different attributes
attno=: <: @ # @ getdesc
NB. get maximum number of values in attributes
attvals=: ". @ }: @ getdesc
maxvals=:# "2 @ |: @ attvals
The third subsection processes the learning data with the information gained from the learning and data files in order to obtain the base class probabilities.
classct obtains a list of the number of occurrences of each class in the learning data.
classprob1 increments the count of the number of occurrences of each class. This is the numerator correction of the Laplace measure.
classprob2 adds the number of different classes to the number of instances in the learning data. This is the denominator correction of the Laplace measure.
classprob calculates the base (relative) probabilities of the occurrence of each class from the learning data.
NB. Get count of number of occurrences of each class
NB. in learning data
classct=:sum @ (classdesc =/ class)
NB. Calculate base class probabilities from learning data
classprob1=: >: @ classct
classprob2=: recno + classno
classprob=: classprob1 % classprob2
The fourth subsection processes the learning data with the information gained from the learning and data files in order to obtain the attribute probabilities.
attvalno finds the placement of highest value for each of the attributes by grading down and matching on zero (the highest element).
attvalno2 takes the list from attvalno and, by multiplying against the attribute value information, obtains the highest value for each attribute.
attvalno3 sums over attvalno2 to convert it back from a table to a list and then increments to obtain the number of different values for each attribute.
lrnclsatts matches the class values for each instance.
lrnclsatts2 uses the matching from lrnclsatts to convert the table of attribute data to a 3 dimensional array (of class, instances and attributes) divided according to class values and removes the class data leaving only attribute data.
attprep gives a binary match of each element against the maximum number of different attribute values.
attcounts sums the information from attprep giving a 3 dimensional array (of value, class and attribute) containing the number of occurrences of each value for each attribute and class.
attprobs1 provides the sum of the number of values for each attribute with the number of occurrences of each class. This is the denominator correction of the Laplace measure.
learn, which is the first of the primary function calls, calculates the relative Bayesian probabilities, using an increment for the Laplace numerator correction. The array of attribute probabilities needs to have its dimensions rearranged to allow for calculation at the appropriate rank.
NB. Get number of values for each attribute
attvalno=:0&= @\: "1 @ attvals
attvalno2 =: attvals * attvalno
attvalno3 =: >: "0 @ sum @ attvalno2
NB. Divide attributes according to class
lrnclsatts=: >:@ classdesc =/ lrnclsdta
lrnclsatts2=: inclrndata }:"1 @ #~ lrnclsatts
NB.Count number of occurrences of each attribute
NB. within each class
attprep=: >:@i.@maxvals =/ lrnclsatts2
attcounts=:+/"2 @ attprep
NB. Calculate Bayesian probabilities using Laplace measure
attprobs1=:attvalno3 +/ classct
learn=: (>:@ attcounts) %"2 (|: @ attprobs1)
The Testing phase¶
The second major section of the program is to check the accuracy of classification of the test data. This section consists of three subsections.
The first subsection consists of loading the test data, converting it to a numeric table and extracting the class data from the table.
testfile adds the appropriate extension (.tst) to the filebase.
tstdata loads the test data using the read function, strips the frets using the get function, opens it to a string table and then converts the string table to a numeric table.
testclass extracts the class data from the table in preparation for checking the accuracy of classification.
tstdata2 removes the class data from the table leaving only attribute data.
tstdata3 swaps the dimensions of the table ready for processing.
attprobs3 rearranges the dimensions of the array of attribute probabilities ready for extracting the matching probabilities.
NB. Add file extension to filebase
testfile=: ,&'.tst'
NB. Load test data, strip frets and convert to array
tstdata =: ". @ get @ read @ testfile
NB. Extract class data from array of test data
testclass=: {: "1 @ tstdata
NB. Remove class data from array of test data
tstdata2=:}: "1@ tstdata
NB. swap dimensions of array of test data
tstdata3=:|:@tstdata2
NB. swap dimensions of array of attribute probabilities
attprobs3=:|: @ learn
The second subsection consists of extracting the matching probabilities and classifying each instance according to the most likely class.
NB. Process testing data with learning probability data
NB. to get attribute probabilities and then classification
tstdtamtch extracts the probabilities from the attribute probability array that match the values of each instance.
tstdatamtchprod gives the naïve element of the Bayesian equation by giving the product of the probabilities of a particular value for each possible class.
tstdtaprobs finishes the Bayesian equation by the product of the class probabilities with the instance probability calculated in tstdatamtchprod. This results in a table (class and instances) of relative probabilities.
tstdtaprobsgrd grades the relative probabilities per class.
tstprobsbst matches the highest relative probability with the appropriate class.
tstclassify1 converts the matches of most probable class to the appropriate class values.
test, the second of the primary function calls, converts the table from tstclassify1 back to a list by summing the table. This gives a list of the class that each instance has been classified as by the program.
NB. extract matching probabilities
tstdatamtch=: tstdata3 from attprobs3
NB. Sum of matching attribute probabilities
tstdatamtchprod=:*/ @ tstdatamtch
NB. Apply Bayesian equation
tstdtaprobs =: classprob * tstdatamtchprod
NB. Grade probabilities for each class and record
tstdtaprobsgrd=: grd "1 @ |: @ tstdtaprobs
NB. Get highest (most likely) class for each record
tstdtaprobsbst =:(<: @ classno) ="0 tstdtaprobsgrd
tstclassify1=:classdesc * "1 tstdtaprobsbst
test=: sum @ tstclassify1
The third subsection checks the accuracy of the classification of the test data.
check1 obtains the match of the classification of the instances with the classes recorded with the instances in the test data.
check2 obtains the number of instances where the classification matches the recorded classes.
tstno obtains the number of instances in the test data.
accuracy, the third major function call, obtains the percentage accuracy of the classification of test data against the recorded values.
NB. Number of records correctly classified
check1=: testclass = test
check2 =: +/ @ check1
NB. Number of records in test data
tstno =: # @ testclass
NB. Get percentage accuracy
accuracy=: check2 100 & * @ % tstno
The Classification Phase¶
The final major section of the program is the classification of new instances from the classification data file. This is the same as the testing phase except that no checking of accuracy is done. This section consists of two subsections.
The first subsection consists of loading the classification data and converting it to a numeric table.
clsfile adds the appropriate extension (.cls) to the filebase.
clsdata loads the classification data using the read function, strips the frets using the get function, opens it to a string table and then converts the string table to a numeric table.
clsdata2 swaps the dimensions of the table ready for processing.
attprobs3 rearranges the dimensions of the array of attribute probabilities ready for extracting the matching probabilities.
NB. Add file extension to filebase
clsfile=: ,&'.cls'
NB. Load classification data, strip frets and convert to array
clsdata =: ". @ get @ read @ clsfile
NB. Swap dimensions of array
clsdata2=:|:@clsdata
The second subsection consists of extracting the matching probabilities and classifying each instance according to the most likely class.
NB. Process classification data with learning probability data
NB. to get attribute probabilities and then classification
clsdatamtch extracts the probabilities from the attribute probability array that match the values of each instance.
clsdatamtchprod gives the naïve element of the Bayesian equation by giving the product of the probabilities of a particular value for each possible class.
clsdtaprobs finishes the Bayesian equation by the product of the class probabilities with the instance probability calculated in clsdatamtchprod. This results in a table (class and instances) of relative probabilities.
clsdtaprobsgrd grades the relative probabilities per class.
clsprobsbst matches the highest relative probability with the appropriate class.
clsclassify1 converts the matches of most probable class to the appropriate class values.
classify, the last of the primary function calls, converts the table from clsclassify1 back to a list by summing the table. This gives a list of the class that each instance has been classified as by the program.
NB. extract matching probabilities
clsdatamtch=: clsdata2 from attprobs3
NB. Sum of matching attribute probabilities
clsdatamtchprod=:*/ @ clsdatamtch
NB. Apply Bayesian equation
clsdtaprobs =: classprob * clsdatamtchprod
NB. Grade probabilities for each class and record
clsdtaprobsgrd=: grd "1 @ |: @ clsdtaprobs
NB. Get highest (most likely) class for each record
clsdtaprobsbst =: (<: @ classno) ="0 clsdtaprobsgrd
clsclassify1=:classdesc * "1 clsdtaprobsbst
classify=: sum @ clsclassify1
Primary Calls & Usage¶
The following are the primary calls and their function:
This call will learn the data and will display the attribute probabilities calculated from the learning data. Requires filebase.dat and filebase.des.
This call will learn and test the data and will display the classification of the test data. Requires filebase.dat, filebase.des and filebase.tst.
This call will learn and test the data and will display the accuracy of classification of the test data. Requires filebase.dat, filebase.des and filebase.tst.
This call will learn, test and classify the data and will display the classification of the test data. Requires filebase.dat, filebase.des, filebase.tst and filebase.cls.
In addition to the four primary calls, some other calls may prove useful in certain situations. One function that may prove of particular interest is:
This call will learn the data and display the class probabilities calculated from the learning data. Requires filebase.dat and filebase.des.
Limitations & Evaluation¶
The performance of this program is obviously dependent on the computer being used and the size and complexity of the data files. The two sets of files used for testing consisted of: wave 6 21 attributes, each of seven values, with three possible class values and 200 instances in each of the three data files; and led 6 seven binary attributes, with ten possible class values and 200 instances in each of the three data files. On a PowerMac G3 running J version 4 the performance was acceptable for the two sets of files tested (approximately 2 - 3 seconds for any of the calls). On a 68040 based Macintosh running J version 4 the performance was considerably less acceptable (30 - 40 seconds for any of the calls).
The performance of the program may be less suited for particularly complex domains due to the size of some of the intermediary arrays. Refining of the implementation may improve some of these performance concerns.
The program does allow for a good degree of flexibility in its usage. As well as the four primary function calls some of the other function calls (which would not normally be directly available in an implementation of this algorithm) could prove potentially useful in the analysis of the classification accuracy of data.
Further Work¶
A variety of further development work would be worthwhile on this program.
- Refining the program with performance considerations specifically in mind.
- Modifying the program to handle numeric rather than nominal attributes, which would require an approach based on the probability density function for the normal distribution. Particularly in the case of allowing for a mixture of nominal and numeric domains at least a slightly more incremental, or alternatively recursive, approach would be necessary. This is due to the necessity of processing the attributes separately for at least part of the time. An overall array based approach (with the necessary incremental or recursive modifications) would be possible with the use of gerunds.
Bibliography¶
Langley, P. (1996) Elements of Machine Learning, Morgan Kaufmann, San Francisco.
Acknowledgement¶
Neville Holmes, School of Computing, University of Tasmania.
Andrew Charman-Williams
School of Computing
University of Tasmania