PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive imputation of missing values for incomplete pattern classification

Zhun-Ga Liu, Quan Pan, Jean Dezert, Arnaud Martin

arXiv:1602.02617v1cs.AI

TL;DR

Incomplete-pattern classification must account for cases where missing values are either unimportant or crucial, while uncertain imputations can lead to imprecise classification. The paper proposes CCAI, which classifies available values first and adaptively imputes ambiguous cases using K-NN and SOM within a belief-function framework. Experiments on artificial and real datasets evaluate its effectiveness against classical methods.

  • Problem

    Missing values may be crucial for class determination, and their uncertain estimation can produce imprecise or inconsistent classification results.

  • Method

    CCAI first classifies incomplete patterns using available attributes, then imputes ambiguous cases with K-NN and SOM and fuses class-wise belief assignments over classes and meta-classes.

  • Results

    Experiments on artificial and real datasets evaluate CCAI against other classical methods, reporting effective reduction of misclassification errors.

  • Takeaways & Limitations

    Meta-classes allow CCAI to capture classification imprecision while assigning belief to specific classes when the available information supports a precise decision.

  • Takeaways & Limitations

    When an object is committed to a meta-class, its missing values cannot be accurately determined without additional information for more precise classification.

Abstract

from arXiv · show

In classification of incomplete pattern, the missing values can either play a crucial role in the class determination, or have only little influence (or eventually none) on the classification results according to the context. We propose a credal classification method for incomplete pattern with adaptive imputation of missing values based on belief function theory. At first, we try to classify the object (incomplete pattern) based only on the available attribute values. As underlying principle, we assume that the missing information is not crucial for the classification if a specific class for the object can be found using only the available information. In this case, the object is committed to this particular class. However, if the object cannot be classified without ambiguity, it means that the missing values play a main role for achieving an accurate classification. In this case, the missing values will be imputed based on the K-nearest neighbor (K-NN) and self-organizing map (SOM) techniques, and the edited pattern with the imputation is then classified. The (original or edited) pattern is respectively classified according to each training class, and the classification results represented by basic belief assignments are fused with proper combination rules for making the credal classification. The object is allowed to belong with different masses of belief to the specific classes and meta-classes (which are particular disjunctions of several single classes). The credal classification captures well the uncertainty and imprecision of classification, and reduces effectively the rate of misclassifications thanks to the introduction of meta-classes. The effectiveness of the proposed method with respect to other classical methods is demonstrated based on several experiments using artificial and real data sets.

I. INTRODUCTION

Incomplete patterns arise when attributes are unavailable, while existing approaches may struggle to classify them or represent the uncertainty introduced by imputation. The paper motivates a credal classifier that adaptively imputes values and represents ambiguity through meta-classes.

  • Missing attributes can result from sensor failure, dysfunction, or partial observation of the object.
  • Existing approaches include deleting incomplete patterns, modeling data distributions, directly handling missingness, and imputing values before classification.
  • Model-based methods require assumptions about the joint distribution of variables, but suitable distributions can be difficult to obtain.
  • Imputation methods estimate missing values separately from classification, although uncertain imputations can produce different classification results.
  • Credal classification assigns belief to singleton classes and meta-classes to represent partial imprecision rather than forcing one class.
  • The proposed method adaptively classifies available information first, then uses K-NN and SOM imputation when ambiguity indicates missing values matter.

II. BACKGROUND KNOWLEDGE

The background introduces belief function theory as a framework for assigning belief to classes and their disjunctions. It also reviews combination rules, including the strengths and limitations of Dempster-Shafer fusion under conflicting evidence.

  • A. Basis of belief function theory: Belief function theory models uncertain and imprecise information through basic belief assignments over subsets of a frame of discernment.
  • A. Basis of belief function theory: Singleton hypotheses represent specific classes, while disjunctions of singleton classes form meta-classes that characterize partial classification ignorance.
  • A. Basis of belief function theory: Credal classification allows objects to receive different belief masses for specific classes and meta-classes.
  • A. Basis of belief function theory: Dempster-Shafer combination is commutative and associative, but its normalization of conflict can yield unreasonable results in high- or special low-conflict cases.
  • A. Basis of belief function theory: Alternative rules include the conjunctive, Dubois-Prade, and PCR rules, although some are less appealing because they are non-associative or complex for multiple sources.

B. Overview of Self-Organizing Map

A self-organizing map projects input vectors onto a low-dimensional grid of learned weighting vectors while preserving neighborhood structure. Here, class-specific SOM vectors replace original samples for missing-value estimation, reducing computation.

  • A SOM is an unsupervised neural network that maps input data to a typically two-dimensional grid of nodes.
  • Each node has a weighting vector, and the best matching unit is the node whose vector is most similar to the input under a chosen metric.
  • The map performs non-uniform quantization while preserving topological properties through neighborhood relationships.
  • SOM training iteratively adjusts the best matching unit and nearby neurons toward each input, with changes decreasing over time and grid distance.
  • Class-specific SOM weighting vectors represent training classes and replace original samples when estimating missing values, reducing computation burden.

III. CREDAL CLASSIFICATION OF INCOMPLETE PATTERN

CCAI adaptively classifies incomplete patterns by first using available attributes and imputing missing values only when the initial classification remains ambiguous. It represents class-specific evidence with belief assignments and fuses the results for credal classification.

  • Method: CCAI first classifies an incomplete pattern using only its available attribute values.Missing values are ignored in this initial step.
  • Adaptive strategy: If the available information does not clearly identify a class, CCAI treats the missing values as potentially crucial and imputes them before classification.This constitutes the method’s second step.
  • Evidence fusion: The original or imputed pattern is classified with respect to each training class, and the resulting basic belief assignments are globally fused.The class-wise results are treated as multiple sources of evidence.
  • Evidence construction: Each class-specific result assigns belief to a singleton class and the ignorant class, with singleton belief based on normalized distance to that class prototype.The distance calculation ignores missing dimensions and normalizes by the number of available attributes.
  • Adaptive strategy: When the distinguishability condition χi ≤ ϵ holds, CCAI directly combines the class-specific belief assignments without imputing missing values.The condition indicates that available attributes are sufficient for classification.
  • Adaptive strategy: When χi ≤ ϵ fails, CCAI imputes missing values because the leading classes cannot be clearly distinguished from the available attributes.The imputed pattern then enters the classification procedure.

1) Multiple estimation of missing values:

For ambiguous incomplete patterns, CCAI generates multiple class-specific imputations using K nearest SOM weighting vectors rather than relying on a single global imputation. These vectors represent each class while reducing the computational burden of direct K-NN search.

  • Computational consideration: The SOM approach reduces the computational complexity associated with K-NN imputation, whose main drawback is calculating distances to all training samples.SOM training can be performed offline.
  • SOM-based representation: CCAI uses SOM separately within each training class to obtain weighting vectors that characterize the class’s topological features.The number of weighting vectors is usually small compared with the full training set.
  • Multiple estimation of missing values: For each class, the K nearest SOM weighting vectors provide weighted contributions to estimating the missing attributes.Their distances to the incomplete input are computed while ignoring missing values.
  • Multiple estimation of missing values: CCAI fills the missing dimensions with class-specific weighted estimates and classifies each resulting edited pattern using that training class.This produces one estimated pattern and classification result per class.

2) Ensemble classifier for credal classification:

CCAI fuses class-specific classification results as an ensemble of belief assignments, discounting unreliable results and preserving conflict in meta-classes. Its threshold controls the trade-off between imprecision and misclassification risk.

  • Ensemble classifier: CCAI combines the classification results obtained from each training class as multiple evidence sources with different reliabilities.The class with the largest weighting factor is treated as the most reliable.
  • Ensemble classifier: Relative weighting factors discount class-specific belief assignments before global fusion, while a fully ignorant assignment contributes neutrally.This limits the influence of unreliable class-specific results.
  • Conflict management: When imputations from different classes produce conflicting classifications, CCAI uses a DP-inspired rule that transfers partial conflict to the corresponding meta-class.The meta-class records imprecision caused by missing values.
  • Credal decision: Hard credal classification assigns an object to the singleton class or meta-class with the maximum mass of belief.A meta-class indicates membership in one of several specific classes without identifying which one.
  • Parameter tuning: The threshold ϵ governs whether CCAI uses imputation and affects discounting, with larger values yielding fewer meta-class assignments but increasing misclassification risk.The paper recommends tuning ϵ according to the acceptable compromise between error and imprecision.

IV. EXPERIMENTS

The experiments evaluate CCAI on artificial and real data and compare it with K-NN imputation, FCM imputation, SOM imputation, and prior credal classification approaches. The reported results emphasize lower error and retained imprecision information through meta-classes.

  • Experimental design: Three experiments using artificial and real data sets evaluate the performance of CCAI.The methods were implemented and tested with MatlabTM software.
  • Comparative methods: CCAI is compared with K-NN imputation, FCM imputation, SOM imputation, and the previous PCC method.ENN is used in the sequel experiments, with EK-NN additionally used in Experiment 3 for comparison.
  • Results: CCAI retains conflicting classification information in meta-classes during fusion, unlike SOMI.This represents imprecision in the classification result.
  • Evaluation measures: The experiments distinguish misclassification from imprecise classification, counting a prediction outside the true class as an error and overlapping meta-class assignments as imprecision.The error rate is Re = Ne/T, where Ne is the number of misclassification errors and T is the number of tested objects.

A. Experiment 1 (artificial data set)

The first experiment evaluates CCAI on a three-class artificial data set with missing y-coordinates, showing when adaptive imputation is needed and how meta-classes represent ambiguity.

  • Setup: 600 training and 600 test samples are generated from three 2-D uniform classes, with every test sample missing its y-coordinate.Each class contributes 200 training and 200 test samples.
  • Missing-value ambiguity: Because the available x-coordinate can overlap class margins, different imputations of the missing value can produce different class assignments.For example, imputations from ω1 and ω3 can assign the same edited pattern to different classes.
  • Credal classification: CCAI assigns ambiguous objects to meta-classes such as ω1 ∪ω3 or ω2 ∪ω3 when available information cannot distinguish the specific classes.This preserves the supported alternatives instead of forcing every object into one specific class.
  • Adaptive imputation: Objects whose x-coordinate alone supports a class are classified directly without estimating the missing value.This applies to objects in the left margin of ω1, right margin of ω2, and middle of ω3.
  • Comparison: CCAI balances error rate, imprecision rate, and computation burden, whereas single-step variants either increase errors or imprecision.The first step alone produces a bigger error rate, while imputing every incomplete pattern produces high imprecision and longer computation time.
  • Comparison: CCAI generally has a smaller error rate than KNNI, FCMI, and SOMI, while SOM-based weighting vectors reduce computation relative to KNNI.The reported CCAI result is Re = 5.83, Ri2 = 16.83, and time = 0.0469s.

B. Experiment 2 (artificial data set)

The second experiment tests CCAI on a 4D artificial data set with one to three randomly missing components and compares it with imputation-based alternatives.

  • Setup: The 4D artificial data set contains three Gaussian classes, with g = 500 or g = 1000 training and test samples per class.Each test sample has n missing values, with n ∈ {1, 2, 3}, and the missing dimension is randomly selected.
  • Results: CCAI produces the lowest error rate among the compared methods because difficult objects can be committed to appropriate meta-classes.The comparison includes FCMI, KNNI, SOMI, and PCC.
  • Results: CCAI also takes the shortest computation time because some incomplete patterns are classified directly without imputing unimportant missing values.Other methods impute missing values in every pattern, increasing computation.
  • Computational analysis: KNNI takes the longest time, while CCAI reduces distance calculations by comparing objects with SOM-derived weighting vectors instead of all training samples.This explains the computational advantage of the SOM-assisted strategy.

C. Experiment 3 (real data set)

The third experiment evaluates CCAI on real data sets with missing values and reports lower error rates than traditional imputation methods, while retaining a compromise between error and imprecision.

  • Setup: Nine UCI real data sets are used, with missing values introduced completely at random for test samples in the data sets without original missingness.Seven data sets use repeated 2-fold cross-validation; Hepatitis already contains missing patterns treated as test samples.
  • Results: PCC and CCAI consistently produce lower error rates than FCMI, KNNI, and SOMI by assigning ambiguous objects to meta-classes.Meta-classes expose classification imprecision rather than forcing uncertain objects into specific classes.
  • Interpretation: CCAI can still assign some imputed objects to meta-classes, indicating that their missing values remain crucial and are not estimated reliably enough.The paper states that different estimates can have similar reliabilities yet lead to distinct classification results.
  • Comparison: Compared with PCC, CCAI generally achieves lower error and imprecision rates through the SOM+KNN missing-value estimator.The authors attribute the improvement mainly to more accurate missing-value estimation.
  • Adaptive strategy: Using only the first SCCAI step increases misclassification, whereas using only the second raises imprecision; adaptive CCAI provides a compromise between both.The two-step design combines direct classification with selective imputation.

V. CONCLUSION

CCAI presents a belief-function-based credal classifier with adaptive imputation for incomplete patterns. It first classifies using available values, imputes with SOM and K-NN only when needed, and represents uncertainty through singleton classes and meta-classes.

  • CCAI adaptively handles incomplete patterns with a credal classification method based on belief function theory.
  • Objects that receive a specific classification from available values bypass imputation, reducing computation complexity.Imputation is performed only when available information is insufficient for an unambiguous classification.
  • When the available information is insufficient, SOM and K-NN estimate missing attributes before classification.The two techniques seek a compromise between estimation accuracy and computational burden.
  • The credal output assigns different belief masses to singleton classes and meta-classes.A meta-class is a disjunction of several classes and represents partial classification ignorance.
  • Meta-classes capture classification imprecision and effectively reduce misclassification errors.The method allows ambiguity when missing values cannot be accurately recovered, rather than forcing a single class.
  • CCAI’s effectiveness and interest were evaluated in three experiments using artificial and real data sets.
Loading 1602.02617v1…