Output: Knowledge Representation
Open in the Padhaiko app3.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).
| Outlook | Humidity | Predicted Play |
|---|---|---|
| Sunny | High | No |
| Sunny | Normal | Yes |
| Overcast | High | Yes |
| Overcast | Normal | Yes |
| Rainy | High | Yes (majority) |
| Rainy | Normal | Yes |
- Strengths: Completely transparent, easy for domain experts to audit, and fast to evaluate via table lookup.
- Limitations: If nominal attributes each have values, a full table requires rows (combinatorial explosion), so decision tables work well only after aggressive feature selection removes irrelevant attributes. Numeric attributes must first be discretized into bins.
2. Linear Models
When input attributes are predominantly numeric, knowledge is naturally expressed as a linear model—a weighted sum of the input features :
Linear Regression and Linear Classification
- Linear Regression (Numeric Prediction): Predicts a continuous target as:
where is the bias (intercept) and measures how much changes per unit increase in attribute .
- Linear Classification (Separating Hyperplane): In binary classification with classes (or ), a linear model defines a hyperplane separating the feature space into two half-spaces:
For multi-class classification with classes, linear models generalize in two ways:
- One-vs-All (One-vs-Rest): Learn separate linear discriminants (each separating class from all other classes) and assign .
- Pairwise (All-Pairs): Learn binary hyperplanes—one for every pair of classes—and classify by majority vote.
- Strengths & Limitations: Linear models are compact ( weights), fast to evaluate, and handle correlated numeric features smoothly, but they cannot capture nonlinear relationships or XOR-like feature interactions unless new interaction/nonlinear features are engineered.
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:
- Internal Nodes: Test a single attribute. Nominal attributes usually branch into one child per attribute value (multi-way split) or subset; numeric attributes split on a threshold ( vs. ).
- Branches: Represent the outcomes of the parent node's test.
- Leaf Nodes: Give the final classification label (or, in regression/model trees, a constant average or a linear regression equation).
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:
- Ordered Rules (Decision List): Test rules strictly top-to-bottom and return the first matching rule, ending with a catch-all
DEFAULTrule. - Unordered Rules: Evaluate all matching rules; resolve conflicts via majority vote, highest confidence, or fallback to a default class.
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.
| Aspect | Classification Rules | Association Rules |
|---|---|---|
| Consequent (RHS) | Always a single designated class attribute | Any item or attribute-value combination |
| Goal | Predict the class of unseen instances | Discover strong co-occurrence relationships in data |
| Key Quality Metrics | Accuracy, error rate, precision/recall | Support (coverage) and Confidence (accuracy), Lift |
| Interaction Between Rules | Evaluated together as a classifier (decision list or vote) | Interpreted individually as self-contained insights |
For an association rule over instances:
- Support (Coverage): Number or fraction of instances containing : .
- Confidence (Accuracy): Conditional probability that holds given : .
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:
default: class = no_lenses
except if tear_rate = normal AND astigmatism = no:
class = soft
except if age = presbyopic AND prescription = myope:
class = no_lensesA 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.
- Nearest-Neighbor Classification: To classify a query instance , compute its distance to all stored instances (e.g., Euclidean distance for normalized numeric attributes, or Hamming mismatch for nominal attributes) and assign the class of the closest instance (-NN) or the majority vote of the closest instances (-NN).
- Geometric Meaning (Voronoi Diagram): In -NN over continuous space, each stored prototype carves out a convex polygonal Voronoi cell containing all points closer to it than to any other stored point.
- Prototype Pruning / Exemplars: Storing every training row consumes memory and lookup time. Instance-based representations often retain only representative exemplars (critical boundary points or cluster prototypes) and discard redundant interior instances.
2. Cluster Representations
When data is unlabeled (unsupervised clustering), the output is a structural description of how instances group together. Four standard representations exist:
| Representation | Description | Example Output Structure |
|---|---|---|
| Exclusive (Partitioning) | Each instance belongs to exactly one cluster | Disjoint sets or centroid coordinates |
| Overlapping | An instance may belong to more than one cluster simultaneously | Multi-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 |
| Hierarchical | Clusters are nested in a tree (dendrogram) from individual points at leaves to one cluster at the root | Binary merge tree cut at a chosen distance threshold |
Worked Examples
Evaluating a Linear Classification Hyperplane
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 :
- : Approve
- : Reject
- : Approve (boundary point on )
Extracting Rules from a Decision Tree and Computing Association Metrics
Suppose a small store tracks customer transactions:
4transactions contain{Bread, Butter}.3transactions contain{Bread, Butter, Milk}.5transactions contain{Milk}in total.
- Compute the support count, support (fraction), and confidence of the association rule:
- 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.
- Support count , support (), and confidence ().
- 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.
Comparing Instance-Based Classification and Soft Cluster Representation
In a feature space, an instance-based classifier stores two labeled prototypes:
- with class
Low - with class
High
- Classify the query point using -Nearest Neighbor (-NN) with Euclidean distance.
- 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.
- and ; -NN classifies as
High. - represents soft cluster membership probabilities summing to , preserving uncertainty for boundary points unlike exclusive partitioning.
Exercises
Practice Exercises — Knowledge Representation
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.
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.
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.
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.
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.
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.
In a dataset of student records, students satisfy Attendance = High and StudyHours >= 10, and of those students also achieve Grade = A.
- Calculate the support and confidence of the rule
Attendance = High AND StudyHours >= 10 => Grade = A. - 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.
- Support (), Confidence ().
- 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.
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:
- Exclusive: Disjoint partition where every instance belongs to one and only one cluster.
- Overlapping: Instances may belong to multiple clusters simultaneously.
- Probabilistic (Soft): Each instance has a membership probability vector across all clusters summing to .
- Hierarchical: Nested tree of clusters (dendrogram) revealing clustering granularity across distance scales.
Evaluating Both Linear Discriminants at :
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).