This paper proposes IPS-KNN, an interpretable variant of the distance-weighted K-nearest neighbors (KNN) algorithm based on interval pattern structures, to address the limitation of KNN's lack of interpretability. The proposed algorithm provides a reason for the classification in the form of a pattern of the interval pattern structure describing the dataset. The intervals in the reason for classification provide insights into which features are important for the classification task and what values these features should have to produce a specific classification result. The IPS-KNN algorithm was evaluated on the red wine quality dataset, where it performed similarly to the distance-weighted KNN algorithm in terms of classification performance. The proposed algorithm can be used in applications where interpretability is important, such as in medical diagnosis or credit risk assessment.
those for which humans can understand the causes of the model’s predictions.
While interpretability may not be crucial in low-risk applications such as recommendation
systems, it is of utmost importance in high-risk applications such as credit risk assessment and
medical diagnosis. In such cases, it is essential to pair each prediction with the reason that led
the model to make that prediction in order to avoid any possible errors. Despite the absence of
a standardized metric for evaluating interpretability, models can be compared based on how
easily humans can comprehend the reasons behind their decisions [
Pattern structures, an extension of Formal Concept Analysis (FCA) introduced by Kuznetsov
and Ganter [
Interval pattern structures, proposed in [
Although the original algorithm was proven efective on pattern structures with graph
descriptors [
Instead of attempting to solve the issues with the original hypotheses-based algorithm, this paper argues that augmenting the distance-weighted KNN with interval pattern structures can provide interpretability. As the nearest instances to the query instance carry the most useful information for classification, this approach focuses on leveraging this information, rather than relying on random batches from the train set.
Pattern structures are a generalization of Formal Concept Analysis (FCA). In FCA, a context
is defined as a set of instances with binary features, where a binary relation specifies which
features are possessed by each instance [
Then (, , ) is called a pattern structure, where = (, ⊓), with the condition that the set () := { ()| ∈ } generates a complete sub-semi-lattice ( , ⊓) from (, ⊓), i.e. each subset of () has a meet ⊓ in (, ⊓).
The elements of are called patterns and are naturally ordered by the absorption relation ⊑: for , ∈ , ⊑ ⇐⇒ ⊓ = . The operation ⊓ is also called the similarity operation.
The pattern structure (, , ) follows FCA and defines two derivative operators (.)◇ given in equations 1 and 2. The first of which is applied to a set of instances and returns the largest common pattern describing these instances, while the second is applied to a pattern and returns a set of instances that possess this pattern.
◇ = ⊓∈ () for ⊆ ◇ = { ∈ | ⊑ ()} for ∈ (, ⊓)
Interval pattern structures [
Thus, the patterns of the set are − dimensional vectors of intervals, where is the number of features. For the patterns = ⟨[, ]⟩=1,2,.., and = ⟨[, ]⟩=1,2,.., in , the similarity of and is given by:
⊓ = ⟨[, ]⟩=1,2,.., ⊓ ⟨[, ]⟩=1,2,.., = ⟨[(, ), (, )]⟩=1,2,.., The absorption relation ⊑ is given by: ⊑ ⇐⇒ ⟨[, ]⟩=1,2,.., ⊑ ⟨[, ]⟩=1,2,..,
⇐⇒ [, ] ⊓ [, ] = [, ] ∀ ∈ {1, 2, .., }
Consequently, larger intervals are absorbed by the smaller intervals they contain. At first glance, this may seem counter-intuitive, but by definition, the similarity of a set of instances should be absorbed by the pattern of each instance in this set.
The original distance-weighted K-nearest neighbors (KNN) algorithm [
To classify a new instance , the set ⊆ consisting of the -nearest neighbors of in the training set is identified. The similarity of all instances in is then calculated by applying the similarity operator ⊓. All instances in the training set that are described by this similarity are included in a voting process. The class of is then determined by the function: where the positive and negative scores, + and − respectively, are calculated as: ( ) = sgn(+ − − ) + = − = +∈◇∩+ ∑︁ ∑︁ − ∈◇∩−
1 (+, )
1 (− , ) (5) (6) (7)
Here, (, ) is the Euclidean distance between instances and in the feature space. The set ◇ is the subset of that contains all instances described by the similarity ◇.
The proposed IPS-KNN algorithm difers from the original distance-weighted -Nearest Neighbors in that, in IPS-KNN, the similarity of the -Nearest Neighbors defines which instances will vote, while in KNN, only the -nearest neighbors vote. The set of voters in IPS-KNN contains all the -nearest neighbors because they are all described by their similarity, but it may include additional instances as well.
The diference in the set of voters between IPS-KNN and KNN is due to the geometric shape that encloses the neighbors in the feature space. In KNN, the distance between the query instance and the farthest instance of the -Nearest Neighbors defines a hyper-sphere in the feature space, and all the instances located on its surface or inside it vote. On the other hand, the similarity of the -Nearest Neighbors of the query instance defines a hyper-rectangle in the feature space in IPS-KNN. This hyper-rectangle is larger than the hyper-sphere of KNN and contains it entirely within its boundaries. Therefore, the set of voters in IPS-KNN may include more instances than just the -Nearest Neighbors.
The similarity operation ⊓ can reveal why a query instance was classified in a certain class, as it captures the similarity of descriptions. Suppose that a query instance was classified as positive by IPS-KNN. In this case, ( ) is the set of k-nearest instances to in the training set, and their common similarity determines the set of voters ( ) = ◇( ), which can be split into positive voters + and negative voters − . The negative score is then given by − = ∑︀− ∈− (− 1, ) . Since was classified as positive, the positive score + is greater than − . It is possible that only a subset of + needs to vote to classify as positive; any subset of + that produces a positive score greater than the negative score will lead to the same classification result.
Formally, let = { | ⊆ +, ∑︀+∈+ (+1, ) > − } be the set of all subsets of +( ) that give a positive score greater than − . The subset with the minimum number of instances includes the instances of + closest to the query instance . However, this subset is not necessarily unique, since multiple instances might have the same distance from the query instance. Let be the subset that correspond to the hyper-rectangle with minimum volume. The similarity of the elements of together with the description of the query instance is the reason for classifying as positive. This is given by = ◇ ⊓ ( ) : ∈ and || = min || : ∈ and Π=1| − | is minimum, where and are the limits of the ℎ interval of ◇ ⊓ ( ) and is the number of features. The reason for classification is itself a pattern in the interval pattern structure (, , ), consisting of a vector of intervals with one interval for each feature. The values of these intervals, relative to the original range of values of the features, provide interpretability. can also be considered a classifier that correctly classifies all instances of and the new instance . It should be noted that substituting the subset with any other element in would provide another correct interpretable classifier. However, using corresponds to enclosing the classified instances in the most specific hyper-rectangle. On the other hand, using + instead of will result in the most general hyper-rectangle.
The interpretability provided by IPS-KNN is somewhat analogous to that provided by decision
trees for continuous features. In IPS-KNN, the reason for classification is represented by a
hyper-rectangle in the feature space, with one interval for each feature. Similarly, in decision
trees, decisions are based on comparisons of feature values using greater than and less than
conditions [
The proposed algorithm IPS-KNN was evaluated against the baseline classification algorithms
on the red wine quality dataset 1, which contains 11 numeric features and its output feature
was binarized for this purpose. In its original form, the quality of each wine is assessed by a
score between 1 and 10, where a higher score indicates better quality. To binarize the output
feature, wines with a quality score in the range [
The following is an example of how IPS-KNN classifies a new instance and provides interpretability on the binary red wine quality dataset. Table 2 shows the features of the red wine quality dataset, the values of these features for the query instance , the ranges of the features, and the intervals of the reason of classification R. We obtained the value of the hyperparameter K of 25 through grid search. The similarity of 25-nearest instances to chose 44 instances to vote, 38 of which are positive and the remaining 6 are negative. The resulting positive and negative scores were + = 19.3 and − = 2.6; therefore, was classified as positive.
Out of the 38 positive instances, the nearest 4 were enough to give a positive score larger than the negative one. The similarity of these 4 objects together with produced the reason of classification denoted by R in Table 2. The intervals of provide the interpretability of why was classified as positive and what values should the features of instances similar to also have in order to be classified as positive.
For example, the interval [6.3, 6.8] of corresponding to the feature (fixed acidity) shows that this feature’s value should be low relative to the original range of values in order to the classification result to be positive. The interval corresponding to the feature (alcohol) shows that the value of this feature should be in in the middle of the range of possible values. The intervals corresponding to the features (fixed acidity, residual sugar, sulphates) are short relative to the ranges of their values, which mean that they are important to the classification process.
In contrast, intervals covering a large part of the entire range of values are less useful since they describe almost all objects in the dataset.
Based on the results of the experiments, we can conclude that the IPS-KNN algorithm performs similarly to the distance-weighted KNN algorithm in terms of classification performance. However, the IPS-KNN algorithm provides additional interpretability through the reason for the classification in the form of a pattern of an interval pattern structure. The intervals in the reason for classification provide insights into which features are important for the classification task and what values these features should have in order to produce a specific classification result.
The proposed algorithm can be used in applications where interpretability is important, such as in medical diagnosis or credit risk assessment. The interpretability provided by IPS-KNN can help experts understand why a certain decision was made, which can lead to better decision making and increased trust in the system.
One limitation of the IPS-KNN algorithm is that the hyper-rectangle surrounding the query instance and its neighbors is currently aligned with the coordinate axes in the feature space. To address this limitation, we plan to investigate the introduction of a tilted hyper-rectangle in future work. By tilting the hyper-rectangle at an angle, we aim to provide better separation of the voters and potentially improve classification accuracy.
Introducing a tilted hyper-rectangle is a promising avenue for future research that could enhance the performance of the IPS-KNN algorithm. However, it is important to conduct more detailed investigation to explore the feasibility and potential benefits of this approach. Specifically, we need to determine the optimal angle of tilt and evaluate the impact of this approach on classification accuracy compared to the current IPS-KNN algorithm.