Adaptive Fraud Detection.
One method for detecting fraud is to check for suspicious changes in user behavior. This paper describes the automatic design of user profiling methods for the purpose of fraud detection, using a series of data mining techniques. Specifically, we use a rule-learning program to uncover indicators of fraudulent behavior from a large database of customer transactions. Then the indicators are used to create a set of monitors, which profile legitimate customer behavior and indicate anomalies. Finally, the outputs of the monitors are used as features in a system that learns to combine evidence to generate high-confidence alarms. The system has been applied to the problem of detecting cellular cloning fraud based on a database of call records. Experiments indicate that this automatic approach performs better than hand-crafted methods for detecting fraud. Furthermore, this approach can adapt to the changing conditions typical of fraud detection environments.
Introduction
In the United States, cellular fraud costs the telecommunications industry hundreds
of millions of dollars per year (Walters and Wilkinson 1994; Steward 1997). One
kind of cellular fraud called cloning is particularly expensive and epidemic in major
cities throughout the United States. Cloning fraud causes great inconvenience to
customers and great expense to cellular service providers. Existing methods for
detecting cloning fraud are ad hoc and their evaluation is virtually nonexistent.
We have embarked on a program of systematic analysis of cellular call data for the
purpose of designing and evaluating methods for detecting fraudulent behavior.
Cloning fraud is one instance of superimposition fraud, in which fraudulent usage
is superimposed upon (added to) the legitimate usage of an account. Other
examples are credit card fraud, calling card fraud and some forms of computer in-
trusion. Superimposition fraud typically occurs when a non-legitimate user gains
illicit access to the account or service of a legitimate user. Superimposition fraud
is detectable if the legitimate users have fairly regular behavior that is generally
distinguishable from the fraudulent behavior.
This paper presents a framework, and a corresponding system, for automatically
generating detectors for superimposition fraud. We have applied the system in the
domain of cellular cloning fraud. Under the framework, massive amounts of cellular
call data are analyzed in order to determine general patterns of fraud. These patterns
are then used to generate a set of monitors, each of which watches customers'
behavior with respect to one discovered pattern. A monitor profiles each customer's
typical behavior and, in use, measures the extent to which current behavior is abnormal
with respect to the monitor's particular pattern. Each monitor's output is
provided to a neural network, which weights the values and issues an alarm when
the combined evidence for fraud is strong enough.
This article is organized as follows. We first describe the problem of cellular
cloning fraud and some existing strategies for detecting it. We then describe the
framework in detail using examples from the implemented system. We present
experimental results comparing the system against other known methods for detecting
fraud. Finally, we discuss the evaluation and describe issues in the future
of automatic fraud detection.
2. Cellular Communications and Cloning Fraud
Whenever a cellular phone is on, it periodically transmits two unique identification
numbers: its Mobile Identification Number (MIN) and its Electronic Serial Number
(ESN). These two numbers together specify the customer's account. These numbers
are broadcast unencrypted over the airwaves, and they can can be received, decoded
and stored using special equipment that is relatively inexpensive.
2.1. Cloning Fraud
Cloning occurs when a customer's MIN and ESN are programmed into a cellular
telephone not belonging to the customer. When this second telephone is used,
the network sees the customer's MIN and ESN and subsequently bills the usage
to the customer. With the stolen MIN and ESN, a cloned phone user (whom we
shall call a bandit) can make virtually unlimited calls, whose charges are billed to
the customer. The attraction of free and untraceable communication makes cloned
phones very popular in major metropolitan areas.
If the fraudulent usage goes undetected, the customer's next bill will include
the corresponding charges. Typically, the customer then calls the cellular service
provider (the carrier) and denies the usage. The carrier and customer then determine
which calls were made by the "bandit" and which were legitimate calls. The
fraudulent charges are credited to the customer's account, and measures are taken
to prohibit further fraudulent charges. In certain cases, the fraudulent call records
will be referred to a law enforcement agency for prosecution.
There are two primary motivations for cloning fraud. Obviously, cloning fraud
allows low-cost communications. A bandit is not charged for calls, which are usually
worth far more (in retail dollars) than the cost of the cloned phone. Less
obviously, cloning fraud allows untraceable communications because the bandit's
identity cannot be tied to the cloned account. This second aspect is very important
to criminals (DeMaria and Gidari 1996).
Cloning fraud is detrimental in many ways. First, fraudulent usage congests cell
sites, causing service to be denied to legitimate customers. Second, most cellular
calls are to non-cellular destinations, so fraud incurs land-line usage charges. Third,
cellular carriers must pay costs to other carriers for usage outside the home territory.
Because these are retail costs, they constitute a considerable financial burden to
the customer's carrier. Fourth, the crediting process is costly to the carrier and
inconvenient to the customer; the customer is more likely to switch to another
carrier ("customer churn") if the other is perceived to be less susceptible to fraud.
For these reasons, cellular carriers have a strong interest in reducing cloning fraud.
2.2. Strategies for dealing with cloning fraud
There are two classes of methods for dealing with cloning fraud. Pre-call methods
try to identify and block fraudulent calls as they are made. Post-call methods try
to identify fraud that has already occurred on an account so that further fraudulent
usage can be blocked.
2.2.1. Pre-call methods Pre-call detection methods involve validating the phone
or its user when a call is placed. A common method is requiring that a Personal
Number (PIN) be entered before every call. A PIN serves as a password
that is validated by the switch prior to allowing the call into the network.
PINs are in use throughout many metropolitan areas in the United States. Unfor-
tunately, like MIN-ESN pairs, PINs are broadcast over the airwaves unencrypted.
For technical reasons, PINs are more difficult to receive and decode, but with more
sophisticated equipment PIN cracking is possible (Herzog 1995). Although PINs
make cloning fraud more difficult, they do not prevent it.
Other methods of prevention include RF Fingerprinting and Authentication (Red-
den 1996). RF Fingerprinting is a method of identifying cellular phones by their
transmission characteristics. Authentication is a reliable and secure private-key
encryption method that imposes no inconvenience on the customer. It has been
predicted that authentication will eliminate cloning fraud eventually. However,
authentication requires changes in hardware: both phones and switches must be
capable of processing authentication requests. Currently about thirty million non-
authenticatable cell phones are in use in the United States alone, and their replacement
will not be immediate (Steward 1997). In the meantime, cloning fraud will
continue to be a problem and the industry will rely on post-call fraud detection
methods.
2.2.2. Post-call methods Post-call methods periodically analyze call data on each
account to determine whether cloning fraud has occurred. One such method, collision
detection, involves analyzing call data for temporally overlapping calls. Since
a MIN-ESN pair is licensed to only one legitimate user, any simultaneous usage is
probably fraudulent. A closely related method, velocity checking (Davis and Goyal
1993), involves analyzing the locations and times of consecutive calls to determine
whether a single user could have placed them while traveling at reasonable speeds.
For example, if a call is made in Los Angeles 20 minutes after a call is made on the
same account in New York, two different people are likely using the account.
Date & Time Day Duration Origin Destination Fraud
mins Brooklyn, NY Stamford,CT
1/05/95 14:53:27 Fri 5 mins Brooklyn, NY Greenwich,CT
1/08/95 09:42:01 Mon 3 mins Bronx, NY White Plains, NY
1/08/95 15:01:24 Mon 9 mins Brooklyn, NY Brooklyn, NY
1/09/95 15:06:09 Tue 5 mins Manhattan, NY Stamford, CT
1/09/95 16:28:50 Tue 53 sec Brooklyn, NY Brooklyn, NY
1/10/95 01:45:36 Wed 35 sec Boston, MA Chelsea, MA bandit
1/10/95 01:46:29 Wed 34 sec Boston, MA Yonkers, NY bandit
1/10/95 01:50:54 Wed 39 sec Boston, MA Chelsea, MA bandit
1/10/95 11:23:28 Wed 24 sec White Plains, NY Congers, NY
1/11/95 22:00:28 Thu 37 sec Boston, MA East Boston, MA bandit
East Boston, MA bandit

Figure

1. Call records of a sample frauded account
Collisions and velocity checks are both believed to be accurate, but they share
the disadvantage that their usefulness depends upon a moderate level of legitimate
activity. Low-usage subscribers (for example, people who only use cellular phones
in emergencies) will rarely cause collisions or velocity alarms with bandits.
Another post-call method, dialed digit analysis, mines call data to build up a
database of telephone numbers called by bandits during periods of fraudulent ac-
tivity. For detection, this database is matched against the numbers called by cus-
tomers, and alarms are produced when the number of hits is above a threshold
("dialed digit hits").
2.2.3. User profiling User profiling methods constitute a special class of post-call
methods. They involve analyzing calling behavior in order to detect usage anomalies
suggestive of fraud. Profiling often works well with low-usage subscribers because
unusual behavior is very prominent. For this reason, profiling is a good complement
to collision and velocity checking because it covers cases the others might miss.

Figure

shows some chronological call data from an example (fabricated) frauded
account (the fields shown are just a sample; our call data contain many more
attributes than shown here). The column at the far right indicates whether the call
is fraudulent or not; that is, whether the call was placed by the customer or the
bandit. A fraud analyst looking at this account would quickly be able to recognize
the two classes of calls:
1. The legitimate user calls from the metro New York City area, usually during
working hours, and typically makes calls lasting a few minutes.
2. The bandit's calls originate from a different area (Boston, Massachusetts, about
200 miles away), are made in the evenings, and last less than a minute.
Ideally, a fraud detection system should be able to learn such rules automatically
and use them to catch fraud.
This paper addresses the automatic design of user profiling methods. User profiling
methods are attractive because they do not depend upon any special hardware
capability, as authentication does, nor do they require that the customer replace
or upgrade existing equipment. Moreover, the ability to generate such detectors is
domain independent: such a system should be able to generate fraud detectors for
any domain with superimposition fraud.
2.3. The Need to be Adaptive
There are a number of commercially available expert systems for fraud detection
that include user profiling. Fraud analysts or system administrators can tune the
techniques by adjusting parameters, or by entering specific patterns that will trigger
alarms. Unfortunately, determining which potential patterns will be useful is a time-consuming
process of trial-and-error. Moreover, the patterns of fraud are dynamic.
Bandits constantly change their strategies in response to new detection techniques
or new cellular hardware capabilities. By the time a system is manually tuned, the
fraudulent behavior may have changed significantly.
The environment is dynamic in other ways as well. The level of fraud changes
dramatically month-to-month because of modifications to work practices (both the
carrier's and the bandits'). Also, the costs of missing fraud or of dealing with false
alarms change with intercarrier contracts, and because of fraud analyst workforce
issues.
For all these reasons, it is important that a fraud detection system adapt easily
to new conditions. It should be able to notice new patterns of fraud. It should also
be able to modify its alarm generation behavior, for example, as the level of fraud
or the cost of dealing with a false alarm changes. Such adaptability can be achieved
by generating fraud detection systems automatically from data, using data mining
techniques.
3. Automatic Construction of Profiling Fraud Detectors
One approach to building a fraud detection system is to classify individual trans-
actions, calls in our case, as being fraudulent or legitimate. Classification has been
well explored, e.g., in machine learning and statistics, so this would seem to be a
straightforward application of existing techniques.
We have not had success using standard machine learning techniques to construct
such a classifier. Some specific results are discussed in Section 6.3. In general, there
are two problems that make simple classification approaches infeasible.
call that would be unusual for one customer would be typical for
another. For example, a call placed from Brooklyn is not unusual for a subscriber
who lives there, but might be very strange for a Boston subscriber.
6 FAWCETT AND PROVOST
Thus, it is necessary (i) to discover indicators corresponding to changes in behavior
that are indicative of fraud, rather than absolute indicators of fraud, and
(ii) to profile the behavior of individual customers to characterize their normal
behavior.
If there were available substantial information about an account's context, we
could possibly ameliorate this problem. Context information would comprise
behavior information such as what the phone is used for, what areas it is used
in, what areas/numbers it normally calls, what times of day, and so on. Context
information is not available, 1 so our solution is to derive it from historical data
specific to each account. The discovery of context-sensitive fraud indicators and
the profiling of individual accounts comprise two of the three major elements
of the learning problem.
At the level of the individual call, the variation in calling behavior
is large, even for a particular user. Legitimate subscribers occasionally make
calls that look suspicious. As far as we have been able to determine, it is not
possible to achieve simultaneously the high degree of accuracy and high level
of coverage necessary to classify individual calls effectively. Any classifier that
fires on a significant number of defrauded accounts produces unacceptably large
numbers of false alarms. Therefore, decisions to take corrective action cannot
be made with confidence on the basis of individual calls. Instead, it is necessary
to aggregate customer behavior, smoothing out the variation, and watch for
coarser-grained changes that have better predictive power. This is the third
major element of the learning problem; in the experiments we describe later,
we aggregate customer behavior into account-days.
In sum, the learning problem comprises three questions, each of which corresponds
to a component of our framework.
1. Which call features are important? Which features or combinations of features
are useful for distinguishing legitimate behavior from fraudulent behavior?
2. How should profiles be created? Given an important feature, how should we
characterize/profile the behavior of a subscriber with respect to the feature, in
order to notice important changes?
3. When should alarms be issued? Given the results of profiling behavior based on
multiple criteria, how should they be combined to be effective in determining
when fraud has occurred?
Each of these issues corresponds to a component of our framework.
4. The Detector Constructor Framework
Our Detector Constructor framework is illustrated in Figure 2. Under the frame-
work, a system first learns rules that serve as indicators of fraudulent behavior. It
Monitor
Construction
Monitor
templates
Rules
Fraud
Detector
Call data
Mn
Training
and Selection
Rule Learning
Classifier
Profiling
monitors

Figure

2. The framework for automatically constructing fraud detectors.
then uses these rules, along with a set of templates, to create profiling monitors
These monitors profile the typical behavior of each account with
respect to a rule and, in use, describe how far each account is from its typical be-
havior. Finally, the system learns to weight the monitor outputs so as to maximize
the effectiveness of the resulting fraud detector.

Figure

3 shows how such a detector will be used. The monitors are provided with
a single day's calls from a given account, and each monitor generates a number indicating
how unusual that account-day looks for the account. The numeric outputs
from the monitors are treated as evidence and are combined by the detector. When
the detector has enough evidence of fraudulent activity on an account, based on
the indications of the monitors, it generates an alarm.
We now discuss each step of the framework in detail, illustrated by the particular
choices made in our first implemented system, as applied to the problem of cloning
fraud detection. The first Detector Constructor system is called DC-1. The call
data used for detecting cloning fraud are chronological records of calls made by
each subscriber, organized by account. These data describe individual calls using
attributes such as DATE, FROM-STATE, DURATION and CELL-SITE.
Account-Day
Day Time Duration Origin Destination
mins Bronx, NY Miami, FL
Tue 10:05 3 mins Scarsdale, NY Bayonne, NJ
Tue 11:23 24 sec Scarsdale, NY Congers, NY
Tue 14:53 5 mins Tarrytown, NY Greenwich, CT
Tue 15:06 5 mins Manhattan, NY Westport, CT
Tue 16:28 53 sec Scarsdale, NY Congers, NY
Tue 23:40 17 mins Bronx, NY Miami, FL
BRONX at night
# calls from
exceeds
daily threshold
Airtime from
BRONX at night
SUNDAY airtime
exceeds
daily threshold1 0
Value normalization
and weighting
FRAUD ALARM
Combining
Evidence >= q
Profiling
Monitors

Figure

3. A DC-1 fraud detector processing a single account-day of data.
4.1. Learning Fraud Rules
The first stage of detector construction, rule learning, involves searching the call
data for indicators of fraud. In the DC-1 system, the indicators are conjunctive
rules discovered by a standard rule-learning program.
As discussed above, an obvious way of mining fraud indicators is to create an
example set consisting of all frauded calls and all legitimate calls, and apply a rule
learning algorithm to the example set. However, this approach loses context information
about the normal behavior of the account in which the fraud occurred.
To illustrate the importance of context, consider a situation in which half the subscribers
live in New York and half in Los Angeles. When cloned, the New York
accounts are used in Los Angeles and the Los Angeles accounts are used in New
York. Applying rule learning to the combined set of call records would uncover no
fraud rules based on call origin; in other words, knowing that a call originated in
New York says nothing about how likely it is to be fraud. In fact, this conclusion
would be wrong: in this scenario a New York account with Los Angeles calls is
much more likely to have been cloned than if it had only New York calls. This fact
is missed when using a combined example set, because in combining examples all
account context information is lost.
In light of the need to maintain context information, rule learning is performed in
two steps. Rules are first generated locally based on differences between fraudulent
and normal behavior for each account, then they are combined in a rule selection
step.
4.1.1. Rule generation DC-1 uses the RL program (Clearwater and Provost
1990; Provost and Aronis 1996) to generate indicators of fraud in the form of
classification rules. Similar to other MetaDENDRAL-style rule learners (Buchanan
and Mitchell 1978; Segal and Etzioni 1994; Webb 1995), RL performs a general-
to-specific search of the space of conjunctive rules. This type of rule-space search
is described in detail by Webb (Webb 1995). In DC-1, RL uses a beam search for
rules with certainty factors above a user-defined threshold. The certainty factor we
used for these runs was a simple frequency-based probability estimate, corrected
for small samples (Quinlan 1987). In order to deal with the very large numbers of
values for some of the attributes used to describe calls (more than 10,000 values in
total), RL also used breadth-first marker propagation techniques, so that the algo-
rithm's time complexity does not depend on the number of attribute values (Aronis
and Provost 1997). (RL's time complexity is linear in the number of attributes and
the number of examples.)
The call data are organized by account, with each call record labeled as fraudulent
or legitimate. When RL is applied to an account's calls it produces a set of rules that
serve to distinguish, within that account, the fraudulent calls from the legitimate
calls. As an example, the following rule would be a relatively good indicator of
Certainty
This rule denotes that a call placed at night from The Bronx (a Borough of New
York City) is likely to be fraudulent. The Certainty means that,
within this account, a call matching this rule has an 89% probability of being
fraudulent.
From each account, RL generates a "local" set of rules describing the fraud on
that account. Each rule is recorded along with the account from which it was
generated. The covering heuristic typically used by RL was disabled, so that all
of the (maximally general) rules with probability estimates above threshold would
be generated. This option was chosen because rule generation in DC-1 is local and
decisions about coverage should not be made locally. The next step, rule selection,
incorporates information about coverage and generality.
4.1.2. Rule Selection After all accounts have been processed, a rule selection
step is performed. The purpose of this step is to derive a set of rules that will serve
as fraud indicators.
A rule selection step is necessary because the rule generation step typically generates
tens of thousands of rules in total, most of which are specific only to single
accounts. The system cannot know a priori how general each rule will be. For
example, from one account RL may generate the rule:
Given:
Accts: set of all accounts
Rules: set of all fraud rules generated from Accts
Number of rules required to cover each account.
Taccts : (parameter) Number of accounts in which a rule must have been found.
Output:
S: Set of selected rules.
1. /* Initialization */
2.
3. for (a 2 Accts) do
4. for (r 2 Rules) do
5. Number of accounts in which r occurs */
of accounts generating r */
7. end for
8. /* Set up Occur and AcctsGen */
9. for (a 2 Accts) do
set of rules generated from a;
11. for (r 2 Ra ) do
12. Occur[r] := Occur[r]
13. add a to AcctsGen[r];
14. end for; end for
15. /* Cover Accts with Rules */
16. for (a 2 Accts) do
17. list of rules generated from a;
18. sort Ra by Occur;
19. while (Cover[a] ! T rules ) do
20. r := highest-occurrence rule from Ra
21. Remove r from Ra
22. if
23. add r to
24. for (a2 2 AcctsGen[r]) do
25.
26. end for; end if
27. end while; end for

Figure

4. Rule selection and covering algorithm used by DC-1
This rule is probably specific only to the account from which it was generated,
but there is no a priori way to know a rule's generality in the generation step,
which processes a single account at a time. If this rule is found in ("covers") many
accounts, it is probably worth using; if it was only found in a single account, it is
probably not a general indicator of fraudulent behavior. Even if the same account
ADAPTIVE FRAUD DETECTION 11
is cloned again, it will not be defrauded in exactly the same way. Note that DC-1's
notion of coverage is slightly different from the standard notion, because of the
multiple levels of granularity; in particular, DC-1 selects a set of rules that covers
the accounts, as opposed to typical classifier learning, in which a set of rules is
selected that covers the examples (in this case, the calls).
The rule selection algorithm is given in Figure 4. The algorithm identifies a small
set of general rules that cover the accounts. Two parameters control the algorithm.
T rules is a threshold on the number of rules required to "cover" each account. In
the selection process, if an account has already been covered by T rules rules, it will
not be examined. T accts is the number of accounts a rule must have been found in
(i.e., mined from) in order to be selected at all.
For each account, the list of rules generated by that account is sorted by the
frequency of occurrence in the entire account set. The highest frequency unchosen
rule is selected. An account is skipped if it is already sufficiently covered. The
resulting set of rules is used in construction of monitors.
4.2. Constructing Profiling Monitors
Rule learning produces a set of rules characterizing changes that commonly occur
when an account is cloned. These rules are not universal: for a given account, we
do not know to what extent that account's normal behavior already satisfies the
rule. For example, the "Bronx-at-night" rule, mentioned above, may be very useful
for someone living in Hartford, Connecticut, but it may cause many false alarms
on a subscriber living in the Bronx. A fraud detection system should distinguish
the two. In the latter case the system should inhibit the rule from firing, or at least
require a much higher level of activation.
Sensitivity to different users is accomplished by converting the rules into profiling
monitors. Each monitor has a Profiling step and a Use step. Prior to being used on
an account, each monitor profiles the account. In the Profiling step, the monitor is
applied to a segment of an account's typical (non-fraud) usage in order to measure
the account's normal activity. Statistics from this profiling period are saved with
the account. In the monitor's Use phase, the monitor processes a single account-day
at a time. The monitor references the normalcy measures calculated in Profiling,
and generates a numeric value describing how abnormal 2 the current account-day
is.
Profiling monitors are created by the monitor constructor, which employs a set of
templates. The templates are instantiated by rule conditions. Given a set of rules
and a set of templates, the constructor generates a monitor from each rule-template
pair. Two monitor templates are shown in Figure 5. At the top is a template that
creates threshold monitors. Such a monitor yields a binary feature corresponding
to whether the user's behavior was above threshold for the given day. The bottom
of

Figure

5 shows a template for a standard deviation monitor. In the Profiling
period, such monitors measure the mean (-) and standard deviation (oe) of typical
usage; in the Use period, they produce a continuous output representing how many
standard deviations above the mean an account-day is.
Threshold monitors
ffl Given: Rule conditions from a fraud rule.
ffl Profiling: On a daily basis, count the number of calls that satisfy rule con-
ditions. Keep track of the maximum as daily threshold.
ffl Use: Given an account-day, let C be the set of all calls on that day that
satisfy rule conditions.
daily threshold
Standard deviation monitors
ffl Given: Rule conditions from a fraud rule.
ffl Profiling: On a daily basis, sum the airtime of all calls satisfying rule con-
ditions. At the end of the training period, record the mean (-) and standard
deviation (oe) of the samples.
ffl Use: Given an account-day, let C be the set of all calls on that day that
satisfy rule conditions. Let
Call2C
airtime(Call)
Airtime if
Airtime\Gamma-
oe if Airtime ? -

Figure

5. Two templates for creating monitors from rules. A threshold monitor learns a threshold
on maximum use and outputs a 1 whenever daily usage exceeds the threshold. A standard
deviation monitor outputs the number of standard deviations over the mean profiled usage.
As an example, assume the Bronx-at-night rule mentioned earlier was used with
the template shown in Figure 5b. Assume that, on some account, the subscriber
called from the Bronx an average of five minutes per night with a standard deviation
of two minutes. At the end of the Profiling step, the monitor would store the values
(5,2) with that account. In Use on that account, if the monitor processed a day
USED
USED
Std. Deviation
Mean
Std. Deviation
Mean
Use
Profiling Use Profiling

Figure

6. Using mean and standard deviation in profiling.
containing three minutes of airtime from the Bronx at night, the monitor would emit
a zero; if the monitor saw 15 minutes, it would emit (15 5. This value
denotes that the account is five standard deviations above its average (profiled)
usage level.
Standard deviation monitors are sensitive both to the expected amount of activity
on an account and to the expected daily variation of that activity. Figure 6 illustrates
the difference, showing one monitor applied to two accounts. The account on
the left has low variation in the Profiling period so its standard deviation is lower.
Consequently the erratic behavior in its Use period will produce large values from
the monitor. The account on the right has the same mean but exhibits much larger
variation in Profiling period, so the standard deviation is higher. The variations in
behavior during the Use period will not produce large values from the monitor.
4.3. Combining Evidence from the Monitors
The third stage of detector construction learns how to combine evidence from the
monitors generated by the previous stage. For this stage, the outputs of the monitors
are used as features to a standard learning program. Training is done on
account data, and monitors evaluate one entire account-day at a time. In training,
the monitors' outputs are presented along with the desired output (the account-
day's correct class: fraud or non-fraud). The evidence combination weights the
monitor outputs and learns a threshold on the sum so that alarms may be issued
with high confidence.
Many training methods for evidence combining are possible. We chose a simple
Linear Threshold Unit (LTU) (Nilsson 1965; Young 1984) for the experiments reported
below. An LTU is simple and fast, and enables a good first-order judgment
of the features' worth.
14 FAWCETT AND PROVOST
A feature selection process is used to reduce the number of monitors in the final
detector. Some of the rules do not perform well when used in monitors, and some
monitors overlap in their fraud detection coverage. We therefore employ a sequential
forward selection process (Kittler 1986) which chooses a small set of useful monitors.
Empirically, this simplifies the final detector and increases its accuracy.
The final output of DC-1 is a detector that profiles each user's behavior based on
several indicators, and produces an alarm if there is sufficient evidence of fraudulent
activity. Figure 3 shows an example of a simple detector evaluating an account-day.
Before being used on an account, the monitors each profile the account. They
are applied to a profiling segment (thirty days in our experiments) during which
they measure unfrauded usage. In our study, these initial thirty account-days were
guaranteed free of fraud, but were not otherwise guaranteed to be typical. From
this initial profiling period, each monitor measures a characteristic level of activity.
4.4. Summary of the Detector Construction Process
In sum, DC-1 begins by examining the call records of defrauded accounts. The call
records are expressed in terms of a set of base level attributes with thousands of
possible values. From these data, the system generates rules characterizing fraudulent
calls within accounts, then selects a smaller set of general rules as indicators
of fraudulent behavior.
These rules are used as the basis from which to build a set of profiling monitors,
each of which examines behavior based on one learned rule. A monitor learns the
typical behavior of an account by scanning an initial sequence of the account's
calls (its "profiling period") and saving some statistics. Subsequently, the monitor
examines chunks of calls (in our experiments, account-days). The monitor
subsequently examines each chunk (day) of each account's behavior and outputs a
number indicating how far away from normal the behavior is.
In order to construct a high-confidence detector, DC-1 must then learn to combine
the outputs of the monitors effectively. To do this, it trains a classifier on a sample
of account-days. Each account-day is a training instance expressed as a vector of
monitor outputs for that day, and labelled as either containing fraud or not. After
training, the system has a classifier that is able to combine the monitors effectively.
The final output of the system is a set of monitors and a trained classifier for
combining their outputs. In order to be applied to a new account, the monitors
must see a profiling period of days from that account.
The next sections describe our cellular call data and the experiments we have
performed on the system.
5. The Data
The call data used for this study are records of cellular calls placed over four months
by users in the New York City area-an area with high levels of fraud. Each call
is described by thirty-one attributes, such as the phone number of the caller, the
duration of the call, the geographical origin and destination of the call, and any
long-distance carrier used. Because of security considerations, we are unable to
disclose all the features used in the system.
To these thirty-one attributes are added several derived attributes that incorporate
knowledge we judged to be potentially useful. One such attribute is a categorical
TIME-OF-DAY variable representing the time segment of the day in which a
call is placed. Its values are MORNING, AFTERNOON, TWILIGHT, EVENING
and NIGHT. Another derived attribute is TO-PAYPHONE, a binary flag indicating
whether the call terminated at a payphone. Note that any number of additional
features could be added to encode relevant domain knowledge.
Each call is also give a class label of legitimate or fraudulent. This is done by
cross referencing a database of all calls that were credited as being fraudulent for
the same time period.
5.1. Data Cleaning
Like all real-world data, our cellular call data contain errors and noise from various
sources. For example, calls are marked as fraudulent based on a process called
block crediting. In this process, the customer and the carrier representative together
establish the range of dates during which the fraud occurred, and the calls within
the range are credited. The customer is usually not asked about each individual
call. The block crediting process uses heuristics to discard obvious non-fraudulent
calls from the credited block, but these heuristics are fallible. Also, if there is
a disagreement about the fraud span, the customer service representative usually
concedes, in the customer's favor, to a wider date span. Any erroneously credited
calls constitute noise in our data.
Because of these noise sources, we cleaned the data in several ways.
ffl Each account's calls were scanned automatically to eliminate credited calls to
numbers that had been called outside of the credited block. In other words, the
program looked for credited calls made to a phone number that also had been
called by the legitimate subscriber; in this case, the crediting may have been a
mistake, so the call is discarded completely.
ffl An account-day was classified as fraudulent only if five or more minutes of
fraudulent usage occurred. Days including one to four minutes of fraudulent
usage were discarded. This policy eliminated a small number of "gray area"
account-days probably mislabelled due to small amounts of noise. For example,
the database of credits due to fraud occasionally included credits for other
reasons, such as wrong numbers.
ffl Within any time period there will be fraud that has not yet been detected.
We assumed that some genuinely fraudulent calls would not be marked as such
because of this time lag. We attempted to minimize this noise by delaying the
data retrieval by two weeks.
ffl In preliminary experiments, rule learning uncovered some unusual attribute
values (e.g., that seemed to be very strong indicators of fraud.
Discussions with the database providers led us to conclude that these suspicious
values were artifacts of the crediting process: in some circumstances, crediting
would erase or replace certain fields. Because the values appeared primarily
in credited records, data mining had extracted them as high-confidence fraud
rules. We found five or six such misleading values and eliminated from the
database all records containing them.
In addition, the start times of calls had been recorded in local time with respect
to the switch of origin. The calls were normalized to Greenwich Mean Time for
chronological sorting.
5.2. Data Selection
The call data were separated carefully into several partitions for rule learning,
account profiling, and detector training and testing. Once the monitors are created
and the accounts profiled, the system transforms raw call data into a series of
account-days using the outputs of the monitors as features.
Rule learning and selection used 879 accounts comprising over 500,000 calls.
About 3600 accounts were selected for profiling, training, and testing. The only
condition used to select these 3600 accounts was that they be guaranteed to have at
least thirty fraud-free days of usage before any fraudulent usage. The initial thirty
days of each account were used for profiling. The remaining days of usage were used
to generate approximately 96,000 account-days. Using randomly selected accounts,
we generated sets of 10,000 account-days for training and 5000 account-days for
testing. Training and testing accounts were distinct, so their account-days were
not mixed between training and testing. 3 Each set of account-days was chosen to
comprise 20% fraud and 80% non-fraud days.
6. Experiments and Evaluation
Rule learning generated 3630 rules, each of which applied to two or more accounts.
The rule selection process, in which rules are chosen in order of maximum account
coverage, yielded a smaller set of 99 rules sufficient to cover the accounts. Each of
the 99 rules was used to instantiate two monitor templates, yielding 198 monitors.
The final feature selection step reduced this to eleven monitors, with which the
experiments were performed.
6.1. The Importance of Error Cost
In this domain, different types of errors have different costs. A realistic evaluation
should take misclassification costs into account. Classification accuracy, a standard
metric within machine learning and data mining, is not sufficient.
A false positive error (a false alarm) corresponds to wrongly deciding that a
customer has been cloned. Based on the cost of a fraud analyst's time, we estimate
the cost of a false positive error to be about $5. A false negative error corresponds

Table

1. Accuracies and costs of various detectors.
Detector Accuracy (%) Cost (US$) Accuracy at cost (%)
Alarm on All 20 20000 20
Alarm on None 80 18111 \Sigma 961 80
Collisions Velocities
High Usage 88 \Sigma :7 6938 \Sigma 470 85 \Sigma 1:7
State of the Art (SOTA) 90 \Sigma :4 6557 \Sigma 541 88 \Sigma :9
detector 92 \Sigma :5 5403 \Sigma 507 91 \Sigma :8
to letting a frauded account-day go undetected. Rather than using a uniform cost
for all false negatives, we estimated a false negative to cost $.40 per minute of
fraudulent airtime used on that account-day. This figure is based on the proportion
of usage in local and non-local ("roaming") markets, and their corresponding costs.
Because LTU training methods try to minimize errors but not error costs, we
employed a second step in training. After training, the LTU's threshold is adjusted
to yield minimum error cost on the training set. This adjustment is done by moving
the decision threshold from -1 to +1 in increments of .01 and computing the resulting
error cost. After the minimum cost on training data is found, the threshold is
clamped and the testing data are evaluated.
6.2. DC-1 Compared with Alternative Detection Strategies

Table

1 shows a summary of results of DC-1 compared against other detectors. The
name of each detector is shown in the left-most column. Classification accuracy averages
and standard deviations are shown in the second column. The third column
shows the mean and standard deviations of test set costs. The right-most column,
"Accuracy at cost," is the corresponding classification accuracy of the detector
when the threshold is set to yield lowest-cost classifications.
Each detector was run ten times on randomly selected training and testing ac-
counts. For comparison, we evaluated DC-1 along with other detection strategies.
ffl Alarm on All represents the policy of alarming on every account every day.
The opposite strategy, Alarm on None, represents the policy of allowing fraud
to go completely unchecked. The latter corresponds to the maximum likelihood
accuracy classification. Note that the cost of Alarm on None does not take
into account the inhibitory effect of fraud detection, without which fraud levels
would likely continue to rise.
ffl Collisions and Velocities is a detector using collision and velocity checks
described in Section 2.2.2. DC-1 was used to learn a threshold on the number of
collision and velocity alarms necessary to generate a fraud alarm. It is surprising
that Collisions and Velocity Checks, commonly thought to be reliable indicators
of cloning, performed poorly in our experiments.
The performance of collisions and velocity checks was originally worse than
reported here because of false alarms. Manual inspection of false alarms revealed
a few synchronization problems; for example, some apparent collisions were
caused when a call was dropped then quickly re-established in a neighboring
cell whose clock did not agree with the first cell's. Some such conditions could
be caught easily, so we patched the detection algorithms to check for them. The
results in this paper are for the improved detectors.
Investigation of confusion matrices revealed that the collision and velocity check
detectors' errors were due almost entirely to false negatives. In other words,
when the detectors fired they were accurate, but many fraud days never exhibited
a collision or velocity check.
ffl Some fraud analysts believe that cloning fraud is usually accompanied by large
jumps in account usage, and sophisticated mining of fraud indicators is probably
unnecessary since most fraud could be caught by looking for sudden increases
in usage. We created the High Usage detector to test this hypothesis. It
generates alarms based only on amount of usage. It is essentially a standard
deviation monitor (see Figure 5) whose rule conditions are always satisfied. The
threshold of this detector was found empirically from training data.
Note that the evaluation of cost for the high usage detector may be overly
optimistic, due to inadequacies in our cost model. In particular, a trained high
usage detector learns to optimally "skim the cream," without regard to the fact
that the errors it makes will involve annoying the best customers. In these cases,
the cost of a false alarm may be much higher than the fixed cost we assigned.
ffl The Best Individual DC-1 Monitor was used as an isolated detector. This
experiment was done to determine the additional benefit of combining monitors.
The best individual monitor was generated from the rule:
Rule learning had discovered (in 119 accounts) that the sudden appearance of
evening calls, in accounts that did not normally make them, was coincident with
cloning fraud. The relatively high accuracy of this one monitor reveals that this
is a valuable fraud indicator.
Our TIME-OF-DAY attribute has five possible values: MORNING, AFTER-
NOON, TWILIGHT, EVENING and NIGHT. Although EVENING is by far
the most frequent value implicated in fraud, rule learning generated fraud rules
involving each of these values. This suggests that any time-of-day change in a
subscriber's normal behavior may be indicative of fraud, though the other shifts
may not be predictive enough to use in a fraud monitor.
ffl The DC-1 detector incorporates all the monitors chosen by feature selection.
We used the weight learning method described earlier to determine the weights
for evidence combining.
ADAPTIVE FRAUD DETECTION 19
ffl The Of The Art") detector incorporates thirteen hand-crafted
profiling methods that were the best individual detectors identified in a previous
study. Each method profiles an account in a different way and produces a
separate alarm. Weights for combining SOTA's alarms were determined by our
weight-tuning algorithm. Details on the detectors comprising are given
in

Appendix

A.
The results in Table 1 demonstrate that DC-1 performs quite well. In fact, DC-
outperforms in terms of both accuracy and cost. 4 In our experiments,
lowest cost classification occurred at an accuracy somewhat lower than optimal. In
other words, some classification accuracy can be sacrificed to decrease cost. More
sophisticated methods could be used to produce cost sensitive classifiers, which
would probably produce better results.
Finally, the monitors of SOTA and DC-1 were combined into a hybrid detector.
The resulting detector exhibits no increase in classification
accuracy, but does show a slight improvement in fraud detection cost.
In this work we have dealt with differing costs of false positive and false negative
errors. However, we have still glossed over some complexity. For a given account,
the only false negative fraud days that incur cost to the company are those prior to
the first true positive alarm. After the fraud is detected, it is terminated. Thus, our
analysis overestimates the costs slightly; a more thorough analysis would eliminate
such days from the computation.
6.3. Fraudulent Call Classifiers
Section 4.1 asserted that account context is important in the rule learning step:
a global example set taken from all accounts would lose information about each
account's normal behavior. In order to test this hypothesis, two such call classifiers
were created from global example sets.
Applying standard classification algorithms to the call data was difficult for several
reasons. First, the description language is very detailed because many thousands
of attribute values appear in the data. Because of this, the volume of data
necessary was relatively large for desktop platforms; the use of fewer than 100,000
examples led to erratic classification behavior. Furthermore, in order to achieve high
coverage of calls, massively disjunctive concept descriptions had to be learned-
there were no simple classifiers that performed well.
After trying many approaches, we chose two classifiers learned in the following
manner. A set of 100,000 training examples was sampled from the accounts set
aside for rule learning. The sample was random, but stratified to achieve a 50/50
class distribution. RL was applied to these data, with parameters set so that it
learned massively disjunctive rule sets. The two classifiers, CC 1054 and CC 1861,
comprise 1054 and 1861 rules, respectively. 5 Each of these rule sets covered around
60% of the calls in a 92212 example test set, with an accuracy of about 75% on the
calls it covered. We observed a clear and graceful tradeoff between accuracy and
coverage: as the coverage increased, the accuracy decreased.

Table

2. A comparison of DC-1 to two global call classifiers
Detector Accuracy (%) Cost (US$) Accuracy at cost (%)
detector 92 \Sigma :5 5403 \Sigma 507 91 \Sigma :8
In order to achieve a competitive comparison, the call classifiers were then given
the advantage of profiling and monitoring. A standard deviation airtime monitor
was created from each. Specifically, instead of instantiating the monitor template
with a single rule, the template was instantiated with the entire classifier. The
resulting monitor profiled each account's normal behavior with respect to the clas-
sifier's output. The call classifier monitor learns if a particular customer's legitimate
behavior typically triggers a positive output. Furthermore, each call classifier
monitor was inserted into the DC-1 weight-training framework in order to find an
"optimal" output threshold for accuracy maximization or cost minimization.
The results are shown in Table 2. The two call classifiers perform similarly, and
outperforms both by a considerable margin. Indeed, we were surprised that
the the call classifier monitors perform as well as they do.
6.4. Shifting Distributions of Fraud
As discussed in Section 2.3, a fraud detection system should be able to adapt to
shifting fraud distributions. For example, each month the relative amount of fraud
changes slightly, and it is rarely possible to predict the level of fraud far into the
future. Thus, unless it is adaptive, even a well-tuned detection system will begin
to lose its edge.
To illustrate this point, we simulated the effects of changing fraud distributions
on detector performance. One DC-1 detector was trained on a fixed distribution of
account-days (80% non-fraud, 20% fraud) and tested against several other distributions
(ranging from 75% to 99% non-fraud account-days), to simulate a well-tuned
but non-adaptive detection system. Another DC-1 detector was allowed to adapt
to each distribution; its LTU threshold was re-trained for minimum predicted cost
on a training set with the new distribution.
The results are shown in Figure 7. The X-axis is the percentage of non-fraud
account-days, and the Y-axis is the cost per account day. This figure shows that
the second detector, which is allowed to adjust itself to each new distribution, is
consistently more cost effective than the fixed detector. This difference increases
as the testing distribution becomes more skewed from the distribution upon which
the fixed detector was trained.
We close by noting that these experiments illustrated changes in fraud detection
performance with respect to fairly simple changes in fraud distribution (changing
ADAPTIVE FRAUD DETECTION 210.20.611.4
Cost
Percentage of non-fraud
Trained for 80/20
Adapted to each distribution

Figure

7. The effects of changing fraud distributions
fraud volume). The patterns of fraud also change, particularly in reponse to detection
methods. Thus the ability to use data mining to discover new patterns
amplifies the benefit of adaptability.
6.5. Discussion
It is difficult to evaluate DC-1 against existing expert systems for fraud detection.
Fraud detection departments carefully protect information about how much fraud
they have and how effective their detection strategies are. Likewise, vendors of fraud
detection systems protect details of their systems' operation that may constitute
trade secrets. Little performance data on fielded systems are available, and what
data do exist are insufficient for careful evaluation.
For these reasons, we evaluated DC-1 against individual known fraud detection
techniques, as well as against a collection of techniques representing the state of
the art as we understand it. Results in the previous sections show that the DC-
detector performs better than the high-usage alarm and the collision/velocity
alarm. DC-1 also out-performs the detector, consisting of a collection of the
best fraud detection techniques known to us, trained by DC-1's evidence combining
method.
22 FAWCETT AND PROVOST
DC-1's framework has three main components, and is more complex than other
approaches. Our experiments were designed not only to evaluate the overall performance
of the system, but also to analyze the contribution of the individual
components. In particular:
ffl The High Usage detector profiles with respect to undifferentiated account usage.
Comparison with DC-1's performance demonstrates the benefit of using rule
learning to uncover specific indicators of fraudulent calls.
ffl The Call Classifier detectors represent rule learning without the benefit of account
context. Comparison with DC-1's performance demonstrates the value
of DC-1's rule generation step, which does preserve account context.
ffl Comparison of DC-1 with the single best individual DC-1 monitor demonstrates
the benefit of combining evidence from multiple monitors.
ffl Experiments with shifting fraud distributions indicate the benefit of making
evidence combination sensitive to fraud distributions.
In each of these cases, the composite DC-1 system out-performed the detector in
which a significant piece was missing. These results suggest that each component
contributes critically to the performance of the entire detector.
Our system uses a Linear Threshold Unit to combine evidence from the monitors.
Other methods of evidence combination are possible. We performed some experiments
with multi-layer neural networks, but found that adding units to a hidden
layer did not improve performance. These networks produced higher training accu-
racies, but lower accuracies on the test sets; such behavior is symptomatic of data
overfitting. Additional experimentation might yield better-performing networks,
but we have not pursued this. It is possible that, because the neural network is
applied far along in the fraud detection process as a means of combining evidence,
non-linear combinations of the evidence contribute little to fraud detection performance

By increasing the expressiveness of the language used for inductive learning, it
may be possible to learn more general patterns of fraudulent behavior, reducing
the need for highly disjunctive class descriptions. The caveats mentioned earlier
about the inability to procure background knowledge for context notwithstanding,
it may be possible to provide additional context by linking call and account data to
geographic and demographic databases. Furthermore, it may be possible to learn
context in one stage, and then apply relational learning approaches in a later stage.
One such possibility is to make use of inductive learners that learn concept descriptions
in first-order logic, such as FOIL (Quinlan 1990) or ILP methods (D-zeroski
1996). Given the appropriate context information, it is possible that more expressive
methods could learn general relational rules such as the following, which
indicates fraud when a user calls from an abnormal location.
Another possibility is to use a learner that forms propositional rules, but can take
advantage of relational background knowledge in the process (Aronis, Provost, and
Buchanan 1996). We have not explored the use of relational learning to any great
extent. We have linked the data to knowledge about the geographic locations of
telephone numbers (Aronis and Provost 1997), which does produce useful generalizations
of the areas to which calls are placed.
Finally, it is important to point out additional limitations to the evaluation of
learned classifiers on real-world problems. For the work described in this paper, we
made use of techniques to deal with skewed class distributions, viz., stratified sam-
pling, and to deal with nonuniform misclassification costs, viz., empirical threshold
adjustment. We also ensured that our evaluation include cost effectiveness in addition
to accuracy. However, because of the complexity and dynamics of real-world
domains, determining precisely the target cost and class distributions is often im-
possible. As noted above, levels of fraud and costs change monthly. It is important
to be able to compare competing classification methods under imprecision in these
distributions. The investigation and design of such techniques is an important area
for future research (Provost and Fawcett 1997).
7. Related Work
Fraud detection is related to intrusion detection, a field of computer security concerned
with detecting attacks on computers and computer networks (Frank 1994;
Sundaram 1996; Kumar 1995). Many forms of intrusion are instances of superimposition
fraud, and thus candidates for systems built with our framework. Within
the intrusion detection community, anomaly detection systems try to characterize
behavior of individual users in order to detect intrusions on that user's account
via anomalies in behavior. Existing anomaly detection systems typically examine
audit trails of user activities, which fill the same roll as cellular call records in DC-
1. DC-1 would be considered a statistical anomaly detection system. Sundaram
An open issue with statistical approaches in particular, and anomaly
detection systems in general, is the selection of measures to monitor and
the choice of metrics. It is not known exactly what the subset of all possible
measures that accurately predicts intrusive activities is.
DC-1's framework directly addresses this problem. Its rule learning step examines
large numbers of fraud episodes in order to generate features (measures) that
distinguish fraudulent from legitimate behavior. To the best of our knowledge, no
published anomaly detection system does this.
Calling card fraud and credit card fraud are other forms of superimposition fraud.
A system built by Yuhas (1993, 1995) examines a set of records representing calling-
card validation queries to identify queries corresponding to fraudulent card usage.
Yuhas transformed the problem into a two-class discrimination task and trained
several machine learning models on the data. All three models had comparable
performance on the test sets. His system must be provided with appropriate fea-
tures; it neither mines the data for fraud indicators nor measures typical customer
usage. Stolfo et al. (1997) address credit card fraud detection. They also transform
the problem into a two-class discrimination task, and do not use customer-specific
information in detection. Specifically, they predict whether individual transactions
are fraudulent. In our domain, we found that DC-1 significantly improves detection
performance over systems that use transaction classification alone. It would
be interesting to determine whether a system like DC-1 could improve performance
on these other superimposition fraud tasks.
Ezawa and Norton (1995, 1996) have addressed the problem of uncollectible debt
in telecommunications services. They use a goal-directed Bayesian network for clas-
sification, which distinguishes customers who are likely to default from those who
are not. As with our work, Ezawa and Norton's work faces problems with unequal
error costs and skewed class distributions. However, it does not face the problem
of determining the typical behavior of individual customers so as to recognize superimposed
fraudulent behavior. Mining the data to derive profiling features is not
necessary.
Because fraud happens over time, methods that deal with time series are relevant
to this work. However, traditional time series analysis (Chatfield 1984; Farnum
and Stanton 1989) in statistics strives either to characterize an entire time series
or to forecast future events in the series. Neither ability is directly useful to fraud
detection.
Hidden Markov Models (Rabiner and Juang 1986; Smyth 1994) are concerned
with distinguishing recurring sequences of states and the transitions between them.
However, fraud detection usually only deals with two states (the "frauded" and
"un-frauded" states) with a single transition between them. Yuhas (1995) mentions
the possibility of recognizing "at home" and "travel" states in order to distinguish
frauded states more effectively. This differentiation could be useful for reducing
false alarms. We are aware of no work pursuing this idea.
8. Conclusion
The detection of cellular cloning fraud is a relatively young field. Fraud behavior
changes frequently as bandits adapt to detection techniques, and fraud detection
systems should be adaptive as well. However, in order to build usage monitors we
must know which aspects of customers' behavior to profile. Historically, determining
such aspects has involved a good deal of manual work, hypothesizing useful
features, building monitors and testing them. Determining how to combine them
involves much trial-and-error as well.
We have presented and demonstrated a framework that automates the process of
generating fraud detectors. This framework is not specific to cloning fraud, but may
be applied to superimposition fraud problems in any domain. Prime candidates are
toll fraud, computer intrusion and credit-card fraud. For example, in credit-card
fraud, data mining may identify locations that arise as new hot-beds of fraud.
The constructor would then incorporate monitors that notice if customers begin to
charge more than they usually do from these specific locations.
Even with relatively simple components, DC-1 is able to exploit mined data to
produce a detector whose performance exceeds that of the state-of-the-art. The
system took several person-months to build; the DC-1 detector took several
CPU-hours. Furthermore, DC-1 can be retrained at any time as necessitated by
the changing environment.
Such adaptability is beneficial in many ways. It can save effort in time-consuming
manual feature identification and detector tuning. It can save on monetary losses
that would occur during the manual identification and tuning process. It can save on
less quantifiable damage done due to higher fraud, such as lower customer opinion
(or even customer churn). Finally, it can act to prevent fraud; a system that quickly
adapts to new patterns will be avoided by bandits in favor of easier prey.

Acknowledgments

This work was sponsored by NYNEX Science and Technology. The views and
conclusions in this paper are those of the authors and do not represent official
policy.
We thank Nicholas Arcuri and the Fraud Control Department at Bell Atlantic
NYNEX Mobile for many useful discussions about cellular fraud and its detection.
We also thank Usama Fayyad, Andrea Danyluk and our anonymous referees for
comments on drafts.
In developing DC-1 we made extensive use of many freely-available software pack-
ages. We wish to thank the generous authors, developers and maintainers of the following
software: The Perl programming language and many of its user-contributed
modules, Donald Tveter's Backprop program, numerous GNU packages including
Emacs and GCC, the GMT geographic information system, Gnuplot and the
processing system.


Appendix


State of the Art (SOTA) detector
The Of The Art") detector incorporates thirteen profiling methods.
Each method profiles an account in a different way and produces a separate alarm.
Some of the monitors were designed by hand, but those that employ weights used
DC-1's weight tuning methods. Specifically, SOTA contains the following monitors:
ffl Two collision detectors, which scan for call collisions of greater than
and
ffl Two velocity detectors, using velocity thresholds of 400 and 600 miles per hour,
respectively.
ffl Three "dialed digits" monitors. We created a dialed digit database as follows.
We scanned through accounts reserved for rule learning and recorded how many
26 FAWCETT AND PROVOST
distinct accounts called a given number both legitimately and in a fraud period.
A phone number was discarded if any legitimate subscriber called it; otherwise,
a count was saved of the number of times it was called from a cloned phone.
Because we did not know an ideal threshold on the number of "hits" required,
we created three monitors each with a different threshold.
ffl Two daily standard deviation usage monitors. One counted the number of calls
on that account-day, one measured total airtime on that account-day.
ffl Four "bad cellsite" indicators. It is commonly believed that certain cellsites
are the locus for higher than average amounts of fraud, so calls originating
from those cellsites might be suspicious. To test this strategy, we tallied the
frauded accounts calling each of the cellsites in our region, then computed the
percentage of frauded accounts using each cellsite. The twenty worst cellsites
were extracted from this list. Using this cellsite list, we created four detectors
that counted hits to these "bad cellsites" each in a different way.
Notes
1. In fact, because many cellular phones belong to large corporate accounts, often even basic user
information such as home town and work location is unavailable.
2. Technically, the numeric value only describes how much above normal the account is. Behavior
levels below normal are not considered.
3. If account-days from a single account appear in both training and testing sets, the performance
evaluation can be deceptively optimistic. Fraudulent behavior within a specific cloning episode
is more similar than fraudulent behavior between episodes. When deployed, the monitors will
be used to search for previously unseen cloning episodes.
4. Earlier work (Fawcett and Provost 1996) reported a higher accuracy for SOTA than is shown
here. Further development of SOTA revealed that some of its component methods, developed
in a prior study, had been built from account data that overlapped data used to test the
methods. When a strict separation was enforced, performance declined slightly to the
figures shown here.
5. To learn CC 1861 (1054) RL tried to cover the example set with rules each of which covered
at least 50 (100) examples and had a Laplace estimate greater than or equal to 0.95, using a
beam width of 5000.



--R

Increasing the efficiency of data mining algorithms with breadth-first marker propagation
Exploiting background knowledge in automated discovery.

The analysis of time series: An introduction (third edition).


Inductive logic programming and knowledge discovery in databases.



Quantitative forecasting methods.
Combining data mining and machine learning for effective user profiling.


Feature selection and extraction.


edu/pub/COAST/kumar-phd-intdet
Learning machines.
Scaling up inductive learning with massive parallelism.
Analysis and visualization of classifier performance: Comparison under imprecise class and cost distributions.
Learning logical definitions from relations.
Generating production rules from decision trees.
IEEE ASSP Magazine 3 (1)

Learning decision lists using homogeneous rules.
Hidden markov models for fault detection in dynamic systems.

JAM: Java agents for meta-learning over distributed databases


OPUS: An efficient admissible algorithm for unordered search.
Recursive estimation and time-series analysis



Foster Provost has been a researcher in machine learning and data mining at NYNEX Science and Technology since
--TR

--CTR
Tom E. Fawcett , Foster Provost, Fraud detection, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Jiawei Han , Russ B. Altman , Vipin Kumar , Heikki Mannila , Daryl Pregibon, Emerging scientific applications in data mining, Communications of the ACM, v.45 n.8, August 2002
Zhaohui Zheng , Xiaoyun Wu , Rohini Srihari, Feature selection for text categorization on imbalanced data, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
Taeho Jo , Nathalie Japkowicz, Class imbalances versus small disjuncts, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
Padhraic Smyth, Task and method selection: selection of tasks, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Signature-Based Methods for Data Streams, Data Mining and Knowledge Discovery, v.5 n.3, p.167-182, July 2001
Tom Fawcett , Peter A. Flach, A response to Webb and Ting's on the application of ROC analysis to predict classification performance under varying class distributions, Machine Learning, v.58 n.1, p.33-38, January 2005
Saharon Rosset , Uzi Murad , Einat Neumann , Yizhak Idan , Gadi Pinkas, Discovery of fraud rules for telecommunicationschallenges and solutions, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.409-413, August 15-18, 1999, San Diego, California, United States
Tom E. Fawcett, Industry: adaptive fraud detection, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Kenji Yamanishi , Jun-ichi Takeuchi, Discovering outlier filtering rules from unlabeled data: combining a supervised learner with an unsupervised learner, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.389-394, August 26-29, 2001, San Francisco, California
Wenke Lee , Salvatore J. Stolfo , Kui W. Mok, Mining in a data-flow environment: experience in network intrusion detection, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.114-124, August 15-18, 1999, San Diego, California, United States
Chris Drummond , Robert C. Holte, Explicitly representing expected cost: an alternative to ROC representation, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.198-207, August 20-23, 2000, Boston, Massachusetts, United States
Nilesh Dalvi , Pedro Domingos , Mausam , Sumit Sanghai , Deepak Verma, Adversarial classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
David Jensen , Matthew Rattigan , Hannah Blau, Information awareness: a prospective technical assessment, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
data mining approach for database intrusion detection, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Jennifer Neville , zgr imek , David Jensen , John Komoroske , Kelly Palmer , Henry Goldberg, Using relational knowledge discovery to prevent securities fraud, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Michael H. Cahill , Diane Lambert , Jos C. Pinheiro , Don X. Sun, Detecting fraud in the real world, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Albert Orriols , Ester Bernad-Mansilla, The class imbalance problem in learning classifier systems: a preliminary study, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C.
Foster Provost , Ron Kohavi, Guest Editors Introduction: On Applied Research in MachineLearning, Machine Learning, v.30 n.2-3, p.127-132, Feb./ March, 1998
Hang , Honghua Dai, Applying both positive and negative selection to supervised learning for anomaly detection, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
Tom Fawcett, ROC graphs with instance-varying costs, Pattern Recognition Letters, v.27 n.8, p.882-891, June 2006
F. Bonchi , F. Giannotti , G. Mainetto , D. Pedreschi, A classification-based methodology for planning audit strategies in fraud detection, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.175-184, August 15-18, 1999, San Diego, California, United States
Tom Fawcett , Foster Provost, Activity monitoring: noticing interesting changes in behavior, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.53-62, August 15-18, 1999, San Diego, California, United States
Mukund Narasimhan , Paul Viola , Michael Shilman, Online decoding of Markov models under latency constraints, Proceedings of the 23rd international conference on Machine learning, p.657-664, June 25-29, 2006, Pittsburgh, Pennsylvania
Wenke Lee , Salvatore J. Stolfo , Kui W. Mok, Adaptive Intrusion Detection: A Data Mining Approach, Artificial Intelligence Review, v.14 n.6, p.533-567, December 1, 2000
Fabrizio Angiulli , Stefano Basta , Clara Pizzuti, Detection and prediction of distance-based outliers, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Fisher , Daryl Pregibon , Anne Rogers, Hancock: a language for extracting signatures from data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.9-17, August 20-23, 2000, Boston, Massachusetts, United States
Tom Fawcett, An introduction to ROC analysis, Pattern Recognition Letters, v.27 n.8, p.861-874, June 2006
Information mining platforms: an infrastructure for KDD rapid deployment, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.327-331, August 15-18, 1999, San Diego, California, United States
Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jrg Sander, LOF: identifying density-based local outliers, ACM SIGMOD Record, v.29 n.2, p.93-104, June 2000
Rakesh Agrawal , Sridhar Rajagopalan , Ramakrishnan Srikant , Yirong Xu, Mining newsgroups using networks arising from social behavior, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
P. Janeja , Vijayalakshmi Atluri , Ahmed Gomaa , Nabil Adam , Christof Bornhoevd , Tao Lin, DM-AMS: employing data mining techniques for alert management, Proceedings of the 2005 national conference on Digital government research, May 15-18, 2005, Atlanta, Georgia
Perlich , Foster Provost, Distribution-based aggregation for relational learning with identifier attributes, Machine Learning, v.62 n.1-2, p.65-105, February  2006
Jennifer Neville , David Jensen, Relational Dependency Networks, The Journal of Machine Learning Research, 8, p.653-692, 5/1/2007
Gang Wu , Edward Y. Chang, KBA: Kernel Boundary Alignment Considering Imbalanced Data Distribution, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.786-795, June 2005
Tamas Abraham, Event sequence mining to develop profiles for computer forensic investigation purposes, Proceedings of the 2006 Australasian workshops on Grid computing and e-research, p.145-153, January 16-19, 2006, Hobart, Tasmania, Australia
Miroslav Kubat , Robert C. Holte , Stan Matwin, Machine Learning for the Detection of Oil Spills in Satellite Radar Images, Machine Learning, v.30 n.2-3, p.195-215, Feb./ March, 1998
Weng-Keen Wong , Andrew Moore , Gregory Cooper , Michael Wagner, What's Strange About Recent Events (WSARE): An Algorithm for the Early Detection of Disease Outbreaks, The Journal of Machine Learning Research, 6, p.1961-1998, 12/1/2005
Fisher , Daryl Pregibon , Anne Rogers , Frederick Smith, Hancock: A language for analyzing transactional data streams, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.301-338, March 2004
Klaus Julisch , Marc Dacier, Mining intrusion detection alarms for actionable knowledge, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Ting Liu , Andrew W. Moore , Alexander Gray, New Algorithms for Efficient High-Dimensional Nonparametric Classification, The Journal of Machine Learning Research, 7, p.1135-1158, 12/1/2006
Chris Drummond , Robert C. Holte, Cost curves: An improved method for visualizing classifier performance, Machine Learning, v.65 n.1, p.95-130, October   2006
Clifton Phua , Damminda Alahakoon , Vincent Lee, Minority report in fraud detection: classification of skewed data, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
Maarten Van Someren , Tanja Urbani, Applications of machine learning: matching problems to tasks and methods, The Knowledge Engineering Review, v.20 n.4, p.363-402, December 2005
Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001
Sofus A. Macskassy , Foster Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study, The Journal of Machine Learning Research, 8, p.935-983, 5/1/2007
Gediminas Adomavicius , Alexander Tuzhilin, Expert-Driven Validation of Rule-Based User Models in Personalization Applications, Data Mining and Knowledge Discovery, v.5 n.1-2, p.33-58, January-April 2001
Yongwon Lee , Bruce G. Buchanan , John M. Aronis, Knowledge-Based Learning in Exploratory Science: Learning Rules to Predict Rodent Carcinogenicity, Machine Learning, v.30 n.2-3, p.217-240, Feb./ March, 1998
Klaus Julisch, Clustering intrusion detection alarms to support root cause analysis, ACM Transactions on Information and System Security (TISSEC), v.6 n.4, p.443-471, November
Foster Provost , Venkateswarlu Kolluri, Data mining tasks and methods: scalability, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
Predrag Radivojac , Nitesh V. Chawla , A. Keith Dunker , Zoran Obradovic, Classification and knowledge discovery in protein databases, Journal of Biomedical Informatics, v.37 n.4, p.224-239, August 2004
M. A. Maloof , P. Langley , T. O. Binford , R. Nevatia , S. Sage, Improved Rooftop Detection in Aerial Images with Machine Learning, Machine Learning, v.53 n.1-2, p.157-191, October-November
Jianping Fan , Hangzai Luo , Jing Xiao , Lide Wu, Semantic video classification and feature subset selection under context and concept uncertainty, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA
Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999
Darse Billings , Lourdes Pea , Jonathan Schaeffer , Duane Szafron, Learning to play strong poker, Machines that learn to play games, Nova Science Publishers, Inc., Commack, NY, 2001
rule learning;constructive induction;intrusion detection;profiling;fraud detection;applications