-Credit card fraud commonly happens in financial institutes such as banks. Fraud results in a huge financial damage that may reach to billions of dollars every year. Detecting and preventing credit card fraud manually is a labor intensive and relatively ineffective approach. Therefore, a significant effort was made to develop automated solutions for fraud detection. Researchers dedicated their works on designing and developing models and systems in particular, the fraud anlaysis systems that enable to detect different types of fraud in different sectors including insurance, telecommunication, financial audit, financial markets, money laundering, credit card, etc. However, some problems remains unsolved. Of all, the most prevalent one is the extreme class imbalance. In this paper, we aimed at addressing this problem. We focused on the K-Nearest Neighbor (KNN) classifier and investigated the cost-sensitive approaches used for KNN. Also, we presented a novel cost-sensitive KNN approach that we developed using Cosine Similarity (CoS). We compared our model with the other methods to verify its efficiency, and we proved using several performance measures that it's a better approach than other KNN algorithms. Index Terms-Fraud detection, K-Nearest Neighbor, Imbalanced classification, Cosine similarity, Cost-sensitive learning.
Credit card fraud has always been a huge interest to financial institutes and credit card users due to its detrimental effect in case of fraudulent event. Credit card fraud is defined as an unauthorized use of a credit card account. Fraudster uses credit card information, often remotely, without the knowledge of the card owner or the card issuer. There are different types of frauds. Simple Theft (offline fraud) occurs if the card is stolen; application fraud occurs when credit card applicants obtain new credit cards using fake identity or information; bankruptcy fraud sometimes is a result of application fraud; finally, counterfeit fraud occurs when only the details of a legitimate card are stolen (skimming or shoulder surfing) and used remotely (mobile sales, online, etc.). Detecting and preventing these frauds are challenging for financial institutes. Human-driven fraud detection approaches are labor intensive.
Over the years, researchers have been working on developing an automated fraud detection system to reduce and
This work partially benefited from the support of the Lebanese National
Council for Scientific Research (CNRS-L).
prevent frauds specifically credit card fraud (e.g., [
The remainder of the paper is organized as follows. In Section II, we review the related work to credit card fraud using KNN and imbalanced classification specially the costsensitive approaches. In Section III, we describe briefly the KNN classifier and the methods compared, then in Section IV we will describe the approach we developed. In Section V, we describe the data provided and we present the results and finally a conclusion and future work.
issue [
As for credit card fraud detection, researchers used different
machine learning algorithms to classify credit card transactions
as normal or fraudulent. A survey of these methods and their
application to credit card datasets is presented by Tripathi and
Pavaskar [
KNN was rarely investigated for credit card fraud detection.
Ganji and Mannem [
Credit card fraud detection is a common example of
imbalanced data classification problem. Sahin et al. [
Kamaruddin and Vadlamani [
Qibei et al. [
In this section, we will describe the KNN classifier
algorithm using simple voting or distance weighted KNN and a
cost-sensitive KNN approach that was introduced by Qin et al.
[
KNN is a data mining method widely used for classification
and regression. It is a simple algorithm that consists of using
the k nearest points to the one we aim to predict [
1) Simple Voting: The most straightforward rule used for the classification is the simple voting. The new observation is assigned to the class of the majority of the k nearest points. The classification is done according to the following formula: y^ = argmax X c2Y
(c; class(k)) k2K Where y^ represents the foretasted value of a new observation y, c represents the possible classification categories, and K is the subset of the chosen nearest neighbors of y. The function is defined as follows: (x; y) = 0 if x = y 1 if x 6= y
The function argmax returns the value of the category 0 or 1 at which the maximum is reached, i.e. the category of the majority of the neighbors.
2) Distance Weighted: Another method is a distance weighted voting. The idea behind this approach is to take into account the distance of the neighbors and to assign a higher weight to the closest ones. The prediction is done as follows: y^ = argmax X c2Y k2K wk (c; class(k))
1 wk = d2k Where wk is the assigned weight and dk is the euclidean distance between y and the considered neighbor.
In [
Pi = k Where Pi is the probability that the class of a new observation y is i, and ki is the number of neighbors of class i. The other approach was distance weighted called Distance-CSKNN. Considering two categories 1 and 0, the idea consists of calculating costs for both classes C1 and C0 as follows: C1 = f p
P0 and
C0 = f n
P1 f p and f n represents respectively the costs of false positives and false negatives. The new sample is assigned to the class with lower Ci. In this case, the Pi are calculated in a costsensitive manner different than the one in DirectCS-KNN.
w1 w0 P1 = w1 + w0 and
P0 = w1 + w0 Where wi are the cost sensitive weights calculated as shown here: angle’s cosine between two vectors p and q representing two observations: wi = ki X wj j=1
C5.0 is one of the most common decision tree algorithms
using cross entropy and information gain to create the partition
and the splits of the tree. The costs are implemented to
the decision boundaries, not in the training algorithm [
Using only the minority cases, a one-class classification
SVM is applied with the aim of learning only the
characteristics of this class [
The purpose of this method is to find a “small” region
that groups most of the minority training observations. This
requires defining a function f that returns 1 if a point belongs
in this region and -1 elsewhere [
i wT (xi) i i 0; i = 1; : : : ; l Where : X ! F is a mapping function. This problem is solved by separating the points from the origin with maximum margin ( jjwjj ) using a hyperplane of equation: wT (xi) = .
IV. COST-SENSITIVE KNN APPROACH (COSKNN) We developed a Cost-Sensitive KNN approach. Our aim was to tackle the imbalance problem by using cosine similarity as a distance metric and by introducing a score for the classification. In order to improve the method’s performance in terms of imbalance, we also studied the choice of the score’s thresholds and the number of neighbors to consider. These steps are described in the following:
The first step of our new approach is the change of the distance metric used. This metric consists of calculating the CoS (p; q) = vu n uX piqi t
i=1 vu n vu n utX pi2utX qi2 i=1 i=1 We replaced euclidean distance used in KNN with this metric when calculating the distance between observations in order to find the nearest neighbors.
Note that, this metric ranges between -1 and 1. If CoS is close to 1, it indicates that the angle between the two observations is close to zero and therefore they are similar (neighbors).
The advantage of using CoS instead of euclidean distance is highlighted in the coming section when we compared KNN (whether simple voting or with weighted distance) with both metrics and we found that CoS is better in terms of sensitivity.
The second step of our approach, after finding the neighbors, is to introduce an imbalanced classification approach while using CoS. The idea is to evaluate the similarity of an observation to its neighbors of the minority class, taking into account the other class as well. This was done by calculating the following score Sy for each sample y:
Sy = i=1 k X Ci : CoSi k X CoSi i=1
k is the number of neighbors considered for y.
C is a vector of length k, Ci 2 f0; 1g that represents the classes of the neighbors. 0 is used to denote the class of the majority group and 1 is used for the minority group.
CoS is another vector representing the Cosine similarity between y and its neighbors.
This score ranges from 0 to 1. It works similarly to a probability, that describes the likelihood of an observation to be in the minority group. When it’s close (or equal) to zero, it indicates that the neighbors are mostly (or all) of the majority group, which would lead to a majority group classification. However, when at least one of the neighbors of y is of the minority class, this score will be higher than zero; and closer to one, the more the neighbors are of the minority group.
The classification is done according to a certain threshold 2 [0; 1].
y^ = 0 if Sy 1 if Sy >
The choice of is not straightforward. A very low value will lead to a large number of false positives (observations of the majority group classed as minority). However, a high threshold value will lead to very low sensitivity rate. Therefore, should have a slightly low value. Taking into account the imbalance ratio of 5%, was later chosen according to the 95th percentile of Sy, and optimized by comparing the sensitivity according to the values of .
The choice of k has an effect on many aspects of the approach. The number of neighbors should be large enough to be informative about the sample’s neighborhood. On the other hand, due to the imbalance, a high number of neighbors will make the classification biased towards the majority group and time consuming.
After trying several possible values of k, we found that considering 10 neighbors is the best for our case.
To prove the efficiency of our approach, we compared it to
the original KNN classifier using both euclidean distance and
cosine similarity, with simple voting and distance weighted
approach. We also compare it with cost sensitive C5.0, one
class classification SVM and Distance-CS-KNN [
The data we used is extracted from a credit card fraud labeled data1. The data contains 10 million observations (in our case, the observations are financial transactions) and 8 variables described in the following.
The explanatory variables are: gender representing the client’s gender, state is a categorical variable denoting the state where the client lives, cardholder representing the number of cards that the client have, balance is a continuous variable that indicates the balance on the credit card, the number of transactions and international transactions made to date, respectively denoted by numTrans and numIntTrans, and creditLine which is the credit limit of the client, and the variable to predict fraudRisk indicating if each observation is fraud (denoted 1) and legitimate (denoted 0). 596,014 (representing 5.96%) are fraud cases and 9,403,986 (representing 94.03%) are legitimate.
In this paper, we extracted a part of the original data due to the time consumption of the KNN method when calculating the distance to all observations in the training set. The new data consists of 6000 credit card transactions (observations) in which we have 5657 Legitimate(0) cases, and 343 fraud(1). This dataset takes into account the imbalance ratio and have the same characteristics as the original one.
These proportions exemplify the extreme imbalance. The fraud
cases represents 5.7% of the dataset. The fraud detection in
this case is very challenging. In fact an accuracy rate less
than 94.3% is not acceptable, because simply an algorithm
that classify all data points as legitimate will give us this
1Available at http://packages.revolutionanalytics.com/datasets/
high accuracy. The choice of other performance measures will
be discussed later. This data is divided between train (3999
transactions) and test (2001 transactions) with similar ratio
of imbalance. For all KNN methods, 10 nearest neighbors
are considered to classify the new samples, and data is first
normalized using the mean and standard deviation of the
variables, to avoid bias towards variables with large ranges
[
In this section, we show the results of the comparison of our approach with the other existing in the state of the art. The compared methods are given in Table I.
The use of the accuracy alone as a performance measure is misleading. Other measures should be considered as well, like the sensitivity, also known as recall. The challenge is that most imbalanced classification methods focus on increasing the sensitivity, which will lead to a slight decrease in accuracy. This decrease that can sometimes be just 1% may seem insignificant, but in fact, it hides a high number of false alarms. Thus, we need to rely also on measures that finds a trade-off between the high accuracy and the sensitivity; the Area Under Precision-Recall Curve (AUPRC), is used for that purpose. However, since we may not always be able to plot this curve like the case of CS - C5.0 and OCC - SVM, we will also use the F1 score, also known as F-measure. To evaluate these measures, a confusion matrix (Table II) is calculated using the test set. The accuracy shows the percentage of the legitimate and fraud transactions correctly predicted.
Recall =
T P T P + F N and
P recision =
T P T P + F P However, the recall or sensitivity focus only on the fraud detection and the true positive rate, and the precision measures the fraction of examples classified as positive that are truly positives.
The Precision-Recall (PR) curve is obtained by plotting the precision over recall rate through different class probabilities thresholds. The closer the curve is to the upper-right-hand corner the better the model is. It is not always straightforward to find the class probabilities, so we will also use the F1 score. The higher this score the better.
F1 score = 2
P recision Recall
P recision + Recall
Table III shows the performance measures (the accuracy, the sensitivity, the AUPRC and the F1 score) for all methods and our new approach. The PR curves are shown in the Figure 1. This table shows that the accuracy is higher than 94.3% for all models except the CS - C5.0 and OCC - SVM. The slight differences of the accuracy between all the other methods shows how much information this measure hides when the imbalance is extreme. We can conclude from the table when comparing the performance measures of EuCKNN with CKNN and DEuCKNN with DCKNN that the use of cosine similarity is improving the classification according to the sensitivity, AUPRC and F1 score, with a reasonable decrease in accuracy.
Our approach CoSKNN is outperforming all the methods according to the AUPRC and F1 score. It is considerably improving the sensitivity when compared to the simple KNN. The other cost-sensitive models are performing better in terms of sensitivity, but at the cost of raising false alarms and decreasing the accuracy sometimes to a less than acceptable value, like the case of CS-C5.0 and OCC-SVM.
Credit card fraud detection is one of the most challenging problems for financial institutes. The financial institutes such as banks are losing billions of dollars every year due to fraudulent activities committed by the fraudsters. Over the years, a number of solutions has been been proposed in large bodies of literature. However, some problems are still open. The class imbalance problem is one of the most critical problems that is yet to be solved.
In this paper, we aimed at addressing this problem. We investigated the use of KNN in fraud detection. We proposed a cost-sensitive KNN approach to tackle the imbalance problem. We provided a comprehensive detail of our new approach. In our approach we used cosine similarity instead of the euclidean distance to find the neighbors, and then calculated a certain score to evaluate the probability of fraud risk.
We also presented a comparative study in this paper. In our study, we compared the performance of simple voting KNN and distance weighted KNN using both euclidean distance and cosine similarity, with another cost sensitive KNN, decision tree approach, one class classification SVM and our new approach. The comparison was done by applying these methods to a credit card fraud dataset with imbalance, using multiple performance measures, mostly relying on AUPRC and F1 score. This experiment shows that our approach is outperforming all the other methods.
We encountered several challenges in our study. The most prevalent one is the elapsed time that restricted us the use of number of observations for the training set which could not exceed 3999. This is an obvious limitation of our experiment.
Several works have been lined up to extend our current work. We planned to work on implementing our approach in a big data environment in order to use the massive amount of data. Another interesting task which we planned is finding an optimized threshold that can be selected automatically instead of letting user to investigate and find it.