Abstract
This paper demonstrates that similarity-based classifiers, such as k-Nearest Neighbors, can be significantly improved by incorporating "virtual attributes" derived from imperfect, expert-provided domain theories. Even when this domain knowledge is "vague" or performs at mere chance level on its own, it provides a structural scaffold that helps the similarity measure better capture the underlying logic of the data.
The Knowledge Acquisition Bottleneck
In machine learning, the choice of features (attributes) is critical. If irrelevant features are present, similarity-based classification often fails. Traditionally, researchers use Constructive Induction (CI) to create new, more useful features from raw data through a bottom-up, data-driven process.
However, experts often possess "rules of thumb" that are too incomplete or "fuzzy" to build a reliable rule-based system. Usually, this imperfect knowledge is discarded. Author Timo Steffens addresses this "knowledge acquisition bottleneck" by asking: Can we use these "broken" expert rules to create "virtual attributes" that help a similarity-based classifier perform better?
Methods: Top-Down Feature Engineering
The proposed approach involves a top-down method for feature engineering:
- Domain Theory as Rules: Expert knowledge is represented as a set of inference rules (Horn clauses). These rules contain "intermediate concepts"—logical steps between raw data and the final classification.
- Virtual Attributes: These intermediate concepts are treated as new, binary attributes. For example, if an expert defines "High Risk" as
Income < 30k AND Debt > 10k, "High Risk" becomes a virtual attribute. - Extended Similarity Measure: The similarity between two cases is calculated as a weighted average of both the original attributes and these new virtual attributes.
To manage the varying quality of these attributes, the paper tests various weighting algorithms (like RELIEF, Mutual Information, and ISAC) to automatically determine which features the classifier should trust.
Key Insights: Partialness vs. Vagueness
The paper specifically distinguishes between two types of "imperfect" knowledge:
- Partialness: The theory is missing rules for certain parts of the data.
- Vagueness: The rules exist, but the boundaries (e.g., the exact threshold for "High Income") are slightly inaccurate.
In controlled tests, adding a single correct boundary (partial knowledge) improved accuracy more reliably than adding a complete but fuzzy boundary (vague knowledge). However, similarity measures proved surprisingly robust to vagueness. Because similarity looks at whether two points are on the same side of a boundary, the exact placement matters less than the existence of the boundary itself.
Key Results
The "Extended" similarity measure outperformed the "Non-extended" version in almost every scenario:
- Promoter Gene Sequences (PGS): Using Mutual Information weighting, accuracy jumped from 86.79% to 98.11%. This is particularly impressive because the domain theory used to generate the features is only 50% accurate (chance level) on its own.
- Japanese Credit Screening (JCS): Accuracy improved across 8 out of 10 weighting methods tested, with the RELIEF method reaching 79.03% compared to the baseline.
Conclusion
The most striking insight is that even a theory that performs at chance level can drastically improve a classifier. This suggests that even "wrong" expert rules provide a useful partitioning of the instance space that the similarity measure can exploit to find patterns it could not see in the raw data. We should not throw away "weak" expert knowledge; it provides the structural hints a learner needs to achieve near-perfect accuracy.
Summary updated