PadhaikoAll subjects

Output: Knowledge Representation

Data Mining (ENCT 435)

Open in the Padhaiko app

3.1 Representing knowledge as tables and linear models

Once a data mining algorithm processes input instances, it outputs a concept description—the learned knowledge structure used to explain patterns or predict unseen cases. Different tasks and attribute types call for different output representations.

1. Decision Tables

A decision table is the simplest way to represent learned knowledge: it selects a compact subset of relevant attributes and tabulates every observed combination of their values together with the predicted class (or default majority class when a combination has no exact match).

Example Decision Table on Two Weather Attributes
OutlookHumidityPredicted Play
SunnyHighNo
SunnyNormalYes
OvercastHighYes
OvercastNormalYes
RainyHighYes (majority)
RainyNormalYes

2. Linear Models

When input attributes are predominantly numeric, knowledge is naturally expressed as a linear model—a weighted sum of the input features :

Definition

Linear Regression and Linear Classification

where is the bias (intercept) and measures how much changes per unit increase in attribute .

For multi-class classification with classes, linear models generalize in two ways:

  1. One-vs-All (One-vs-Rest): Learn separate linear discriminants (each separating class from all other classes) and assign .
  2. Pairwise (All-Pairs): Learn binary hyperplanes—one for every pair of classes—and classify by majority vote.

3.2 Decision trees and various types of rules (classification, association, rules with exceptions)

1. Decision Trees

A decision tree represents knowledge hierarchically as a rooted directed tree using a divide-and-conquer structure:

To classify a new instance, start at the root, evaluate each node's test, follow the matching branch, and return the label at the leaf. Missing attribute values during prediction are handled by sending fractional instance weights down each branch proportional to training frequencies and combining the resulting leaf class probabilities.

2. Classification Rules

A classification rule has the form:

where the antecedent is a conjunction () of attribute tests, and the consequent specifies a single fixed target class. Every root-to-leaf path in a decision tree can be read directly as an IF-THEN classification rule.

Replicated Subtree Problem & Conflict Resolution

Although trees convert directly into rules, rules are often more compact because decision trees suffer from the replicated subtree problem: when a disjunctive rule such as (a = 1 AND b = 1) OR (c = 1 AND d = 1) => class = X holds, a single-root tree must duplicate the (c = 1 AND d = 1) subtree under multiple branches of a and b.

Because independent rules can overlap (two rules firing with different classes) or leave gaps (no rule fires), rule sets require an execution policy:

3. Association Rules

Association rules look syntactically like classification rules (Antecedent => Consequent), except any attribute (or set of attributes) may appear on either side—not just a designated target class—and a single rule may predict multiple attributes at once.

AspectClassification RulesAssociation Rules
Consequent (RHS)Always a single designated class attributeAny item or attribute-value combination
GoalPredict the class of unseen instancesDiscover strong co-occurrence relationships in data
Key Quality MetricsAccuracy, error rate, precision/recallSupport (coverage) and Confidence (accuracy), Lift
Interaction Between RulesEvaluated together as a classifier (decision list or vote)Interpreted individually as self-contained insights

For an association rule over instances:

4. Rules with Exceptions

Human experts naturally state knowledge as general defaults followed by exceptions rather than rewriting dozens of long rules. Rules with exceptions (related to Ripple-Down Rules) formalize this as:

Syntax of Rules with ExceptionsText
default:  class = no_lenses
except if tear_rate = normal AND astigmatism = no:
    class = soft
    except if age = presbyopic AND prescription = myope:
        class = no_lenses

A new instance starts at the default conclusion and descends into any matching except if clause (and nested exceptions) until no deeper exception applies. This keeps the rule base readable and modular: adding a rare edge case only appends a local except if branch without altering existing general rules.


3.3 Instance-based and cluster representations

1. Instance-Based Representation

Unlike trees, rules, or linear equations that summarize training data into explicit abstractions and discard the raw rows, instance-based representation (lazy learning) stores the training instances themselves as the knowledge base.

2. Cluster Representations

When data is unlabeled (unsupervised clustering), the output is a structural description of how instances group together. Four standard representations exist:

Four Forms of Cluster Output Representation
RepresentationDescriptionExample Output Structure
Exclusive (Partitioning)Each instance belongs to exactly one clusterDisjoint sets or centroid coordinates
OverlappingAn instance may belong to more than one cluster simultaneouslyMulti-label membership matrix (e.g., documents in multiple topics)
Probabilistic (Soft)Each instance has a degree/probability of membership in every cluster ()Vector from a Gaussian Mixture Model
HierarchicalClusters are nested in a tree (dendrogram) from individual points at leaves to one cluster at the rootBinary merge tree cut at a chosen distance threshold

Worked Examples

Example 1

Evaluating a Linear Classification Hyperplane (5 marks)

A linear classifier separates two classes (Approve vs. Reject) using two normalized attributes: credit score and income ratio , with decision function:

Predict Approve when and Reject when . Classify the three applicants:

Evaluating applicant :

Evaluating applicant :

Evaluating applicant :

Answer:
  • : Approve
  • : Reject
  • : Approve (boundary point on )
Example 2

Extracting Rules from a Decision Tree and Computing Association Metrics (6 marks)

Suppose a small store tracks customer transactions:

  1. Compute the support count, support (fraction), and confidence of the association rule:
  1. Explain how this association rule differs in output role from a classification rule extracted from a decision tree predicting Buy_Milk.

Computing support and confidence of : Let and . Here , , and :

Computing confidence:

Comparing with a classification rule: A classification rule restricts its consequent solely to the pre-selected target class Buy_Milk and forms part of a mutually coordinating classifier designed to label every transaction. By contrast, an association rule discovers any strong co-occurrence among items (Milk => Bread, Bread => Butter, etc.) and is judged individually by support and confidence rather than global classification accuracy.

Answer:
  1. Support count , support (), and confidence ().
  2. Association rules allow any attribute combination on either side and evaluate local co-occurrence strength, whereas classification rules always predict one fixed target class as part of a predictive model.
Example 3

Comparing Instance-Based Classification and Soft Cluster Representation (5 marks)

In a feature space, an instance-based classifier stores two labeled prototypes:

  1. Classify the query point using -Nearest Neighbor (-NN) with Euclidean distance.
  2. Suppose an unsupervised probabilistic clustering model instead outputs soft cluster memberships for across three clusters as . Explain what this vector represents and how it differs from an exclusive partition.

Computing Euclidean distances from to both prototypes:

Since , is the nearest prototype, so -NN predicts High.

Interpreting the probabilistic cluster representation: The vector sums to and indicates that has a posterior probability of belonging to Cluster , to Cluster , and to Cluster . Unlike an exclusive (hard) partition—which forces strictly into Cluster and discards ambiguity—a probabilistic representation captures boundary uncertainty and partial similarity to multiple clusters.

Answer:
  1. and ; -NN classifies as High.
  2. represents soft cluster membership probabilities summing to , preserving uncertainty for boundary points unlike exclusive partitioning.

Exercises

Practice Exercises — Knowledge Representation

Question 1

What is a decision table? If a dataset has nominal attributes with , , and possible values respectively, how many rows are required for a complete decision table, and what is the primary limitation of decision tables on wide datasets?

Definition and Table Size Calculation: A decision table maps combinations of chosen attribute values directly to predicted class labels. With nominal attributes having , , and values, the total number of distinct attribute-value combinations is:

Primary Limitation on Wide Datasets: As the number of attributes grows, the table size grows exponentially as (combinatorial explosion), causing most combinations to be unrepresented in training data and demanding heavy feature selection beforehand.

Answer:

A decision table maps attribute-value combinations directly to predicted classes. For attributes of sizes , a full table needs rows. Its main limitation is exponential table growth when many attributes are included.

Question 2

Explain the replicated subtree problem in decision trees and compare ordered decision lists with unordered rule sets for resolving rule conflicts.

Replicated Subtree Problem: When a concept includes a disjunction of conjunctions—such as (A = 1 AND B = 1) OR (C = 1 AND D = 1)—a single-root decision tree must pick one attribute first (say A) and then repeat the entire (C = 1 AND D = 1) subtree under multiple branches (A = 0, A = 1, B = 0). Classification rules avoid this duplication by writing two independent IF-THEN rules.

Ordered vs. Unordered Rule Conflict Resolution:

  • Ordered rules (decision list): Rules are checked sequentially top-to-bottom; the first rule whose conditions match fires immediately, avoiding ambiguity, though individual rules cannot be interpreted in isolation without considering earlier rules.
  • Unordered rules: Every rule is evaluated independently, making each rule self-contained; if multiple conflicting rules fire, resolution uses majority vote, highest rule accuracy/confidence, or a default fallback class if none fire.
Answer:

The replicated subtree problem occurs when a tree duplicates identical subtrees across multiple branches to represent disjunctive concepts. Ordered decision lists resolve conflicts by firing the first matching rule top-to-bottom, whereas unordered rules are self-contained and resolve conflicts by voting or confidence ranking.

Question 3

What are rules with exceptions (ripple-down rules), and why are they often preferred by human domain experts over flat lists of independent classification rules?

Structure of Rules with Exceptions: Rules with exceptions start from a broad default conclusion and attach nested except if <condition> then <new class> overrides for special cases. Evaluation walks down matching exceptions until no deeper exception applies.

Practical Advantage: Human experts naturally think in terms of general principles plus edge-case exceptions. Adding a new exception modifies only a local branch without breaking or requiring re-verification of unrelated general rules, keeping the rule base compact and maintainable.

Answer:

Rules with exceptions represent knowledge as a default rule overridden by nested except if clauses. They match human reasoning and allow incremental updates for rare edge cases without rewriting the rest of the rule base.

Question 4

In a dataset of student records, students satisfy Attendance = High and StudyHours >= 10, and of those students also achieve Grade = A.

  1. Calculate the support and confidence of the rule Attendance = High AND StudyHours >= 10 => Grade = A.
  2. State whether this syntax could represent either a classification rule or an association rule, and explain what distinguishes the two.

Computing Support and Confidence: With , antecedent count , and joint count :

Classification vs. Association Rule: Because Grade is the single target outcome, this rule looks like a classification rule. However, an association rule framework allows any attribute (including Grade = A => Attendance = High or multi-item consequents) to appear on the right-hand side and evaluates each rule independently using support/confidence rather than predicting a single target variable.

Answer:
  1. Support (), Confidence ().
  2. Classification rules fix a single target class in the consequent to classify unseen rows, whereas association rules allow any attribute combination on either side to reveal general co-occurrence patterns.
Question 5

Compare the four types of cluster representations (exclusive, overlapping, probabilistic, hierarchical), and classify the query point using the linear discriminant (predict Positive if , else Negative), then check against a second hyperplane .

Four Types of Cluster Representations:

  1. Exclusive: Disjoint partition where every instance belongs to one and only one cluster.
  2. Overlapping: Instances may belong to multiple clusters simultaneously.
  3. Probabilistic (Soft): Each instance has a membership probability vector across all clusters summing to .
  4. Hierarchical: Nested tree of clusters (dendrogram) revealing clustering granularity across distance scales.

Evaluating Both Linear Discriminants at :

Answer:

Cluster outputs can be exclusive (disjoint), overlapping (multi-cluster), probabilistic (soft weights summing to ), or hierarchical (dendrogram). At , (Positive) and (Positive, directly on the hyperplane).

← Input: Concepts, Instances, and AttributesAlgorithms: The Basic Methods →