Other Classification Methods

1. Genetic Algorithms (GA)

Evolution-inspired search over a population of chromosomes (candidate solutions) using selection, crossover and mutation. Each chromosome may encode rule conditions (0/1 bits for "attribute included or not", interval boundaries for numeric attributes) and a class; fitness = rule quality (accuracy/coverage/length).

 1. initialise population P of rules randomly        (encode: cond1 cond2 ... class)
 2. evaluate fitness:  fitness = accuracy^2 * coverage  (or (TP-NP)/T, ...)
 3. repeat
      select parents (roulette wheel / tournament, proportional to fitness)
      crossover  (single point / two point)  -> offspring
      mutate with a small probability p_m (flip a bit / widen an interval)
      replace least-fit individuals with the best offspring
    until sufficient quality is reached or generations exceeded
 4. return the best chromosome(s) as rules / classifier

Fitness function example where TP/NP are true/false positives and $T$ is the number of target-class tuples:

\text{fitness}(r)=\frac{TP}{T}\times\frac{TP-NP}{TP+NP}

Strength: searches a huge rule space in parallel, immune to local optima traps, uses only fitness values (derivative-free). Weakness: needs careful encoding and many parameters, slow, no guarantee of optimality, results vary over runs.

2. Rough Set Approach

Rough sets (Pawlak) handle vague, inconsistent and incomplete data without any external parameter or probability assumption. The set of tuples is approximated by two definable sets from equivalence classes induced by attribute values:

Lower approximation $\underline{R}(X)$ — tuples certainly in $X$ ,
Upper approximation $\overline{R}(X)$ — tuples possibly in $X$ ,
Boundary region $BN_R(X)=\overline{R}(X)-\underline R(X)$ — cannot be decided.

\text{Accuracy of approximation: } \alpha_R(X)=\frac{|\underline{R}(X)|}{|\overline{R}(X)|},\qquad \text{Quality: } \gamma = \frac{|\bigcup \underline{R}(X_i)|}{|U|}

Reduct = minimal subset of attributes preserving the same classification power as the full set; core = intersection of all reducts. Reducts are found with the discernibility matrix and generate if-then decision rules from the lower approximations.

3. Fuzzy Set Approaches

Real data are often "fuzzy" — income may be partly low and partly medium. A fuzzy set $F = \{(x,\mu_F(x))\}$ assigns a membership degree $\mu_F(x)\in[0,1]$ instead of crisp 0/1 membership.

Fuzzy if-then rules: IF age is Young(0.7) AND income is High(0.4) THEN credit is Good (0.6); inference combines memberships by min (AND), max (OR), product.
Fuzzy clustering (fuzzy c-means) allows a point to belong to many clusters with a degree; fuzzy decision trees split using fuzzy entropy.
Advantage: tolerates imprecise/vague attribute values and gives smooth, robust boundaries; disadvantage: membership functions must be defined (domain knowledge) and rule sets get large.

4. Bayesian Belief Networks (BBN)

A directed acyclic graph where nodes are random variables and edges encode conditional dependencies; each node stores a conditional probability table (CPT) giving $P(X_i \mid \text{Parents}(X_i))$ . Unlike naive Bayes, attributes need not be conditionally independent given the class.

Joint probability factorisation:

P(x_1,\dots,x_n)=\prod_{i=1}^{n}P\big(x_i \mid \text{Parents}(x_i)\big)

  FamilyHistory ---> Gene ---> LungCancer <--- Smoking
                                  |   |
                                  v   v
                            PositiveXray  Dyspnoea
  P(LungCancer=yes | Gene=yes, Smoking=yes) = 0.85   (one CPT entry)

Learning: parameters estimated from data (MLE/Bayesian estimates); structure learned by search (hill climbing with a scoring metric such as BIC/MDL) or supplied by experts. Inference for classification computes the most probable class with exact (variable elimination, junction tree) or approximate (Gibbs sampling, loopy belief propagation) methods.

Advantages: principled handling of uncertainty, missing values and causal knowledge; graphical, understandable structure. Limitations: structure learning is NP-hard; exact inference is expensive for large/cyclic networks; needs enough data to estimate CPTs.

5. Instance-Based k-NN and Case-Based Reasoning

Covered under Lazy Learners; k-NN is memory based, and case-based reasoning (CBR) generalises it by storing rich cases and using adaptation/repair rules to solve new problems (help desk, medical diagnosis, legal reasoning).

6. Semi-Supervised / Active Learning and Other Miscellaneous Methods

Method	Core idea
Semi-supervised classification	Use a large unlabeled set plus a small labeled set (self-training, co-training, transductive SVM); reduces labelling cost
Active learning	The classifier asks a human to label the most informative tuples (uncertainty sampling, query by committee)
Multiclass / one-class classification	One-vs-rest, one-vs-one, and one-class SVM for novelty/anomaly detection with a single class of training data
Fuzzy-GA hybrid	GA evolves fuzzy rule sets, membership functions tuned jointly
Rough-neuro / rough-GA hybrids	Reducts from rough sets reduce attributes then a neural net or GA classifier is trained
Transfer learning / domain adaptation	Knowledge from a related source domain is reused when target labelled data are scarce

7. Comparison Summary

Method	Handles uncertainty	Interpretable	Needs parameters	Typical strength
Naive Bayes	Yes (probabilities)	Partly	Very few	Fast, robust, text
Bayesian belief network	Yes	Yes (graph)	Structure + CPTs	Causal, correlated attributes
Genetic algorithm	Yes (via fitness)	Rules yes	Many (pop, p_c, p_m)	Global search for rules
Rough sets	Yes (approximations)	Yes (reducts, rules)	None	Inconsistent/incomplete data, attribute reduction
Fuzzy sets	Yes (membership)	Yes (fuzzy rules)	Membership functions	Vague linguistic attributes
k-NN / CBR	No (distance)	Little	k, distance metric	Non-linear, incremental

8. Exam Points

Explain the genetic algorithm approach to classification with the fitness function and operators — 7-10 marks (frequent).
Explain the rough-set approach: lower/upper approximation, boundary region, reduct, core, accuracy — 7-10 marks.
Short note on fuzzy sets and fuzzy classification — 5 marks.
Explain Bayesian belief networks with a CPT example and inference — 10 marks.
Compare any of these methods in a table — 5 marks.

Other Classification Methods