Class Imbalance in Neighbor Voting

Why Class Imbalance Changes a Neighbor Vote

A K-nearest-neighbor classifier assigns a class to a new observation by examining the labels of nearby training observations. When one class is much more common in the training data, an ordinary majority vote can favor it even in a neighborhood where the less common class has substantial support. The issue is not that majority voting is incorrect: it reflects the class composition of the neighbors. The issue is whether that composition represents the population in which the classifier will be used and the decision that must be made.

For example, a hypothetical fraud-screening data set might contain many ordinary transactions and few fraudulent ones. A query transaction can have several fraudulent neighbors and still receive an ordinary-transaction prediction if the selected neighborhood is large enough. Conversely, a training sample deliberately constructed to contain equal numbers of each class may not reflect the fraud prevalence among transactions in use. The appropriate vote depends on the training design, the target population, and the costs or priorities of the classification decision.

Definition: Class imbalance means that the classes have substantially different frequencies in a data set. For a query \(x\), let \(n_c(x)\) be the number of its \(k\) nearest training observations in class \(c\), so that \(\sum_c n_c(x)=k\). The ordinary vote assigns \(x\) to a class with the largest \(n_c(x)\). Its local class fraction is \(n_c(x)/k\). These fractions describe the selected neighbors; they are not automatically the class probabilities in a different target population.

Ordinary Votes and Class-Weighted Votes

An unweighted vote gives every one of the \(k\) neighbors a contribution of one. If class A occurs 8 times and class B occurs 4 times among 12 neighbors, the vote scores are 8 and 4, and class A is selected. This is the standard majority-vote rule. A tie requires a specified tie-breaking rule; it must not be silently resolved by assuming that the less common class wins.

A class-weighted vote multiplies each class’s neighbor count by a chosen positive weight. The score for class \(c\) is \(w_c n_c(x)\), and the class with the largest score is selected. Weights can reflect target-population prevalence or a decision objective, but those are different reasons for weighting. In particular, inverse training prevalence is not automatically the right choice: the correct adjustment depends on how the training sample was obtained and what prediction is needed.

A useful special case is prior adjustment. Suppose training observations were sampled at different rates by class, but within each class the distribution of predictors is unchanged by sampling. Let \(\pi_{s,c}\) be class \(c\)'s training-sample prevalence and \(\pi_{t,c}\) its target-population prevalence. If \(q_{s,c}(x)\) is the class probability estimated from the training sample at \(x\), the prior-adjusted score is proportional to \(q_{s,c}(x)\pi_{t,c}/\pi_{s,c}\). Normalize these scores across classes if probabilities are required.

q_{t,c}(x) = \frac{q_{s,c}(x)\,\pi_{t,c}/\pi_{s,c}} {\sum_j q_{s,j}(x)\,\pi_{t,j}/\pi_{s,j}}

For ordinary KNN, \(q_{s,c}(x)\) is commonly estimated by \(n_c(x)/k\). Since the common factor \(1/k\) cancels when the adjusted scores are normalized or compared, one may calculate scores as \(n_c(x)\pi_{t,c}/\pi_{s,c}\). The target prevalence and training prevalence must both refer to the same classes and be defined on the same basis.

Why Prior Adjustment Has This Form

The adjustment follows from Bayes’ rule. Write \(f_c(x)\) for the predictor density in class \(c\), assumed to be the same in the training sample and target population. The class posterior in either population is proportional to its class density times its class prevalence. Thus the training posterior is proportional to \(f_c(x)\pi_{s,c}\), while the target posterior is proportional to \(f_c(x)\pi_{t,c}\). Taking their ratio cancels \(f_c(x)\), leaving the prevalence factor \(\pi_{t,c}/\pi_{s,c}\).

q_{s,c}(x)\ \propto\ f_c(x)\pi_{s,c} \quad\Longrightarrow\quad f_c(x)\ \propto\ \frac{q_{s,c}(x)}{\pi_{s,c}} \quad\Longrightarrow\quad q_{t,c}(x)\ \propto\ q_{s,c}(x)\frac{\pi_{t,c}}{\pi_{s,c}}

This argument requires that sampling changes class prevalences but does not change the predictor distribution within a class. It also requires positive training prevalence for any class to be adjusted: if \(\pi_{s,c}=0\), the training data contain no information for estimating that class’s local pattern. In practice, KNN fractions are based on a finite neighborhood, so adjusted scores can be unstable when a class has very few nearby observations. Prior adjustment corrects a prevalence mismatch; it does not create missing local evidence.

Worked Example: A Rare Class in a Representative Training Sample

A hypothetical claim-screening classifier is trained on a sample representative of its target population. Class A (routine) has training prevalence \(\pi_{s,A}=0.80\), and class B (review-worthy) has prevalence \(\pi_{s,B}=0.20\). The same prevalences apply in the target population. Among the \(k=9\) nearest observations to a new claim, 7 are A and 2 are B. Compare the ordinary vote with prior adjustment. State the method and the mistake to avoid.

Method. First calculate the ordinary counts, then use the target-to-training prevalence ratios for adjustment. Because the sample and target prevalences match, prior adjustment should not change the result.

Ordinary vote. The scores are \(n_A=7\) and \(n_B=2\). Since \(7>2\), the ordinary prediction is A. The local fractions are \(7/9=0.7778\) for A and \(2/9=0.2222\) for B, to four decimals.

Prior-adjusted scores. The prevalence ratios are \(0.80/0.80=1\) for A and \(0.20/0.20=1\) for B. Therefore the scores are \(7(1)=7\) for A and \(2(1)=2\) for B. The adjusted fractions remain \(7/9=0.7778\) and \(2/9=0.2222\), so the prediction remains A.

Check. The two methods agree, as they should when the training and target prevalences are identical. Common mistake: multiplying class B’s count by the inverse training prevalence, \(1/0.20=5\), without also specifying the target prevalence. That would give B a score of 10 and reverse the result, even though no prevalence mismatch has been established.

Worked Example: Correcting an Enriched Training Sample

A hypothetical equipment-monitoring study deliberately samples equal numbers of normal and fault cases, so the training prevalences are \(\pi_{s,N}=0.50\) and \(\pi_{s,F}=0.50\). In actual operation, the target prevalences are \(\pi_{t,N}=0.90\) and \(\pi_{t,F}=0.10\). For a new sensor record, \(k=8\) neighbors include 5 normal and 3 fault observations. Assume sampling within each class preserves the predictor distribution. Find the ordinary and prior-adjusted predictions and adjusted probabilities.

Ordinary vote. The counts are \(n_N=5\) and \(n_F=3\), so the ordinary prediction is normal. The sample local fractions are \(5/8=0.6250\) and \(3/8=0.3750\).

Prior adjustment. The normal prevalence ratio is \(0.90/0.50=1.8\), and the fault prevalence ratio is \(0.10/0.50=0.2\). Using counts as proportional scores gives \(5(1.8)=9\) for normal and \(3(0.2)=0.6\) for fault. The score total is \(9+0.6=9.6\).

The adjusted normal probability is \(9/9.6=0.9375\), and the adjusted fault probability is \(0.6/9.6=0.0625\). The adjusted prediction is normal. The adjustment changes the estimated probabilities substantially because the balanced training design over-represents fault cases relative to the target population; in this particular neighborhood, it does not change the selected class.

Check. The adjusted probabilities sum to \(0.9375+0.0625=1.0000\). Common mistake: treating the training prevalence of 0.50 for faults as the actual operational prevalence. Doing so skips the stated target-population correction and reports the unadjusted local fraction instead.

Worked Example: Three Classes and a Changed Winner

A hypothetical maintenance classifier uses classes A (routine), B (monitor), and C (urgent). The training prevalences are \(0.70\), \(0.20\), and \(0.10\), respectively. The target prevalences are \(0.50\), \(0.30\), and \(0.20\). Assume that sampling preserves the predictor distribution within each class. Of the \(k=5\) neighbors to a new observation, 2 are A, 2 are B, and 1 is C. Find the ordinary winner and the prior-adjusted winner, including adjusted probabilities.

Ordinary vote. A and B each have 2 votes; C has 1. The ordinary vote is tied between A and B. Without a specified tie rule, the ordinary prediction cannot be uniquely determined.

Prior-adjusted scores. The prevalence ratios are \(0.50/0.70=5/7\) for A, \(0.30/0.20=1.5\) for B, and \(0.20/0.10=2\) for C. The proportional scores are \(2(5/7)=10/7\), \(2(1.5)=3\), and \(1(2)=2\). Their total is \(10/7+3+2=45/7\).

The normalized probability for A is \((10/7)/(45/7)=10/45=0.2222\). For B it is \(3/(45/7)=21/45=0.4667\). For C it is \(2/(45/7)=14/45=0.3111\). These probabilities sum to \((10+21+14)/45=1.0000\). The prior-adjusted winner is B.

Check. B has the largest adjusted score, \(3\), compared with \(10/7\approx1.4286\) for A and \(2\) for C. Common mistake: resolving the ordinary tie first and then adjusting only the chosen class. Adjustment must be applied to every class score before comparing them.

Choosing Weights and Interpreting the Result

Prior adjustment is one principled way to weight classes, but a class-weighted vote can also encode a decision objective. For example, a user may assign more weight to a missed urgent case than to an unnecessary review. Such weights are not automatically estimates of target probabilities. They change the decision rule to reflect the stated objective. Keep the reason for each weight explicit: prevalence correction, unequal decision costs, or another operational requirement.

The prevalence adjustment is appropriate when the training sample differs from the target population by class prevalence and the within-class predictor distributions are preserved. If class-specific sampling also changes which predictors are included within a class, the simple ratio correction need not recover target probabilities. If the training sample is representative of the target population, adjusting by inverse prevalence can instead damage a valid vote. A zero or tiny training prevalence also makes the adjustment undefined or highly sensitive to small changes.

Finally, a change in prediction is not by itself evidence that a method is better. The best choice depends on the target population and the consequences of errors. In a classification task where overall accuracy is the objective, the majority class can dominate the accuracy measure as well as the votes; other objectives may place different importance on the classes. State the objective, the relevant prevalences, and the sampling assumptions before interpreting an adjusted result.

Key takeaway: An ordinary KNN vote reflects the labels among the selected neighbors. Use prior-adjusted scores \(n_c(x)\pi_{t,c}/\pi_{s,c}\) only when the target prevalences are known or specified and class-dependent sampling preserves predictor distributions within classes. Class weights used for decision costs should be identified as decision weights, not mistaken for probability corrections.

Check Your Understanding

For each problem, distinguish the ordinary vote from any requested adjustment and use the stated sampling assumptions.

A representative training sample has two classes with prevalences 0.75 and 0.25. A query has 6 neighbors in the first class and 4 in the second, with \(k=10\). Give the ordinary prediction and explain whether prior adjustment changes it. (Answer: first class; no change, since training and target prevalences match.)
A balanced training sample has two classes, P and Q, with training prevalences 0.50 each. The target prevalences are 0.80 for P and 0.20 for Q. A query has 3 P neighbors and 5 Q neighbors. Find the ordinary and prior-adjusted winners. (Answer: ordinary winner Q; adjusted scores are \(3(0.80/0.50)=4.8\) and \(5(0.20/0.50)=2\), so the adjusted winner is P.)
Three classes have training prevalences \((0.60,0.30,0.10)\) and target prevalences \((0.50,0.30,0.20)\). A query has neighbor counts \((3,2,1)\). Calculate the normalized prior-adjusted probabilities to four decimals. (Answer: proportional scores \((2.5,2,2)\), total \(6.5\); probabilities \((0.3846,0.3077,0.3077)\).)
A study oversamples cases within one class, but the sampling also preferentially includes high-valued predictor measurements within that class. Is multiplying local votes by target-to-training prevalence ratios guaranteed to recover target probabilities? (Answer: no; the adjustment requires the predictor distribution within each class to be preserved by sampling.)
A classifier has training prevalence 0.90 for class R and 0.10 for class S, while target prevalences are 0.60 and 0.40. A query has 7 R neighbors and 3 S neighbors. Calculate the adjusted scores and winner. (Answer: R score \(7(0.60/0.90)=14/3\); S score \(3(0.40/0.10)=12\); S wins.)

What You'll Learn