A proposal for PU classification under Non-SCAR using clustering and logistic model

1. Problem Statement

The paper addresses the challenge of Positive-Unlabeled (PU) Learning, a semi-supervised learning scenario where the training data consists of:

• Positive examples ($S=1$): Confirmed positive instances ($Y=1$).
• Unlabeled examples ($S=0$): A mixture of true negatives ($Y=0$) and unobserved positives ($Y=1$).

The Core Challenge: Most existing PU learning methods rely on the SCAR (Selected Completely At Random) assumption. This assumption posits that the probability of an example being labeled ($P(S=1|Y=1)$) is constant and independent of the feature vector $X$. However, in many real-world applications (e.g., medical diagnosis, survey data), this assumption is violated (Non-SCAR scenario), where the selection probability depends on the features ($P(S=1|Y=1, X) = e(x)$).

The authors aim to:

1. Develop a computationally efficient algorithm to solve PU classification when the SCAR condition is not satisfied.
2. Evaluate the robustness of the LassoJoint method (originally designed for SCAR) when applied to Non-SCAR data.

2. Methodology

The authors propose a novel "Pecking" Cluster Cleaning Procedure combined with logistic regression and Lasso regularization. The methodology consists of the following steps:

A. The "Pecking" Cluster Cleaning Algorithm

This is the core contribution designed to handle Non-SCAR data by generating pseudo-labels for the unlabeled set.

1. Data Mixing: A proportion $q$ (e.g., 25%, 50%, or 100%) of the known positive samples ($S=1$) is drawn and added to the unlabeled pool ($S=0$) to form a temporary set $C^q_0$.
2. Clustering: The 2-means clustering algorithm is applied to $C^q_0$ to split it into two clusters: $C_{0,0}$ and $C_{0,1}$.
3. Label Assignment:
   • The cluster containing a higher density of the injected positive samples ($S=1$) is identified as the "positive" cluster ($C_{0,1}$).
   • The remaining cluster is identified as the "negative" cluster ($C_{0,0}$).
   • Cleaning: All original $S=1$ samples and the samples in $C_{0,1}$ are assigned the cleaned label $\hat{Y}=1$. The samples in $C_{0,0}$ are assigned $\hat{Y}=0$.
4. Repetition & Averaging: This process is repeated $R$ times (Monte Carlo replications). The final model coefficients are derived by averaging the results across repetitions.

B. Classification Models

Two modeling strategies are applied to the cleaned data:

1. Logistic Regression: Standard logistic regression fitted on the cleaned labels $(\hat{Y}, X)$.
2. LassoJoint: A hybrid method combining:
   • Lasso Selection: Identifying significant predictors.
   • Thresholded Lasso: Filtering features based on coefficient magnitude.
   • Joint Logistic Model: Fitting a joint model for the propensity score and the class probability.
   • Variants: The authors test "Strict" (averaging coefficients only for features selected in all repetitions) and "Non-Strict" (averaging features selected in any repetition) variants.

C. Experimental Setup

• Datasets: 11 real-world datasets from the UCI repository (e.g., Adult, Breast Cancer, Spambase) and 1 synthetic dataset.
• Non-SCAR Generation: A specific function was developed to generate the surrogate label $S$ based on high-variance features, ensuring the selection probability depends on $X$ (violating SCAR).
• Parameters: The label frequency $c$ (proportion of positives labeled) was tested at 0.3, 0.5, and 0.8. The mixing proportion $q$ was tested at 0.25, 0.5, and 1.0.
• Metrics: Accuracy, F1-score, and Area Under the Curve (AUC).

3. Key Contributions

1. Novel Cleaning Algorithm: The introduction of the "Pecking" procedure, which uses 2-means clustering to iteratively clean unlabeled data without relying on the SCAR assumption. It is computationally simpler than hierarchical clustering approaches used in previous literature.
2. Robustness Analysis: A comprehensive evaluation showing how the LassoJoint method, typically sensitive to SCAR violations, performs under Non-SCAR conditions when combined with the proposed cleaning step.
3. Efficiency: The proposed method is shown to be computationally efficient, significantly faster than methods requiring complex cross-validation for Lasso tuning in every iteration, while maintaining competitive accuracy.

4. Results

• Performance in Non-SCAR Scenarios:

  • The Cluster (Clust) method demonstrated high accuracy across most datasets, outperforming the naive approach (which treats $S$ as $Y$).
  • The LassoJoint methods (both strict and non-strict variants) achieved performance comparable to the Clust method.
  • AUC Improvements: The Lasso-based methods showed slight but consistent improvements in AUC for specific datasets (e.g., breastc, credit_a, wdbc) compared to the standard Clust method.
  • Impact of $c$: As the label frequency $c$ increased (approaching 1.0), all methods improved, with the Naive method eventually gaining an advantage as the problem approached full-label classification.
  • Parameter $q$: No single optimal value for $q$ was found; however, larger values ($q \approx 1$) generally yielded better average statistics, though specific datasets benefited from smaller $q$.

• Performance in SCAR Scenarios (Control):

  • As expected, the LassoJoint method performed nearly optimally when the SCAR assumption held true, confirming its theoretical validity.
  • The proposed Clust method also performed well in SCAR scenarios, suggesting its versatility.

• Computational Time:

  • The Naive and Clust methods were the fastest.
  • Methods involving Lasso with cross-validation (LassoJoint) were significantly slower, though the "Pecking" repetition strategy helped stabilize results without excessive computational overhead compared to other complex EM-based approaches.

5. Significance and Conclusion

• Practical Applicability: The study provides a viable solution for PU learning in real-world scenarios where the SCAR assumption is often violated (e.g., under-reporting in surveys or biased diagnosis in medicine).
• Robustness: The findings suggest that the LassoJoint method is moderately robust to SCAR violations if preceded by a clustering-based cleaning step.
• Generalization: The authors note that the 2-means clustering step is not limited to single-sample PU scenarios but can also be applied to case-control PU learning.
• Future Work: The paper establishes a foundation for using simple, computationally efficient clustering techniques to preprocess data for complex logistic models in PU settings, offering a practical alternative to more computationally intensive generative models (like GANs) or EM algorithms.

In summary, the paper successfully demonstrates that a simple 2-means clustering cleaning procedure ("Pecking") combined with Logistic Regression or LassoJoint offers a robust, efficient, and effective framework for PU classification when the strict SCAR assumption cannot be guaranteed.