designecoc

Coding matrix for reducing error-correcting output code to binary

collapse all in page

Syntax

M = designecoc(K,name)
M = designecoc(K,name,Name,Value)

Description

example

M = designecoc(K,name) returns the coding matrix M that reduces the error-correcting output code (ECOC) design specified by name and K classes to a binary problem. M has K rows and L columns, with each row corresponding to a class and each column corresponding to a binary learner. name and K determine the value of L.

You can view or customize M, and then specify it as the coding matrix for training an ECOC multiclass classifier using fitcecoc.

example

M = designecoc(K,name,Name,Value) returns the coding matrix with additional options specified by one or more Name,Value pair arguments.

For example, you can specify the number of trials when generating a dense or sparse, random coding matrix.

Examples

collapse all

Open Live Script

Consider the arrhythmia data set. There are 16 classes in the study, 13 of which are represented in the data. The first class indicates that the subject did not have arrhythmia, and the last class indicates that the subject's arrhythmia state was not recorded. Suppose that the other classes are ordinal levels indicating the severity of arrhythmia. Train an ECOC classifier using a custom coding design specified by the description of the classes.

Load the arrhythmia data set.

load arrhythmia
K = 13; % Number of distinct classes

Construct a coding matrix that describes the nature of the classes.

OrdMat = designecoc(11,'ordinal');
nOM = size(OrdMat);
class1VSOrd = [1; -ones(11,1); 0];
class1VSClass16 = [1; zeros(11,1); -1];
OrdVSClass16 = [0; ones(11,1); -1];
Coding = [class1VSOrd class1VSClass16 OrdVSClass16,...
    [zeros(1,nOM(2)); OrdMat; zeros(1,nOM(2))]]
Coding = 13×13

     1     1     0     0     0     0     0     0     0     0     0     0     0
    -1     0     1    -1    -1    -1    -1    -1    -1    -1    -1    -1    -1
    -1     0     1     1    -1    -1    -1    -1    -1    -1    -1    -1    -1
    -1     0     1     1     1    -1    -1    -1    -1    -1    -1    -1    -1
    -1     0     1     1     1     1    -1    -1    -1    -1    -1    -1    -1
    -1     0     1     1     1     1     1    -1    -1    -1    -1    -1    -1
    -1     0     1     1     1     1     1     1    -1    -1    -1    -1    -1
    -1     0     1     1     1     1     1     1     1    -1    -1    -1    -1
    -1     0     1     1     1     1     1     1     1     1    -1    -1    -1
    -1     0     1     1     1     1     1     1     1     1     1    -1    -1
      ⋮

Train an ECOC classifier using the custom coding design Coding and specify that the binary learners are decision trees.

Mdl = fitcecoc(X,Y,'Coding',Coding,'Learner','Tree');

Estimate the in-sample classification error.

genErr = resubLoss(Mdl)
genErr = 0.1460
Open Live Script

If you request a random coding matrix by specifying sparserandom or denserandom, then, by default, designecoc generates 10,000 random matrices. Then, it chooses the matrix with the largest, minimal, pair-wise row distances based on the Hamming measure. You can specify to generate more matrices to increase the chance of obtaining a better one, or you can generate several coding matrices, and then see which performs best.

Load the arrhythmia data set. Reserve the observations classified into class 16 (i.e., those that do not have an arrhythmia classification) as new data.

load arrhythmia
oosIdx = Y == 16;
isIdx = ~oosIdx;
Y = categorical(Y(isIdx));
tabulate(Y)
  Value    Count   Percent
      1      245     56.98%
      2       44     10.23%
      3       15      3.49%
      4       15      3.49%
      5       13      3.02%
      6       25      5.81%
      7        3      0.70%
      8        2      0.47%
      9        9      2.09%
     10       50     11.63%
     14        4      0.93%
     15        5      1.16%

K = numel(unique(Y));

Generate four random coding design matrices such that the first two are dense and the second two are sparse. Specify to find the best out of 20,000 variates.

rng(1); % For reproducibility 

Coding = cell(4,1); % Preallocate for coding matrices
CodingTypes = {'denserandom','denserandom','sparserandom','sparserandom'};
for j = 1:4;
    Coding{j} = designecoc(K,CodingTypes{j},'NumTrials',2e4);
end

Coding is a 4-by-1 cell array, where each cell is a coding design matrix. The matrices have K rows, but the number of columns (i.e., binary learners) might vary.

Train and cross validate ECOC classifiers using the 15-fold cross validation. Specify that each ECOC classifier be trained using a classification tree, and the random coding matrix stored in Coding.

Mdl = cell(4,1); % Preallocate for the ECOC classifiers
for j = 1:4;
    Mdl{j} = fitcecoc(X(isIdx,:),Y,'Learners','tree',...
        'Coding',Coding{j},'KFold',15);
end
Warning: One or more of the unique class values in GROUP is not present in one or more folds. For classification problems, either remove this class from the data or use N instead of GROUP to obtain nonstratified partitions. For regression problems with continuous response, use N.

Warning: One or more of the unique class values in GROUP is not present in one or more folds. For classification problems, either remove this class from the data or use N instead of GROUP to obtain nonstratified partitions. For regression problems with continuous response, use N.

Warning: One or more of the unique class values in GROUP is not present in one or more folds. For classification problems, either remove this class from the data or use N instead of GROUP to obtain nonstratified partitions. For regression problems with continuous response, use N.

Warning: One or more of the unique class values in GROUP is not present in one or more folds. For classification problems, either remove this class from the data or use N instead of GROUP to obtain nonstratified partitions. For regression problems with continuous response, use N.

Mdl is a 4-by-1 cell array of ClassificationPartitionedECOC models. Several classes have low relative frequency in the data, and so there is a chance that, during cross validation, some in-sample folds will not train using observations from those classes.

Estimate the 15-fold classification error for each classifier.

genErr = nan(4,1);
for j = 1:4;
    genErr(j) = kfoldLoss(Mdl{j});
end

genErr
genErr = 4×1

    0.2256
    0.2116
    0.2186
    0.2186

Though the generalization error is still high, the best performing model, based solely on the out-of-sample classification error, is the model that used the coding design Coding{3}.

You can try to improve the generalization error by tuning some parameters of the binary learners. For example, you can specify to use the twoing rule or deviance for the split criterion, rather than the default Gini's diversity index. You might also specify to use surrogate splits since there are missing values in the data.

Input Arguments

collapse all

Number of classes, specified as a positive integer.

K specifies the number of rows of the coding matrix M.

Data Types: single | double

Coding design name, specified as a value in the following table. The table summarizes the coding schemes.

ValueNumber of Binary LearnersDescription
'allpairs' and 'onevsone'K(K – 1)/2For each binary learner, one class is positive, another is negative, and the software ignores the rest. This design exhausts all combinations of class pair assignments.
'binarycomplete'2(K−1)−1This design partitions the classes into all binary combinations, and does not ignore any classes. For each binary learner, all class assignments are -1 and 1 with at least one positive and negative class in the assignment.
'denserandom'Random, but approximately 10 log2KFor each binary learner, the software randomly assigns classes into positive or negative classes, with at least one of each type. For more details, see Random Coding Design Matrices.
'onevsall'KFor each binary learner, one class is positive and the rest are negative. This design exhausts all combinations of positive class assignments.
'ordinal'K – 1For the first binary learner, the first class is negative, and the rest positive. For the second binary learner, the first two classes are negative, the rest positive, and so on.
'sparserandom'Random, but approximately 15 log2KFor each binary learner, the software randomly assigns classes as positive or negative with probability 0.25 for each, and ignores classes with probability 0.5. For more details, see Random Coding Design Matrices.
'ternarycomplete'(3K−2(K+1)+1)/2This design partitions the classes into all ternary combinations. All class assignments are 0, -1, and 1 with at least one positive and one negative class in the assignment.

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside quotes. You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

Example: 'NumTrials',1000 specifies to generate 1000 random matrices.

Number of random coding matrices to generate, specified as the comma-separated pair consisting of 'NumTrials' and a positive integer.

The software:

  • Generates NumTrials matrices, and selects the one with the maximal, pair-wise row distance.

  • Ignores NumTrials for all values of name except 'denserandom' and 'sparserandom'.

Example: 'NumTrials',1000

Data Types: single | double

Output Arguments

collapse all

Coding matrix that reduces an ECOC scheme to binary, returned as a numeric matrix. M has K rows and L columns, where L is the number of binary learners. Each row corresponds to a class and each column corresponds to a binary learner.

The elements of M are -1, 0, or 1, and the value corresponds to a dichotomous class assignment. This table describes the meaning of M(i,j), that is, the class that learner j assigns to observations in class i.

ValueDichotomous Class Assignment
–1Learner j assigns observations in class i to a negative class.
0Before training, learner j removes observations in class i from the data set.
1Learner j assigns observations in class i to a positive class.

The binary learners for designs denserandom, binarycomplete, and onevsall do not assign 0 to observations in any class.

Tips

  • The number of binary learners grows with the number of classes. For a problem with many classes, the binarycomplete and ternarycomplete coding designs are not efficient. However:

    • If K ≤ 4, then use ternarycomplete coding design rather than sparserandom.

    • If K ≤ 5, then use binarycomplete coding design rather than denserandom.

    You can display the coding design matrix of a trained ECOC classifier by entering Mdl.CodingMatrix into the Command Window.

  • You should form a coding matrix using intimate knowledge of the application, and taking into account computational constraints. If you have sufficient computational power and time, then try several coding matrices and choose the one with the best performance (e.g., check the confusion matrices for each model using confusionchart).

  • Leave-one-out cross-validation (Leaveout) is inefficient for data sets with many observations. Instead, use k-fold cross-validation (KFold).

Algorithms

collapse all

Custom Coding Design Matrices

Custom coding matrices must have a certain form. The software validates custom coding matrices by ensuring:

  • Every element is -1, 0, or 1.

  • Every column contains as least one -1 and one 1.

  • For all distinct column vectors u and v, u ≠ v and u ≠ -v.

  • All rows vectors are unique.

  • The matrix can separate any two classes. That is, you can travel from any row to any other row following these rules:

    • You can move vertically from 1 to -1 or -1 to 1.

    • You can move horizontally from a nonzero element to another nonzero element.

    • You can use a column of the matrix for a vertical move only once.

    If it is not possible to move from row i to row j using these rules, then classes i and j cannot be separated by the design. For example, in the coding design

    [10−10010−1]

    classes 1 and 2 cannot be separated from classes 3 and 4 (that is, you cannot move horizontally from the -1 in row 2 to column 2 since there is a 0 in that position). Therefore, the software rejects this coding design.

Random Coding Design Matrices

For a given number of classes K, the software generates random coding design matrices as follows.

  1. The software generates one of these matrices:

    1. Dense random — The software assigns 1 or –1 with equal probability to each element of the K-by-Ld coding design matrix, where Ld≈⌈10log2K⌉.

    2. Sparse random — The software assigns 1 to each element of the K-by-Ls coding design matrix with probability 0.25, –1 with probability 0.25, and 0 with probability 0.5, where Ls≈⌈15log2K⌉.

  2. If a column does not contain at least one 1 and at least one –1, then the software removes that column.

  3. For distinct columns u and v, if u = v or u = –v, then the software removes v from the coding design matrix.

The software randomly generates 10,000 matrices by default, and retains the matrix with the largest, minimal, pairwise row distance based on the Hamming measure ([4]) given by

Δ(k1,k2)=0.5∑l=1L|mk1l||mk2l||mk1l−mk2l|,

where mkjl is an element of coding design matrix j.

References

[1] Fürnkranz, Johannes. “Round Robin Classification.” J. Mach. Learn. Res., Vol. 2, 2002, pp. 721–747.

[2] Escalera, S., O. Pujol, and P. Radeva. “Separability of ternary codes for sparse designs of error-correcting output codes.” Pattern Recog. Lett., Vol. 30, Issue 3, 2009, pp. 285–297.

See Also

|

Introduced in R2014b

Statistics and Machine Learning Toolbox Documentation

Support