ICCS
July –, Semi-Supervised Learning for MixedType Data via Formal Concept Analysis
Mahito SUGIYAMA†,‡ ，Akihiro YAMAMOTO††

Kyoto University‡
JSPS Research Fellow
/Summary• We propose a semi-supervised learning (SSL) method,
called SELF (SEmi-supervised Learning via FCA), using
Formal Concept Analysis (FCA)– It can handle mixed-type data containing both discreteand continuous variables∘ Numerical data are discretized by binary encoding

/Summary• We propose a semi-supervised learning (SSL) method,
called SELF (SEmi-supervised Learning via FCA), using
Formal Concept Analysis (FCA)– It can handle mixed-type data containing both discreteand continuous variables∘ Numerical data are discretized by binary encoding• Main contributions
. The ﬁrst direct SSL method for mixed-type data
– FCA is shown to be a powerful tool for machine learning and knowledge discovery
. Can handle incomplete datasets– missing values and missing labels
. Achieve good accuracy of classiﬁcation experimentally
/Contents
. Problems and Motivation
. Flowchart of SELF
. Learning by SELF
i ) Data preprocessingii ) Make concepts by FCAiii ) Learn classiﬁcation rulesiv ) Classify unlabeled data
. Experiments
. Conclusion

/Problems in Knowledge Discovery• We need to treat more and more massive datasets in KDD• Problems:
. Many datasets are mixed-type: consist of both discreteand continuous variables
. Many datasets are incomplete: contain NULL values– A missing value: Some value of a datum is missing– A missing label: Class label of a datum is missing

/Example: The Horse-Colic Dataset in
UCI Repository/Mixed-Type Datasets• Lots of mixed-type data with discrete and continuous variables are available for KDD– e.g. traﬃc data for intrusion detection, biochemical data, …
– Discrete variable: binary (T, F), nominal (A, B, … , v)
∘ e.g., sex, buying history, questionnaire results, …
– Continuous variable: real-valued (ℝ)∘ Mainly obtained by measurement or observation– cf. scales of measure (nominal, ordinal, interval, ratio)• Only few machine learning and KDD methods can directly
handle mixed-type data
– e.g. Decision tree-based methods such as C.• Modern eﬃcient and eﬀective KDD method is needed/Incomplete Datasets• How to treat incomplete datasets with NULL（⊥）values isimportant problem in KDD– There are various types of NULL
• We consider the following two types of NULL
– A missing value: Some value of a datum is missing– A missing label: Class label of a datum is missing• Treat errors of discretized (quantized) real-valued data
– e.g. If a real number π = 3.1415 … is discretized to 3.1, thesubsequent bits become unknown– This error is not treated in most methods in (statistical) machine learning and KDD, but there always exist

/Problems in Knowledge Discovery• We need to treat more and more massive datasets in KDD• Problems:
. Many datasets are mixed-type: consist of both discreteand continuous variables
. Many datasets are incomplete: contain NULL values– A missing value: Some value of a datum is missing– A missing label: Class label of a datum is missing

/Problems in Knowledge Discovery• We need to treat more and more massive datasets in KDD• Problems:
. Many datasets are mixed-type: consist of both discreteand continuous variables
. Many datasets are incomplete: contain NULL values– A missing value: Some value of a datum is missing– A missing label: Class label of a datum is missing

. Labeling task costs high (money, time, … )– We need class labels to obtain classiﬁcation rules– Yet we have lots of unlabeled data to be analyzed– The concept of semi-supervised learning arose in machine learning and KDD
/Semi-Supervised Learning• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with (only few) labeled data, build better classiﬁers [Zhu and Goldberg, ]/

Semi-Supervised Learning• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with (only few) labeled data, build better classiﬁers [Zhu and Goldberg, ]/

Semi-Supervised Learning• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with (only few) labeled data, build better classiﬁers [Zhu and Goldberg, ]/

Semi-Supervised Learning• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with (only few) labeled data, build better classiﬁers [Zhu and Goldberg, ]/

Problems in SSL• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with (only few) labeled data, build better classiﬁers [Zhu and Goldberg, ]• However, to date, no SSL method can treat mixed-type
datasets directly

/Problems in SSL and Our Solution• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with (only few) labeled data, build better classiﬁers [Zhu and Goldberg, ]• However, to date, no SSL method can treat mixed-type
datasets directly• We solve this problem by using Formal Concept Analysis– We present a new SSL method, called SELF, for incomplete mixed-type datasets

/Contents
. Problems and Motivation
. Flowchart of SELF
. Learning by SELF
i ) Data preprocessingii ) Make concepts by FCAiii ) Learn classiﬁcation rulesiv ) Classify unlabeled data
. Experiments
. Conclusion

/Flowchart of SELF
Input a training dataset

Data preprocessing
phase
Preprocess for binary and nominal variablesk←0

Learning phase

Discretize real-valued variables at level kk←k+1

Make a context

Remove objects
contained inconsistent concepts

Make concepts by FCA

Extract classification rules using labeled data

All labeled data
are contained inconsistent concepts

NO

YES
Classify a test dataset

Classification phase

Output a result

/Contents
. Problems and Motivation
. Flowchart of SELF
. Learning by SELF
i ) Data preprocessingii ) Make concepts by FCAiii ) Learn classiﬁcation rulesiv ) Classify unlabeled data
. Experiments
. Conclusion

/Learning by SELF
• Learning from the following dataset (⊥ is the missing value)






Feature 

Feature 

Feature 

Label

T
F
T
F
T

C
A
B
A
C

.
.
�
.
.



�

�

/

Data Preprocessing (/)• Learning from the following dataset (⊥ is the missing value)
Feature 

Feature 

Feature 

Label

T
F
T
F
T

C
A
B
A
C

.
.
�
.
.



�

�







• Make a context in the data preprocessing phase






.T
×
×
×

.A
×
×

.B

.C
×

.

.

×
×
/

Data Preprocessing (/)• Learning from the following dataset (⊥ is the missing value)






Feature 

Feature 

Feature 

Label

T
F
T
F
T

C
A
B
A
C

.
.
�
.
.



�

�

• Discretize the continuous feature (F) using binary encoding

0
0.28

1
0.54

0.79 0.81
/Data Preprocessing (/)• Learning from the following dataset (⊥ is the missing value)
Feature 

Feature 

Feature 

Label

T
F
T
F
T

C
A
B
A
C

.
.
�
.
.



�

�







• Make a context in the data preprocessing phase






.T
×
×
×

.A
×
×

.B

.C
×

×
×

.
×

.
×
×
×
/

Make a Concept Lattice by FCA• Make a concept lattice∅from the context
1, 2, 3, 4, 5
1.T
1, 3, 5
3.1
2, 4, 5
2.A, 3.1
2, 4

1.T, 2.C
1, 5
1.T, 2.C, 3.1
5

1.T, 2.C, 3.0
1

1.T, 2.B
3

1.T, 2.A, 2.B, 2.C, 3.0, 3.1
∅

/

Learn Classiﬁcation Rules• Search the maximal cons∅
istent concepts
1, 2, 3, 4, 5

3.1
2, 4, 5
2.A, 3.1
2, 4

Labels 1: 1
2: 1
3: ⊥
1.T
4: 2
1, 3, 5 5: ⊥1.T, 2.C
1, 5
1.T, 2.C, 3.1
5

1.T, 2.C, 3.0
1

1.T, 2.B
3

1.T, 2.A, 2.B, 2.C, 3.0, 3.1
∅

/

Learn Classiﬁcation Rules• Search the maximal cons∅
istent concepts
1, 2, 3, 4, 5

3.1
2, 4, 5
2.A, 3.1
2, 4

Labels 1: 1
2: 1
3: ⊥
1.T
4: 2
1, 3, 5 5: ⊥1.T, 2.C
1, 5
1.T, 2.C, 3.1
5

1.T, 2.C, 3.0
1

1.T, 2.B
3

1.T, 2.A, 2.B, 2.C, 3.0, 3.1
∅

/

Data Preprocessing• Learning from the remaining dataFeature 
FF

Feature AA

Feature 
.
.

Label



• Reﬁne discretization, and obtain the following context
.T



.A
×
×

00

.B

.C

01

.00

10
0.54

.01

.10
×

.11
×

11
0.79
/

Make a Concept Lattice by FCA
2.A
2, 4

2.A, 3.10
2

2.A, 3.11
4

1.T, 2.A, 2.B, 2.C,
3.00, 3.01, 3.10, 3.11
∅

/

Learn Classiﬁcation Rules
Labels 2: 1
4: 2

2.A
2, 4

2.A, 3.10
2

2.A, 3.11
4

1.T, 2.A, 2.B, 2.C,
3.00, 3.01, 3.10, 3.11
∅

/

Classify Unlabeled Data
• We obtain classiﬁcation rules for each discretization level:ℛ = {ℛ1 , ℛ2 },ℛ1 = {({.T}, 1)},ℛ2 = {({.A, .10}, 1), ({.A, .11}, 2)}– Each ℛi is a set of pairs (attributes of a maximal concept,
a class label)• Classiﬁcation of unlabeled (test) data
– Datum (T, B, 0.45) belongs to class  since the st variable is T
– Datum (F, A, 0.84) belongs to class  since the nd variable is A and the rd variable is in [0.75, 1]
/Contents
. Problems and Motivation
. Flowchart of SELF
. Learning by SELF
i ) Data preprocessingii ) Make concepts by FCAiii ) Learn classiﬁcation rulesiv ) Classify unlabeled data
. Experiments
. Conclusion

/Methods
. SELF v.s. the decision tree-based method using mixedtype datasets
. SELF v.s. other SSL methods using continuous datasets• There is no SSL method for mixed-type datasets• SELF is implemented in R ..
• To enumerate all concepts, we use LCM [Uno et al., ]presented by Uno– One of the fastest algorithm• If  label candidates is more than two, we adopt the mode
– If there is no label candidate, we adopt the mode of labels of a training dataset
/Methods of Exp. • We used  mixed-type datasets from UCI repository• To check eﬀectivity of unlabeled data, we tested the following two cases
. Use labeled and unlabeled data for training
. Use only labeled data for training• We used the decision tree-based method in R for control• For reference, we used -NN using only continuous features• We used -fold cross validation– One fold is labeled training data, another one fold is test data,
and the other  folds are unlabeled training data
– We ﬁxed the number of labeled training data as ∼• We compared the accuracy
/Datasets for Exp. 
Name
ad
allbp
annealarrhythmia
australian
crx
echoc
heart
hepatitishorse Data











 Classes











Bin.











Nom.











Real.











/

Results for Exp. 
ad

allbp
96

86

94
Accuracy (%)

Accuracy (%)

84
82
70
78
76

92
90
88
86

74
0 20 40 60 80 100
The number of labeled data84

SELF(b)0 20 40 60 80 100
The number of labeled data
Tree

1-NN

SELF

/

Results for Exp. annealarrhythmia
55

75
Accuracy (%)

Accuracy (%)

50
70
65
60

45
40
35
30

0 20 40 60 80 100
The number of labeled data
SELF(b)0 20 40 60 80 100
The number of labeled data
Tree

1-NN

SELF

/

Results for Exp. 
australian
60

crx
60

55

Accuracy (%)

Accuracy (%)

58

50

56
54
52
50

45
0 20 40 60 80 100
The number of labeled data48

SELF(b)0 20 40 60 80 100
The number of labeled data
Tree

1-NN

SELF

/

Results for Exp. 
echoc

heart
58

65

Accuracy (%)

Accuracy (%)

60

60
55

56
54
52
50
48

0 20 40 60 80 100
The number of labeled data

46

SELF(b)0 20 40 60 80 100
The number of labeled data
Tree

1-NN

SELF

/

Results for Exp. 
hepatitis

horse
65

75

Accuracy (%)

Accuracy (%)

80

70
65

60
55
50

0 20 40 60 80 100
The number of labeled data
SELF(b)0 20 40 60 80 100
The number of labeled data
Tree

1-NN

SELF

/

Methods for Exp. • Use the benchmark datasets in [Chapelle et al., ]• Check two cases like exp. 
. Use labeled and unlabeled data for training
. Use only labeled data for training• Compared our results to those in [Chapelle et al., ]/Datasets for Exp. Name Data Classes

 features

g241c (D)g241d (D)Digit1 (D)USPS (D)COIL (D)BCI (D)






















/

Results for Exp.  (with  labeled data)
SELF(b)
SELF
-NN
SVM
MVU
LEM
QC
Disc.Reg.
TSVM
SGT
C.Kernel
D.Reg.
LDS
RLS
CHM

D

D

D

D

D

D

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
NA
.
.
.
.
NA

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
/

Results for Exp.  (with  labeled data)
SELF(b)
SELF
-NN
SVM
MVU
LEM
QC
Disc.Reg.
TSVM
SGT
C.Kernel
D.Reg.
LDS
RLS
CHM

D

D

D

D

D

D

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
NA
.
.
.
.
NA

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
/

Contents
. Problems and Motivation
. Flowchart of SELF
. Learning by SELF
i ) Data preprocessingii ) Make concepts by FCAiii ) Learn classiﬁcation rulesiv ) Classify unlabeled data
. Experiments
. Conclusion

/Conclusion• We have presented a semi-supervised learning (SSL)
method, SELF, for mixed-type data
• Contribution to the FCA:
– A novel application of FCA• Contribution to the KDD:
– The ﬁrst direct SSL method for mixed-type datasets∘ An original dataset is lifted to the concept lattice using FCA(Formal Concept Analysis)∘ Classiﬁcation rules are learned in the space– Moreover, SELF can apply to incomplete data with missing values
/Appendix

A-/A-Related Work (in FCA)
• Many studies used FCA for machine learning and knowledge discovery [Kuznetsov, ]– Classiﬁcation [Ganter and Kuznetsov, ; Ganter andKuznetsov, ]– Clustering [Zhang et al., ]– Association rule mining [Jaschke et al., ; Pasquier et al.,; Valtchev et al., ]– Bioinformatics [Blinova et al., ; Kaytoue et al., ;Kuznetsov and Samokhin, ]• Ganter and Kuznetsov attacked to the problem of binaryclassiﬁcation for real-valued data
– Their method discretizes real-valued variables by conceptual
scaling [Ganter and Wille, ], that are given a priori
A-/A-Related Work (in ML)• Decision tree-based methods, e.g., C. [Quinlan, ;Quinlan, ], can treat mixed-type data
• Discretization techniques [Fayyad and Irani, ; Liu etal., ; Skubacz and Hollmén, ]– Our approach is diﬀerent from them since we integrate discretization process into learning process and avoid overﬁtting• Kok and Domingos [Kok and Domingos, ] have proposed a learning method via hypergraph lifting– Construct clusters by hypergraphs and learns on them– it is diﬃcult to treat continuous variables in their approach

A-/A-Time Complexity• Data preprocessing takes O(nd)– n is the number of objects– d is the number of attributes• Making concepts takes O(Δ3 )– Δ = max{#J ∣ J ⊆ I, g = h for all (g, m), (h, l) ∈ J, or m = l
for all (g, m), (h, l) ∈ J}
• Judging consistency of concepts takes less than O(Λ)– Λ is the number of concepts at discretization level 1• The time complexity of SELF is O(nd) + O(Δ3 ) + O(Λ)

A-/A-

An Fatal Error Caused by Discretization• Solve the system of linear equations [Schroder, ]
40157959.0 x + 67108865.0 y = 1
67108864.5 x + 112147127.0 y = 0– Obtained by the well-known formulab1 a22 − b2 a12
b2 a11 − b1 a21x=, y=a11 a22 − a21 a12
a11 a22 − a21 a12• By ﬂoating point arithmetic with double precision variables (IEEE ) :x = 112147127, y = −67108864.5• The correct solution:x = 224294254, y = −134217729
A-/A-What is SSL?
• It is a special form of classiﬁcation• Goal: Using (large amount of ) unlabeled data eﬀectively,
together with labeled data, build better classiﬁers [Zhuand Goldberg, ]– Transductive learning focuses on classiﬁcation of unlabeleddata in the training data [Vapnik and Sterin, ]– In contrast, in SSL we treat learning of classiﬁcation rules andclassiﬁcation of unseen data

• Usual assumption: There are only few labeled data(∼) and lots of unlabeled data (∼)– Labeling costs high in real situation

A-/A-Data Preprocessing for Binary andNominal Variables• Goal: Make a context from a given dataset to use FCA– A context is a triple (G, M, I), G and M are sets and I ⊆ G × M∘ Elements in G and M are objects and attributes, resp.
∘ gIm means an object g has an attribute m∘ Represented by a cross-table• Strategy: Convert each feature in the given dataset into acontext, and merge into one context– First we make a context from discrete variables– The process of making a context from continuous variables isembedded into the learning process∘ Increase discretization level along with the learning process∘ We can avoid overﬁtting
A-/A-Data Preprocessing Algorithm for
Binary and Nominal Variables
Input: Dataset X = [xij ]n×q whose variables are binary or nominal
Output: Context (G, MBN , IBN )function ContextBN(X): G ← {1, 2, … , n}: for each j ∈ {1, 2, … , d}:
if the feature j of X is binary and has no missing value then:
Mj ← {T}, Ij ← {(i, xij ) ∣ i ∈ G and xij = T}:else if the feature j of X is binary and has missing value then:
Mj ← {T, F}, Ij ← {(i, xij ) ∣ i ∈ G and xij ≠ ⊥}:else // the feature j is nominal:Mj ← {1, … , vj }, Ij ← {(i, xij ) ∣ i ∈ G and xij ≠ ⊥}: combine (G, M1 , I1 ), (G, M2 , I2 ), … , (G, Md , Id ) into (G, MBN , IBN ): return (G, MBN , IBN )A-/A-Example of Data Preprocessing for
Discrete Variables• Data preprocessing for the following dataset


Feature 

Feature 

Feature 

T
F

�
F

C
�

– Features  and  are binary, and the feature  is nominal

A-/A-Example of Data Preprocessing for
Discrete Variables• Data preprocessing for the following dataset
Feature 

Feature 

Feature 

T
F

�
F

C
�




– Features  and  are binary, and the feature  is nominal• We obtain the context as follows:
.T



.T

.F

.A

.B

.C

×
A-/A-Example of Data Preprocessing for
Discrete Variables• Data preprocessing for the following dataset
Feature 

Feature 

Feature 

T
F

�
F

C
�




– Features  and  are binary, and the feature  is nominal• We obtain the context as follows:
.T



.T

.F

.A

.B

.C

×
×
A-/A-Example of Data Preprocessing for
Discrete Variables• Data preprocessing for the following dataset
Feature 

Feature 

Feature 

T
F

�
F

C
�




– Features  and  are binary, and the feature  is nominal• We obtain the context as follows:
.T



.T

.F

×

.A

.B

.C
×

×
A-/A-Data Preprocessing Algorithm forReal-Valued Variables
Input: Real-valued dataset X and discretization level k
Output: Context (G, MR , IR )function ContextR(X, k)
: G ← {1, 2, … , n}: for each j ∈ {1, 2, … , d}:
Mj ← {1, 2, … , βk }:Normalize Xj by min-max normalization
:for each i ∈ {1, 2, … , n}:
if xij = 0 then Ij ← Ij ∪ {(i, 1)}
̸ and xij =⊥̸ then:else if xij =0:
Ij ← Ij ∪ {(i, m)}, where xij ∈ ((m − 1)/βk , m/βk ]: combine (G, M1 , I1 ), (G, M2 , I2 ), … , (G, Md , Id ) into (G, MR , IR ): return (G, MR , IR )A-/A-

Discretization level

Discretization by Binary Encoding
5
4
3

000

2

001

010

00

1

011

100

01

110

10

0
0

101

111

11
1

0.5

1

A-/A-Example of Data Preprocessing forReal-Valued Variables• Data preprocessing for the following dataset


Feature 
TF

Feature 
.
.

Feature .
�– Features  is binary, and feature  and  are real-valued

A-/A-Example of Data Preprocessing forReal-Valued Variables• Data preprocessing for the following dataset
Feature 
TFFeature 
.
.

Feature .
�– Features  is binary, and feature  and  are real-valued• At discretization level , we obtain the context as follows:
.T



.0

.1

.0

.1

×
A-/A-Example of Data Preprocessing forReal-Valued Variables• Data preprocessing for the following dataset


Feature 
TF

Feature 
.
.

Feature .
�– Features  is binary, and feature  and  are real-valued• At discretization level , we obtain the context as follows:
0

1
0.35

0.78 0.813
A-/A-Example of Data Preprocessing forReal-Valued Variables• Data preprocessing for the following dataset
Feature 
TFFeature 
.
.

Feature .
�– Features  is binary, and feature  and  are real-valued• At discretization level , we obtain the context as follows:



.T

.0

×

×

.1

.0

.1

×
A-/A-Example of Data Preprocessing forReal-Valued Variables• Data preprocessing for the following dataset
Feature 
TFFeature 
.
.

Feature .
�– Features  is binary, and feature  and  are real-valued• At discretization level , we obtain the context as follows:



.T

.0

×

×

.1

.0

.1
×

×
A-/A-Formal Concept Analysis (FCA)• Generate a concept lattice using the algebraic “closed”
property• For A ⊆ G and B ⊆ M of a context (G, M, I),
A = {m ∈ M ∣ (∀g ∈ A) gIm}, B = {g ∈ G ∣ (∀m ∈ B) gIm}
• A concept of a (G, M, I) is a pair (A, B) (A ⊆ G, B ⊆ M) suchthat A = B and B = A– A is an extent and B is an interior, A is extent ⟺ A = A’
– ℬ(G, M, I) is the set of concept• For concepts (A1 , B1 ), (A2 , B2 ), A1 ⊆ A2 ⇒ (A1 , B1 ) ≤ (A2 , B2 )(A1 , B1 ) ≤ (A2 , B2 ) ⟺ A1 ⊆ A1 ⟺ B1 ⊇ B2
• ≤ is an order of ℬ(G, M, I), ⟨ℬ(G, M, I), ≤⟩ is a complete lattice
A-/A-– The concept lattice of a context (G, M, I)

A-/A-Example of FCA• Given the following context






A

B

×

×
×

C

D

E

×
×

×

×
×

×

• There are  concepts as follows:– (∅, {A, B, C, D, E}), ({1}, {A, B, D}), ({2}, {B, D, E}),({3}, {C}), ({1, 2}, {B, D}), ({2, 4}, {B, E}), ({1, 2, 4}, {B}),({1, 2, 3, 4}, ∅).
• The concept lattice is constructed from these concepts
A-/A-Example of FCA∅
1234

XY denotes the set {X, Y}

B
124
BD
12

BE
24
C
3

BDE
2

ABD
1

ABCDE
∅

A-/A-Learning Classiﬁcation Rules• Idea: If the label of an object in a concept is c, those of theother objects in the same concept are also c• Basic strategy: Search the concept lattice from the top
concept, and ﬁnd maximal and consistent concepts– The attribute B of such a concept (A, B) is a rule
∘ A is a dataset classiﬁed to the class by the rule B– Each concept can be viewed as a base cluster• For each object g ∈ G, g’s label is denoted by γ(g)– Γ(G) ≔ {g ∈ G ∣ γ(g) ≠ ⊥}∘ γ(g) = ⊥ ⟺ g is unlabeled data
• For a concept (A, B), if Γ(A) ≠ ∅ and γ(g) = γ(h) for all g, h ∈ Γ(A),then (A, B) is consistentA-/A-The SELF Algorithm (/)Input: Dataset X with n objects and d attributes
Output: A set of classiﬁcation rules ℛ
function Main(X): Divide X into two datasets XBN and XR , where XBN contains
all binary and nominal variables in X, and XR contains all
real-valued variables in X
: (G, MBN , IBN ) ← ContextBN(XBN )// make a context from binary and nominal variables of X
: k ← 1 // k is level of discretization
: ℛ ← Learning(XR , G, MBN , IBN , k, ∅)// use this function recursively
: return ℛA-/A-The SELF Algorithm (/)function Learning(XR , G, MBN , IBN , k, ℛ)
: (G, MR , IR ) ← ContextR(XR , k)// make a context from real-valued variables of X at level k
: make (G, M, I) from (G, MBN , IBN ) and (G, MR , IR ): build the concept lattice 𝔅(G, M, I) from (G, M, I)
: 𝒞 ← {(A, B) ∈ 𝔅(G, M, I) ∣ (A, B) is consistent}
: ℛk ← {(B, γ(a)) ∣ (A, B) ∈ Max𝒞 and a ∈ Γ(A)}: ℛ ← ℛ ∪ (ℛk , k) // add the current result ℛk
: G ← G ⧵ {g ∣ g ∈ A for some (A, B) ∈ 𝒞}
: remove corresponding attributes and relations from MBN
and IBN , respectively
: remove corresponding objects from XR
: if Γ(G) = ∅ then return ℛ
: else return Learning(XR , G, MBN , IBN , k + 1, ℛ)
: end if
A-/A-Classify unlabeled data
• Assume we obtain the rules ℛ = {ℛ1 , … , ℛk } by SELF
• To classify a test datum, check rules from ℛ1 to ℛk• For each level k,
. Make a context (G, M, I) by data preprocessing
. Enumerate all l such that B ⊆ M for (B, l) ∈ ℛk
• We obtain label candidates L = {l1 , … , lc } and sometimes
cannot decide an unique label– All one-against-all classiﬁcation methods have the sameproblem∘ One of future works

A-/A-Classiﬁcation Algorithm
Input: Classiﬁcation rules ℛ = {ℛ1 , ℛ2 , … , ℛK } and x = [xij ]1×d
Output: Label candidates L = {l1 , l2 , … , lC }function Classify(R, x)
: L ← ∅: divide x into two data xBN and xR , where xBN contains all
binary and nominal variables, xR contains all real-valued
variables
: (G, MBN , IBN ) ← ContextBN(xBN )// make a context from binary and nominal variables of x
: for each k ∈ {1, 2, … , K}
:(G, MR , IR ) ← ContextR(xR , k)// make a context from real-valued variables of x at level k:make the context (G, M, I) from (G, MBN , IBN ) and (G, MR , IR ):
add l to L if R ∈ M for some (R, l) ∈ ℛk
: end for; return LA-/A-References[Abe, ] S. Abe. Analysis of multiclass support vector machines. In Proceedings of International Conference on Computational Intelligence forModeling Control and Automation, pages –, .
[Blinova et al., ] V. G. Blinova, D. A. Dobrynin, V. K. Finn, S. O. Kuznetsov,
and E. S. Pankratova. Toxicology analysis by means of the JSMmethod. Bioinformatics, ():–, .
[Chapelle et al., ] O. Chapelle, B. Schölkopf, and A. Zien, editors. SemiSupervised Learning. MIT Press, .
[Davey and Priestley, ] B. A. Davey and H. A. Priestley. Introduction tolattices and order. Cambridge University Press,  edition, .
[de Brecht and Yamamoto, ] Matthew de Brecht and Akihiro Yamamoto. Topological properties of concept spaces (full version). Information and Computation, :–, .
[Fayyad and Irani, ] U. M. Fayyad and K. B. Irani. Multi-interval discretization of continuous-valued attributes for classiﬁcation learning.

A-/A-

In Proceedings of the th International Joint Conference on Artiﬁcial Intelligence, pages –, .
[Frank and Asuncion, ] A. Frank and A. Asuncion. UCI machine learning repository, .
[Ganter and Kuznetsov, ] B. Ganter and S. Kuznetsov. Formalizing hypotheses with concepts. In B. Ganter and G. W. Mineau, editors,
Conceptual Structures: Logical, Linguistic, and Computational Issues,volume  of Lecture Notes in Computer Science, pages –.
Springer, .
[Ganter and Kuznetsov, ] B. Ganter and S. Kuznetsov. Hypotheses andversion spaces. In A. de Moor, W. Lex, and B. Ganter, editors, Conceptual Structures for Knowledge Creation and Communication, volume
 of Lecture Notes in Computer Science, pages –. Springer,.
[Ganter and Wille, ] B. Ganter and R. Wille. Formal Concept Analysis:
Mathematical Foundations. Springer, .
[Garcia-Molina et al., ] H. Garcia-Molina, J. D. Ullman, and J. Widom.
Database systems: The complete book. Prentice Hall Press, .

A-/A-[Han and Kamber, ] J. Han and M. Kamber. Data Mining. Morgan Kaufmann,  edition, .
[Jaschke et al., ] R. Jaschke, A. Hotho, C. Schmitz, B. Ganter, and
G. Stumme. TRIAS–An algorithm for mining iceberg tri-lattices. In Proceedings of the th International Conference on Data Mining (ICDM’),
pages –. IEEE, .
[Kaytoue et al., ] M. Kaytoue, S. O. Kuznetsov, A. Napoli, and S. Duplessis. Mining gene expression data with pattern structures in formal
concept analysis. Information Sciences, .
[Kok and Domingos, ] S. Kok and P. Domingos. Learning Markov logic
network structure via hypergraph lifting. In Proceedings of the thInternational Conference on Machine Learning, pages –, .
[Kuznetsov and Samokhin, ] S. O. Kuznetsov and M. V. Samokhin.
Learning closed sets of labeled graphs for chemical applications. In
S. Kramer and B. Pfahringer, editors, Inductive Logic Programming,volume  of Lecture Notes in Computer Science, pages –.
Springer, .
[Kuznetsov, ] S. O. Kuznetsov. Machine learning and formal concept

A-/A-analysis. In P. Eklund, editor, Concept Lattices, volume  of Lecture
Notes in Computer Science, pages –. Springer, .
[Liu et al., ] H. Liu, F. Hussain, C. L. Tan, and M. Dash. Discretization: An enabling technique. Data Mining and Knowledge Discovery,
():–, .
[Makino and Uno, ] K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. Algorithm Theory-SWAT , pages
–, .
[Murthy, ] S. K. Murthy. Automatic construction of decision trees from
data: A multi-disciplinary survey. Data Mining and Knowledge Discovery, ():–, .
[Pasquier et al., ] N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Eﬃcient mining of association rules using closed itemset lattices. Information Systems, ():–, .
[Quinlan, ] J. R. Quinlan. C.: programs for machine learning. Morgan
Kaufmann, .
[Quinlan, ] J. R. Quinlan. Improved use of continuous attributes inC.. Journal of Artiﬁcial Intelligence Research, :–, .

A-/A-[R Development Core Team, ] R Development Core Team. R: A Language and Environment for Statistical Computing. R Foundation for
Statistical Computing, .
[Ripley, ] B. D. Ripley. Pattern Recognition and Neural Networks. Cambridge University Press, .
[Skubacz and Hollmén, ] M. Skubacz and J. Hollmén. Quantization ofcontinuous input variables for binary classiﬁcation. In Intelligent Data
Engineering and Automated Learning — IDEAL . Data Mining, Financial Engineering, and Intelligent Agents, volume  of Lecture
Notes in Computer Science, pages –. Springer, .
[Sugiyama and Yamamoto, ] M. Sugiyama and A. Yamamoto. The
coding divergence for measuring the complexity of separating two
sets. In Proceedings of nd Asian Conference on Machine Learning,volume  of JMLR Workshop and Conference Proceedings, pages
–, .
[Uno et al., ] T. Uno, M. Kiyomi, and H. Arimura. LCM ver. : Collaboration of array, bitmap and preﬁx tree for frequent itemset mining.
In Proceedings of the st International Workshop on Open Source Data
Mining: Frequent Pattern Mining Implementations, pages –. ACM,

A-/A-.
[Valtchev et al., ] P. Valtchev, R. Missaoui, and R. Godin. Formal concept analysis for knowledge discovery and data mining: The newchallenges. Concept Lattices, pages –, .
[Vapnik and Sterin, ] V. Vapnik and A. Sterin. On structural risk minimization or overall risk in a problem of pattern recognition. Automation and Remote Control, ():–, .
[Vapnik, ] V. N. Vapnik.
The nature of statistical learning theory.
Springer, .
[Zhang et al., ] Y. Zhang, B. Feng, and Y. Xue. A new search results clustering algorithm based on formal concept analysis. In Proceedings ofth International Conference on Fuzzy Systems and Knowledge Discovery, pages –. IEEE, .
[Zhu and Goldberg, ] X. Zhu and A. B. Goldberg. Introduction to semisupervised learning. Morgan and Claypool Publishers, .

A-/A-