📊 statistics

A Jensen-Shannon divergence based $k$ -- $NN$ algorithm for missing value imputation in compositional data

This paper proposes a novel nonparametric $k$ -NN algorithm for imputing missing values in compositional data that leverages Jensen-Shannon divergence and the Fréchet mean to handle zero values and self-adapt hyper-parameters, demonstrating superior accuracy and computational efficiency compared to existing methods.

Original authors: Michail Tsagris, Connie Stewart, Abdulaziz Alenazi

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Michail Tsagris, Connie Stewart, Abdulaziz Alenazi

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to recreate a secret family recipe. You have a stack of recipe cards, but some of them are torn or have missing ingredients listed. Your goal is to guess what those missing ingredients are so you can finish the dishes.

In the world of data science, this is called imputation (filling in the blanks). But this paper deals with a very specific, tricky type of recipe: Compositional Data.

What is "Compositional Data"?

Think of a pie chart. The whole pie always equals 100%. If you have a slice of "Apples" and a slice of "Oranges," and you add more Apples, the Orange slice must get smaller to keep the total at 100%.

This is different from a normal grocery list where you can have 5 apples and 10 oranges without one affecting the other. In compositional data, the parts are locked in a dance; if one moves, the others must adjust. This makes filling in missing numbers very hard because you can't just guess a number; you have to guess a number that fits the whole pie perfectly.

The Problem with Old Methods

For years, scientists tried to fix missing pieces in these "pie charts" using a method called k-NN (k-Nearest Neighbors).

How it works: If you have a recipe missing "Salt," the computer looks at other recipes that are very similar to yours. It sees what those similar recipes used for salt and guesses that you probably used something similar.
The Flaw: The old way of measuring "similarity" (called Aitchison's distance) is like trying to measure the distance between two cities using a ruler on a flat map, even though the Earth is round. It works okay sometimes, but it breaks down if your recipe has zero ingredients (e.g., "No Olives"). In the old math, you can't calculate the distance if a number is zero, so the whole system crashes.

The New Solution: The "Jensen-Shannon" Compass

The authors of this paper built a new, smarter compass to measure similarity. They call it the Jensen-Shannon Divergence (JSD).

The Analogy: Imagine you are comparing two smoothies. The old method might get confused if one smoothie has zero strawberries. The new JSD method is like a smart blender that says, "Okay, you have zero strawberries, but you have lots of bananas. Let's compare the flavor profile of the whole mix, ignoring the fact that one ingredient is missing."
The Benefit: This new method works perfectly even when the data contains zeros. It doesn't break; it just adapts.

The "Magic Dial" (The Fréchet Mean)

The authors didn't stop there. They added a "Magic Dial" (a parameter called $\alpha$ ) to their algorithm.

The Analogy: Imagine you are averaging the opinions of your neighbors to guess the missing ingredient.
- If you just take the Arithmetic Mean (the standard average), you are like a strict teacher: "Everyone gets equal weight."
- If you use the Geometric Mean, you are like a cautious editor: "We'll ignore the extreme outliers."
- The Fréchet Mean is like a flexible mediator. The "Magic Dial" ( $\alpha$ ) lets you slide between being strict, being cautious, or being somewhere in between. The computer can automatically tune this dial to find the perfect balance for your specific data.

The "Self-Adapting" Feature

Sometimes, missing data isn't random. Maybe the "Salt" is missing only in spicy recipes, while "Sugar" is missing only in sweet ones.

The authors created an Adaptive version of their tool. Instead of using one rule for the whole cookbook, this version looks at how the data is missing and changes its strategy for each specific pattern. It's like having a different chef for every type of dish.

What Did They Find?

The team tested their new tool against the old methods using real-world data, such as:

Wine chemistry: Analyzing acids in Czech wines.
River water: Checking chemical levels in Spanish rivers.
Fish diets: Looking at fatty acids in fish (where some fish simply don't eat certain things, creating "zero" values).
Farm crops: Figuring out how much of specific crops were grown in Greek regions.

The Results:

Accuracy: Their new method was consistently more accurate than the old ones. It guessed the missing numbers closer to the truth.
Speed: It was much faster. In some tests, the old method took 12 to 25 times longer to do the same job.
Zeros: It handled "zero" values without any trouble, whereas the old methods struggled or failed.

The Bottom Line

The authors built a new, faster, and more flexible way to fill in the missing pieces of "pie chart" data. It works even when some slices are completely empty (zeros), and it uses a smart "Magic Dial" to adjust its own settings for the best results. While the "self-adapting" feature is cool, they found that sometimes the simpler version is just as good and less complicated.

Note: The paper focuses strictly on the math and the simulation results. It does not claim this is a medical cure or a specific tool for future clinical use, but rather a statistical improvement for handling data in fields like economics, ecology, and chemistry.

Technical Summary: A Jensen-Shannon Divergence based k–NN Algorithm for Missing Value Imputation in Compositional Data

1. Problem Statement

Compositional data, defined as non-negative multivariate vectors summing to a constant (typically 1), reside in a standard simplex sample space ( $S^{D-1}$ ). Missing values in such data pose unique challenges because standard imputation techniques often fail to respect the restrictive geometry of the simplex or require log-ratio transformations that cannot handle zero values.

Existing methods, such as the k–NN algorithm proposed by Hron et al. (2010), rely on Aitchison's distance. However, Aitchison's distance requires log-ratio transformations, rendering it inapplicable to datasets containing zeros (whether rounded or structural). Furthermore, traditional approaches often assume a specific parametric structure or require iterative regression models that may be computationally intensive. This paper addresses the need for a flexible, nonparametric imputation method that:

Operates directly on the simplex without log-ratio transformations.
Naturally accommodates zero values.
Offers computational efficiency and flexibility in handling missing value patterns.

2. Methodology

The proposed solution is a novel JSD k–NN algorithm, extended with a Fréchet mean generalization and an adaptive mechanism.

2.1 Distance Metric: Jensen-Shannon Divergence (JSD)

Instead of Aitchison's distance, the algorithm utilizes the Jensen-Shannon divergence (JSD) to measure distances between compositional vectors.

Definition: For two compositions $x$ and $y$ , $JSD(x, y) = \sum_{j=1}^D \left( x_j \log \frac{2x_j}{x_j+y_j} + y_j \log \frac{2y_j}{x_j+y_j} \right)$ .
Advantages: Unlike Aitchison's distance, JSD treats zero values naturally (since $0 \log 0 = 0$ ), eliminating the need for zero-replacement strategies. It is a metric (the square root satisfies the triangular inequality) and is bounded.

2.2 The JSD k–NN Algorithm

The core algorithm follows a six-step nonparametric procedure:

Selection: Choose the number of nearest neighbors, $k$ .
Separation: Split the data into incomplete vectors ( $X_M$ ) and complete vectors ( $X_O$ ).
Normalization: For an incomplete vector, normalize the observed components to sum to 1. Similarly, normalize the corresponding components in the complete vectors.
Distance Calculation: Compute the JSD between the normalized observed components of the incomplete vector and all complete vectors.
Neighbor Selection: Identify the $k$ complete vectors with the smallest JSD distances.
Imputation: Calculate the mean of the $k$ nearest neighbors. The missing components are estimated by taking the arithmetic mean of the corresponding components in the $k$ neighbors, normalizing them, and scaling them by the sum of the observed components in the original incomplete vector.

2.3 Extension 1: JSD $\alpha$ –k–NN (Fréchet Mean)

To increase flexibility, the arithmetic mean used in Step 5 is replaced by the sample Fréchet mean defined by Tsagris et al. (2011):
$\hat{\mu}_\alpha(x) = C \left\{ \left( \sum_{i=1}^n \frac{x_{ij}^\alpha}{\sum_{k=1}^D x_{kj}^\alpha} \right)^{1/\alpha} \right\}_{j=1,\dots,D}$
where $\alpha$ is a tunable hyper-parameter.

Properties: As $\alpha \to 0$ , it converges to the geometric mean; at $\alpha = 1$ , it is the arithmetic mean. This allows the algorithm to adapt to the data's distribution without log-ratio transformations.

2.4 Extension 2: Adaptive JSD $\alpha$ –k–NN

Recognizing that missing value patterns may vary (e.g., missingness related to specific component magnitudes), the authors propose an adaptive approach where the hyper-parameters ( $\alpha$ and $k$ ) are tuned separately for each distinct missingness pattern observed in the data, rather than using a single global pair.

2.5 Hyper-parameter Tuning

The optimal values for $k$ and $\alpha$ are determined via a repeated leave-N-out cross-validation protocol. The performance metric is the distance (Aitchison's distance if no zeros are present; JSD if zeros are present) between the true values and the imputed values in the test set.

3. Key Contributions

Zero-Tolerance Imputation: The method is the first k–NN approach for compositional data that does not require log-ratio transformations, thereby handling both rounded and structural zeros natively.
Nonparametric Flexibility: By utilizing JSD and the Fréchet mean, the method avoids restrictive parametric assumptions about the data structure.
Computational Efficiency: The algorithm is significantly faster than competing iterative regression-based methods (specifically those in the robCompositions package).
Adaptive Framework: The introduction of an adaptive mechanism allows hyper-parameters to adjust to specific missingness patterns, though the paper notes this adds computational complexity.

4. Results from Simulation Studies

The authors evaluated the algorithms using four real-world datasets: Wines (no zeros), Hydrochemical (no zeros), Prey Fatty Acids (contains zeros and species classes), and FADN (agricultural data with zeros and aggregation/disaggregation scenarios).

Accuracy (No Zeros): On the Wines and Hydrochemical datasets, the JSD $\alpha$ –k–NN (with optimal $\alpha$ ) outperformed the standard JSD k–NN by 12% and 2% respectively, measured by Aitchison's distance. Both proposed methods outperformed the competing Hron et al. (2010) algorithms (rob k–NN, lm, ltsReg).
Accuracy (With Zeros): On the Prey Fatty Acids dataset, the JSD k–NN improved performance by 22% over the robust k–NN (Hron et al., 2010) using Euclidean distance. The JSD $\alpha$ –k–NN provided an additional 3.5% improvement. The adaptive version did not yield further gains in this specific case.
Disaggregation Scenario: In the FADN dataset (simulating the disaggregation of aggregated crop data), the JSD k–NN outperformed the robust k–NN by 15%. The $\alpha$ and adaptive extensions did not show further improvement here.
Computational Cost: The JSD k–NN was significantly faster than the robust k–NN. Speed-up factors ranged from approximately 6x to 25x, depending on sample size and dimensionality. The speed-up was more pronounced at higher dimensions and lower sample sizes.

5. Significance and Claims

The paper claims that the proposed JSD k–NN algorithm offers a robust, accurate, and computationally efficient alternative for imputing missing values in compositional data. Its primary significance lies in its ability to handle zero values without modification, a critical limitation of existing log-ratio based methods.

The authors modestly conclude that while the adaptive JSD $\alpha$ –k–NN extension offers a theoretical improvement by tailoring parameters to missingness patterns, it does not always substantially improve performance in practice. They suggest that the added complexity may not be worthwhile in all cases, particularly when missing patterns are sparse. However, the core JSD k–NN and the Fréchet mean extension (JSD $\alpha$ –k–NN) consistently demonstrate superior accuracy and efficiency compared to current state-of-the-art methods.

The work is positioned as a practical tool for fields such as ecology, agriculture, and official statistics where compositional data with zeros and missing values are prevalent. The authors acknowledge that while the method assumes Missing At Random (MAR), it has not been assessed under Missing Not At Random (MNAR) scenarios, which are common in official statistics.