TravelSky Technology(China Airline): Predicting Airfare Price by SVM
We
were faced with the large dataset with no explicit links between records,
making it a very challenging task to analyze price changes of an individual
round-trip.
It
was much more practical to develop a model that generalizes the properties of
all records in the dataset, and to train a SVM as a binary pricing classifier
to distinguish between ”expensive” and ”cheap” of all tickets (transaction
records) processed.
Part I. General
Introduction
Travelsky
technologies is one of the largest global distribution system in the
travel/tourism industry: it sells tickets for all airlines (also hotels) and
processes millions billable transactions per month.
Project Goals
1
Construct and train a general classifier so that it can distinguish between
expensive and cheap tickets.
2.
Use this classifier to predict the prices of future tickets.
3.
Determine which factors have the greatest impact on price by analyzing the
trained classifier.
Exploratory data
analysis
Extent
of the dataset: billion records, 132.2
GiB (uncompressed) , hundreds departure
airports, hundreds destinations, hundreds routes, hundreds airlines.
Lots
of fields: “Buy” date: When was this
price current? “Fly” date: When does the flight leave? Price. Cabin class Economy/Business/First (98%
economy tickets) . Booking class A-Z …
Airline The airline selling the ticket. some data looks like a time series,
tickets are linked over time
Classification &
Prediction methods
Implemented
two different classifiers: Support
vector machine (SVM), L1- regularized
linear regression. Both are convex
minimization problems that can be solved online by employing the stochastic
gradient descent (SGD) method.
SVM: binary linear classifier. Goal: Find
maximum-margin hyperplane that divides the points with label y “+1” from those
with label y “-1”.
Training:
Generate training label yi for i-th data point xi. Choose hyperplane parameters so the margin is
maximal and the training data is still correctly classified.
Preprocessing
For
each route r, calculate the arithmetic mean (and standard deviation) of the
price over all tickets.
Assign
labels: Label +: “Above mean price for this route”. Label -: “Below mean price for this route” .Only
store mean/std-dev, do not actually store labels.
Feature Selection
Extract
features from plaintext records (x).
Each
plaintext record is transformed into a 990-dimensional vector.
Each
dimension contains a numerical value corresponding to a feature such as: Number of days between “Buy” and “Fly” dates,
Week of day (for all dates) , Is the day on a weekend (for all dates), Dates
isMonday, isWeekend, isWinter, weekOfYear, . . . .
Each
dimension is normalized to zero mean and unit variance (per route r).
Part II. More Detailed
Descriptions of Our Model
Classification methods
In
order to identify which records represent cheap tickets and which records have
traits identifying them as expensive tickets, a classifier able to distinguish
between ”expensive” and ”cheap” records is necessary.
It
should be possible to train such a classifier on all records at once,
identifying the features making a record cheaper or more expensive than other
records. As some routes are more expensive than others, it does not make sense
to include the route as a feature, but rather normalize prices per route. This enables
comparison of prices across all routes without simply marking all records of a
particular route as expensive. Each record is then labeled according to the
normalized price.
In
short, a record for a particular route is labeled as ”expensive” (+1) if its
price is higher than the average price of all records for that specific route.
Otherwise it is labeled as ”cheap” (-1).
After
training the classifier, it should be able to predict a label from and assign this label to a new record with an
unknown price. As the route of the new record is known, a numerical minimal or
maximal price (the afore-mentioned average price per route) can be directly
inferred from the predicted label.
Additionally,
the model parameters of the trained classifier should contain information on
how much each feature contributes to a record being cheap or expensive.
Online algorithms for
classification
Due
to the large amount of data, algorithms using more than a constant amount of
memory are not suitable. Two algorithms were implemented, one for online
support vector machines and the other for online-regularized logistic
regression. This allows efficient training of the classifier on a parallel
system with limited memory.
Some
definitions and terminology as they are used in the following sections:
Xi
Each
data point Xi represents the features of
a single record Ri and is also called the feature
vector
for record Ri
Each
component contains information about a single aspect of the record Ri . The
contents are described previously are derived from the fields of Ri
Yi
Each
label yi represents the label (classification) of a single record Ri, with two
values: ”expensive” (+1), “cheap” (-1).
Record
Ri always consists of a pair (Xi Yi) , both values are known for trading
dataset.
For new data points Xi,
the value of the labels Yi is initially unknown, and is the result of the
classification/prediction. A label has only two possible values: −1 and 1.
W
The
weight vector w is the model parameter of the classifier to be estimated and is
initially
unknown.
In both classifiers discussed below, w has the same number of dimensions as a
data
point
Xi and determines the effect each value in Xi has on the classification result.
Feature
vector generation
For each record, a feature vector consisting of 990
features was created. Before normalization, each entry was set to either 1.0
(boolean true), 0 (boolean false) or a value associated with a numerical field
in the record.
The feature vector represents each record as a 990-dimensional
vector.
Some
examples of features, and record fields utilized:
Dates Request Date, Departure Date, Return Date
Date differences Return-Departure Date,
Departure-Request Date
Categorical values Passenger Type, Airline
Numerical values Number of passengers, Number of hops
Sequences of categorical values Cabin Classes, Booking
Classes, Availabilities
Sequences of numerical values Flight numbers
Feature
vector normalization
As with price normalization, each of the 990 features
fm was normalized in two steps. In a first MapReduce job, the arithmetic means
µfm and standard deviations σfm were calculated using the same methods as for
price normalization and subsequently stored to disk.
All following MapReduce jobs loaded the 990 means and
standard deviations from disk and calculated the normalized feature vector x 0
i on-the-fly by calculating the standard score of each feature fm: f 0 m = fm −
µfm σfm , m ∈
1, . . . , 990
Stochastic gradient
descent (SGD)
Given
a convex set S and a convex function f, we can estimate the parameter w in min
f(w)
is of the form f(w) = Pn
a
single observed data point from the dataset. Finding w is done iteratively, by
using one random
sample
data point from the dataset per iteration. For regularization, w ∈ S needs to be ensured,
thus
a projection onto S is necessary.
Let
w0 ∈ S be the starting value. Then each iteration t consists of the
update step
t=1
ft(w). Usually, each summand ft represents the loss function for
wt+1
= P rojS(wt − ηt∇ft(wt))
where
P rojS is a projection onto the set S, ηt is the current step size (learning
rate), and ∇ft is the
gradient
of f approximated at the sample data point for iteration t.
It
is possible to only use a subsample of the full dataset if the data points used
for training are picked
at
random from the dataset. Training can then either be halted after a fixed
number of iterations or as soon as sufficient accuracy is achieved.
