Apparatus and method for detecting and removing outliers using sensitivity score

1. An apparatus for detecting outliers of a digitized text corpus, the apparatus comprising:

a memory for storing instructions; and

a processor that, when executing the instructions performs a method, the method comprising:

receiving the digitized text corpus comprising a plurality of data points (X={x i } i=1 n );

identifying k clusters of the plurality of data points, wherein k is a natural number smaller than n;

sampling a data point among the plurality of data points as a first cluster center of the k clusters;

determining sampling probability of each of remaining data points of the plurality of data points, wherein the remaining data points indicate a difference between the plurality of data points and the sampled data point and the sampling probability indicates a probability of each of the remaining data points to be sampled as a next cluster center of the k clusters;

sampling the next cluster center based on the sampling probability and iterate the process of determining sampling probability and the process of sampling the next cluster center until k cluster centers are sampled to form a set of cluster centers C={C} i=1 k , wherein each of the k cluster centers corresponds to each of the k clusters;

generating weightage for each of the k cluster centers by counting a number of data points belonging to each of the k cluster centers;

determining sensitivity scores of the data points belonging to each of the k cluster centers based on the weightage for each of the k cluster centers;

labeling, based on the determined sensitivity scores, a data point having a sensitivity score greater than a threshold value as an outlier of the digitized text corpus and removing the outlier from the digitized text corpus; and

providing a first parameter of the digitized text corpus by analyzing the removed outlier or a second parameter of the digitized text corpus by analyzing data points without the outlier.

2. The apparatus of claim 1 , wherein the k clusters of the plurality of data points are identified by spherical k-means clustering algorithm applied to the plurality of data points.

3. The apparatus of claim 1 , wherein the first cluster center is selected among data points belonging to a cluster having a highest density of data points among the k clusters.

4. The apparatus of claim 1 , wherein the sampling probability is determined by calculating angular distance between the sampled data point and each of the remaining data points and normalizing the calculated angular distance with a sum of all distances between the sampled data point and the remaining data points.

5. The apparatus of claim 1 , wherein a sensitivity of a data point is determined based on determination of a maximal ratio between a cost contribution of the data point and an average cost contribution of the plurality of data points.

6. The apparatus of claim 1 , wherein the number of data points belonging to each of the k cluster centers is determined by assigning each of the plurality of data points to a nearest cluster center among the k cluster centers and determining distance between each of the plurality of data points and the corresponding nearest cluster center.

7. The apparatus of claim 1 , wherein the threshold value is determined based on a number of outliers that a user decided to detect and remove from the digitized text corpus.

8. A method for detecting outliers of a digitized text corpus, the method comprising:

receiving the digitized text corpus comprising a plurality of data points (X={x i } i=1 n );

identifying k clusters of the plurality of data points, wherein k is a natural number smaller than n;

sampling a data point among the plurality of data points as a first cluster center of the k clusters;

determining sampling probability of each of remaining data points of the plurality of data points, wherein the remaining data points indicate a difference between the plurality of data points and the sampled data point and the sampling probability indicates a probability of each of the remaining data points to be sampled as a next cluster center of the k clusters;

sampling the next cluster center based on the sampling probability and iterate the process of determining sampling probability and the process of sampling the next cluster center until k cluster centers are sampled to form a set of cluster centers C={C} i=1 k , wherein each of the k cluster centers corresponds to each of the k clusters;

generating weightage for each of the k cluster centers by counting a number of data points belonging to each of the k cluster centers;

determining sensitivity scores of the data points belonging to each of the k cluster centers based on the weightage for each of the k cluster centers;

labeling, based on the determined sensitivity scores, a data point having a sensitivity score greater than a threshold value as an outlier of the digitized text corpus and removing the outlier from the digitized text corpus; and

providing a first parameter of the digitized text corpus by analyzing the removed outlier, or a second parameter of the digitized text corpus by analyzing data points without the outlier.

9. The method of claim 8 , wherein the identifying k clusters of the plurality of data points further comprises:

applying, by the processor, spherical k-means clustering algorithm to the plurality of data points.

10. The method of claim 8 , wherein the first cluster center is selected among data points belonging to a cluster having a highest density of data points among the k clusters.

11. The method of claim 8 , wherein the determining sampling probability of each of remaining data points of the plurality of data points further comprises:

calculating, by the processor, angular distance between the sampled data point and each of the remaining data points; and

normalizing, by the processor, the calculated angular distance with a sum of all distances between the sampled data point and the remaining data points.

12. The method of claim 8 , wherein a sensitivity of a data point is determined based on determination of a maximal ratio between a cost contribution of the data point and an average cost contribution of the plurality of data points.

13. The method of claim 8 , wherein the generating weightage of each of the k cluster centers further comprises:

assigning, by the processor, each of the plurality of data points to a nearest cluster center among the k cluster centers; and

determining, by the processor, distance between each of the plurality of data points and the corresponding nearest cluster center.

14. The method of claim 8 , wherein the threshold value is determined based on a number of outliers that a user decided to detect and remove from the digitized text corpus.

15. A non-transitory computer readable medium including instructions stored thereon that when processed by a processor cause a system for detecting outliers of a digitized text corpus to perform acts of:

receiving the digitized text corpus comprising a plurality of data points (X={x i } i=1 n );

identifying k clusters of the plurality of data points, wherein k is a natural number smaller than n;

sampling a data point among the plurality of data points as a first cluster center of the k clusters;

determining sampling probability of each of remaining data points of the plurality of data points, wherein the remaining data points indicate a difference between the plurality of data points and the sampled data point and the sampling probability indicates a probability of each of the remaining data points to be sampled as a next cluster center of the k clusters;

sampling the next cluster center based on the sampling probability and iterate the process of determining sampling probability and the process of sampling the next cluster center until k cluster centers are sampled to form a set of cluster centers C={C} i=1 k , wherein each of the k cluster centers corresponds to each of the k clusters;

generating weightage for each of the k cluster centers by counting a number of data points belonging to each of the k cluster centers;

determining sensitivity scores of the data points belonging to each of the k cluster centers based on the weightage for each of the k cluster centers;

labeling, based on the determined sensitivity scores, a data point having a sensitivity score greater than a threshold value as an outlier of the digitized text corpus and removing the outlier from the digitized text corpus; and

providing a first parameter of the digitized text corpus by analyzing the removed outlier or a second parameter of the digitized text corpus by analyzing data points without the outlier.

16. The medium of claim 15 , wherein the identifying k clusters of the plurality of data points further comprises:

applying spherical k-means clustering algorithm to the plurality of data points.

17. The medium of claim 15 , wherein the first cluster center is selected among data points belonging to a cluster having a highest density of data points among the k clusters.

18. The medium of claim 15 , wherein the determining sampling probability of each of remaining data points of the plurality of data points further comprises:

calculating angular distance between the first cluster center and each of the remaining data points; and

normalizing the calculated angular distance with a sum of all distances between the first cluster center and the remaining data points of the plurality of data points.

19. The medium of claim 15 , wherein a sensitivity of a data point is determined based on determination of a maximal ratio between a cost contribution of the data point and an average cost contribution of the plurality of data points.

20. The medium of claim 15 , wherein the threshold value is determined based on a number of outliers that a user decided to detect and remove from the data set.

21. The medium of claim 15 , wherein the generating weightage of each of the k cluster centers further comprises:

assigning each of the plurality of data points to a nearest cluster center among the k cluster centers; and

determining distance between each of the plurality of data points and the corresponding nearest cluster center.