3
$\begingroup$

I have a training set mapping some Likert-scale variables (integers between 1 and 7, rescaled to real numbers between 0 and 1) to predict a continuous variable between 0 and 1. The data set is reasonable large ($10^4$-$10^5$ rows) but very noisy (5-20% has bogus labeling).

When applying regression algorithms to this dataset, the regression algorithm predicts scores only in a subinterval of [0,1], e.g. scores below 0.1 and above 0.9 are not reached for any input value of the columns. This is expected given the bogus labels; but also inacceptable, as the prediction for non-bogus rows is severely impacted. Moreover, since 0.0 and 1.0 are the most common target values in the training set (it is a 'How much ... are you?' type prediction) it is not appreciated by the users that 0.0 and/or 1.0 would be unreachable. (Simply stretching the result to cover [0,1] greatly increases the error, so is probably suboptimal.)

What method could I use to detect and remove these mislabeled/bogus rows, or at least a significant amount of them? Since they are a minority, I would think something with majority voting should be the answer, but it's not clear how to implement such an approach, since $7^{n_{cols}} > n_{rows}$.

$\endgroup$
2
+50
$\begingroup$

Since you seem to have enough data, RANSAC could be a good option. That is, we treat the noisy data as outliers. The idea of RANSAC is to iteratively detect those outliers and discard them from the fitting. It is extensively used in image processing for tasks like camera calibration and segmenting primitives like planes in a 3D point cloud, with very good results, because it is able to handle a high rate of outliers, when there are enough data points (as it is your case).

For the sake of completeness, let me copy verbatim the description of the algorithm from Wikipedia (a more detailed though still accessible introduction can be found in RANSAC for dummies by M. Zuliani.

    Given:
        data – a set of observations
        model – a model to explain observed data points
        n – minimum number of data points required to estimate model parameters
        k – maximum number of iterations allowed in the algorithm
        t – threshold value to determine data points that are fit well by model 
        d – number of close data points required to assert that a model fits well to data

    Return:
        bestFit – model parameters which best fit the data (or nul if no good model is found)

    iterations = 0
    bestFit = nul
    bestErr = something really large
    while iterations < k {
        maybeInliers = n randomly selected values from data
        maybeModel = model parameters fitted to maybeInliers
        alsoInliers = empty set
        for every point in data not in maybeInliers {
            if point fits maybeModel with an error smaller than t
                add point to alsoInliers
        }
        if the number of elements in alsoInliers is > d {
            % this implies that we may have found a good model
            % now test how good it is
            betterModel = model parameters fitted to all points in maybeInliers and alsoInliers
            thisErr = a measure of how well betterModel fits these points
            if thisErr < bestErr {
                bestFit = betterModel
                bestErr = thisErr
            }
        }
        increment iterations
    }
    return bestFit

$\endgroup$
1
$\begingroup$

Considering the size of the Dataset Mentioned by you can use Heterogenous Ensemble, Homogenous Ensemble or Edited Nearest Neighbors for Filtering the noise in the Data.

The homogeneous ensemble is inspired by Cross-Validated Committees Filter[1]. At noise levels approximately more than 10% Heterogenous Ensemble performs worse than Homogenous Ensemble.

So you should use Homogenous Ensemble to filter the noise. You can use Apache-Spark to implement this model. Here is the algorithm for this method:

  • Input: data consisting of labels and features
  • Input: P= the number of partitions
  • Input: n= Trees the number of trees for Random Forest
  • Input: e= error tolerance (0<e<1)
  • Output: the filtered data without noise
  • partitions ← kFold(data, P)
  • filteredData ← NULL
  • for all train, test in partitions do
  •       rfModel ← random Forest(train, n Trees)
  •       rfPred ← predict(rfModel, test)
  •       joinedData ← join(zipWithIndex(test), zipWithIndex(rfPred))
  •       markedData ←
  •       map original, prediction ∈ joinedData
  •       if label(prediction)-(label(prediction)) *e < label(original) < label(prediction)+
         (label(prediction))*e then
  •           original
  •       else
  •           (label = NULL, features(original))
  •       end if
  • end map
  • filteredData ← union(filteredData, markedData)
  • end for
  • return(filter(filteredData, label != NULL))

[1]       [C.E. Brodley, M.A. Friedl. Identifying Mislabeled Training Data. Journal of Artificial Intelligence Research 11 (1999) 131-167 doi: 10.1613/jair.606]

$\endgroup$
  • $\begingroup$ (1) Why use k-fold validation with random forests instead of the inherent out of bag prediction? It's not clear to me what the benefit would be. (2) Since this is a regression problem, not a classification problem, label(original) = label(prediction) is an extremely rare condition that will likely miss 100% of my data. Any suggestions on how to do this for regression? I could of course replace it by abs(label(original)-label(prediction))<0.5 but that seems rather arbitrary; especially the constant. $\endgroup$ – user1111929 Feb 16 at 23:32
  • $\begingroup$ You are right, I have corrected the algorithm so it can be used in a regression model. You have to choose the error tolerance though. I suggest choosing a value which does not deplete your data set by a large amount. $\endgroup$ – A-ar Feb 17 at 0:04
  • $\begingroup$ Using a proper k-fold validation is usually better (i.e, more robust) than in built out of bag. $\endgroup$ – Tom Feb 18 at 15:04
  • $\begingroup$ @Tom care to elaborate why you believe this to be the case? Oob doesn't use the row at hand for training, so should be equally robust as a proper k-fold, from what I understand. $\endgroup$ – user1111929 Feb 20 at 2:43
  • 1
    $\begingroup$ I think it is better to check this study to get a better intuition: file.scirp.org/pdf/OJS20110300008_18086118.pdf. I think it is mostly fine in practice to use either OOB or proper cross validation. However, in cross-validation your test/val fold is always unique, and so is your training set, so it gives you a better idea (less biased) on how it would generalize on unknown data. But in practice, with enough trees in your forest, it should not be an issue in general. $\endgroup$ – Tom Feb 20 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.