# DISCOVERING MALICIOUS SIGNATURES IN SOFTWARE FROM STRUCTURAL INTERACTIONS

###### Abstract

Malware represents a significant security concern in today’s digital
landscape, as it can destroy or disable operating systems, steal sensitive
user information, and occupy valuable disk space. However, current malware
detection methods, such as static-based and dynamic-based approaches, struggle
to identify newly developed (“zero-day”) malware and are limited by customized
virtual machine (VM) environments. To overcome these limitations, we propose a
novel malware detection approach that leverages deep learning, mathematical
techniques, and network science. Our approach focuses on static and dynamic
analysis and utilizes the Low-Level Virtual Machine (LLVM) to profile
applications within a complex network. The generated network topologies are
input into the GraphSAGE architecture to efficiently distinguish between
benign and malicious software applications, with the operation names denoted
as node features. Importantly, the GraphSAGE models analyze the network’s
topological geometry to make predictions, enabling them to detect state-of-
the-art malware and prevent potential damage during execution in a VM. To
evaluate our approach, we conduct a study on a dataset comprising source code
from 24,376 applications, specifically written in C/C++, sourced directly from
widely-recognized malware and various types of benign software. The results
show a high detection performance with an Area Under the Receiver Operating
Characteristic Curve (AUROC) of 99.85%. Our approach marks a substantial
improvement in malware detection, providing a notably more accurate and
efficient solution when compared to current state-of-the-art malware detection
methods.

Index Terms—  Malware detection, Graph neural network, Complex network

##  1 Introduction

Fig. 1: Overview of the Proposed Method: (a) C/C++ files are transformed into
LLVM IR and converted into a weighted complex network by capturing operations
from the source code. The generated networks are passed into an embedding
layer to compute node features, resulting in an $n\times N$ matrix
representation. (b) Leveraging these matrices, the GraphSAGE architecture
extracts information from the neighbors of each node. Lastly, the
classification layer predicts whether the file is malicious or benign.

Malware refers to malicious software designed to cause damage to the Internet
and computers. Malware could intrude into PC, collect user’s personal
information and sensitive data, and gain administrative privileges on a host,
trigger havoc on PC’s operating system, and lead to the loss of billions of
dollars. For instance, malware-based cyber-attacks can target industrial
control systems (ICS) to slow down industrial processes or destroy critical
components, causing significant financial damages, safety, and life-
threatening events [1].

To mitigate such catastrophic events, researchers have dedicated decades of
work to malware detection. Mainstream solutions have emerged, namely static
analysis and dynamic analysis. Static analysis involves scanning software
binary byte-streams to generate signatures, like printable strings, n-grams,
and instructions [2]. Kim et al. proposed a multimodal deep learning scheme to
detect Android mobile malware by analyzing various factors such as strings,
method APIs, permissions, components, and environment [3]. Despite their high
accuracy for specific malware types, static analysis methods struggle with
“zero-day” malware, where the signatures have changed due to updates [4].

On the other hand, dynamic analysis can handle the latest malware by
monitoring their behavior during execution and regaining control of infected
systems. Recently, researchers have applied deep learning models to dynamic
analysis. Classic convolutional- (CNN) and recurrent- neural network (RNN) can
learn features from the sequential data extracted from software [5] and image
data [6]. For instance, Zhang et al. [7] designed a CNN-LSTM model to analyze
features from each API call for detecting malicious files. Furthermore, deep
learning-based approaches can detect intrusion attempts [8] and anomalies in
network traffic [9]. Despite overcoming static analysis limitations, deep
learning based dynamic approaches’ inherent black-box nature hinders the
interpretability of its feature attribution [10].

To address the challenges posed by both static and dynamic analysis, this
paper introduces a robust and mathematically grounded deep learning framework
for malware detection called the Malware Graph Network (MGN). MGN involves
adopting a Low-Level Virtual Machine (LLVM) intermediate representation (IR)
compiler to transform suspected malware software into a complex weighted
network, where nodes represent instructions, and edges indicate data and
control dependencies among LLVM instructions. The weights associated with the
network can represent data sizes or latency values. By utilizing this compiler
approach, executing suspected applications on the virtual machine is avoided.
This complex network representation allows capturing the spatiotemporal
characteristics of software and interpreting the differences between benign
and malicious files by revealing the intrinsic correlations between APIs and
the software’s instructions. To process these intricate network structures
that have been extracted, we incorporate a GNN-based deep learning
architecture called GraphSAGE into MGN for malware classification. This
approach surpasses state-of-the-art baselines, such as N-gram Analysis [11],
Grayscale Image Analysis [12, 13], Operation Code Analysis [14], and Byte File
Analysis [15, 7].

##  2 METHOD

To create a robust and interpretable malware detection strategy capable of
effectively handling malware evolution and obfuscation, we present MGN,
illustrated in Figure 1. MGN comprises two primary components: (1) utilizing a
compiler approach built on LLVM to compile source code into a sophisticated
network representation and (2) feeding the constructed networks into a GNN-
based deep learning architecture for the purpose of malware detection. This
two-part framework forms the foundation of our proposed approach for enhanced
malware detection.

###  2.1 Compiler Analysis and Network Modeling

In this section, we leverage code compilation tools to transform source code
into a graph representation. Specifically, we transform input applications
into a corresponding dependency graph [16] through LLVM compiler and
transparent by introducing IR as a common model for analysis, transformation,
and synthesis. The LLVM is a compiler framework which makes program analysis
lifelong. The resulting graph encompasses the structure of the graph itself,
which includes nodes and the connections between them, as well as node
features. For each graph, its node features are derived from the operation
names present in the code, such as “store”, “getelementptr”, and “load”.

We first run the applications with representative inputs to collect dynamic
LLVM IR traces to resolve dynamic memory dependencies. Next, we analyze the
traces to figure out whether source registers of the current instruction
depend on destination registers of the previous instructions. If such
dependencies exist, we add edges between these two nodes to represent
dependencies. Then, these instructions are profiled to get the precise data
sizes as edge weights in the graph. For example, a part of dynamic traces has
been shown as follows: $\%3$ = sub $\%1$, $\%2$; $\%5$ = sub $\%3$, $\%4$. The
second instruction has the register $\%3$, which depends on the destination
register $\%3$ of the first instruction.

Hence, we find a dependency between the last two instructions and an edge is
inserted between these two nodes. After following these compiled steps, a
suspected application is profiled into a complex network that will be analyzed
in the following section to predict whether this application is benign or
malicious. Figure 1 shows the steps of dynamically profiling applications into
graphs.

After the transformation of the suspected files into graph representations, we
encode the node features, represented by operation names, into one-hot
vectors. Each graph’s node features can be denoted by a matrix of dimensions
$n\times N$, where $n$ signifies the number of distinct operation names
present in a given graph and $N$ denotes a constant that represents the union
of operation names across the entire dataset. Moreover, each graph is assigned
a label indicating whether it represents malware or benign software.

###  2.2 GraphSAGE Neural Network Modeling

In this study, we choose GraphSAGE to analyze the preprocessed features
represented as complex networks. GraphSAGE can efficiently analyze large graph
structures, where many software source codes often consist of numerous nodes
[17]. Furthermore, GraphSAGE employs inductive learning and ensures excellent
generalizability, which allows it to generate embeddings for previously unseen
nodes. This character can be highly effective for classification tasks.
Instead of relying on manually crafted features to describe malware, this
property becomes invaluable in malware detection, given the frequent emergence
of new malware variants and families.

Through an in-depth examination of GraphSAGE’s structure and the graphs
representing malware and benign software, we have devised our deep learning
architecture. It comprises of the following components: an embedding layer, 6
GraphSAGE layers, 1 global pooling layer, and 1 output layer. In the input
layer, we incorporate node features and edge indices, where the node features
denote operation name for the instruction and the edge indices represent edge
lists. The GraphSAGE employs the mean aggregator as its initial step, which
calculates the mean of node features within the neighborhood. Subsequently,
the number of neighbors sampled in each layer depends on the average degree of
nodes.

While GraphSAGE layer achieved the most exceptional performance in graph
neural network model, the number of SAGE layers and the choice of activation
functions have a significant impact on the final model’s performance. This was
evident in our ablation experiments.

##  3 EVALUATION

Following the same training and testing strategy with all the baselines, our
model is trained and evaluated on 24,376 applications (12,815 malware and
11,561 benign software). All these applications are source code gathered from
real-world programs. For malware representation, we select a diverse array of
types, including Spyware, Botnet, Trojan, among others. As for benign
software, we choose programs from gaming, system development, application
software, mobile apps, and artificial intelligence to guarantee that our
dataset comprehensively includes various domains. For every software, we
identify their main execution functions as data points. These are then
compiled using our toolset and transformed into a graph, serving as individual
data entries. The entire dataset is randomly split into $80\%$ as training set
and the remaining $20\%$ is testing set. The model performances are assessed
via the AUROC and accuracy (ACC).

Table 1: Comparison of malware detection results using different
hyperparameters and settings. The best results are highlighted in red.

SAGE EL LRelu ACC AUROC F1-score 4layers ✗ ✗ 96.29% 99.38% 96.81% ✓ ✓ 97.45%
99.72% 97.76% ✓ ✗ 97.17% 99.57% 97.54% 6layers ✗ ✗ 95.79% 99.33% 96.08% ✓ ✓
98.55% 99.85% 98.72% ✓ ✗ 97.45% 99.73% 97.78% 8layers ✗ ✗ 96.51% 99.61% 96.96%
✓ ✓ 98.18% 99.79% 98.40% ✓ ✗ 97.45% 99.59% 97.78% 10layers ✗ ✗ 95.65% 99.37%
95.95% ✓ ✓ 96.03% 99.46% 96.30% ✓ ✗ 95.82% 99.40% 96.11%

###  3.1 Ablation study

To gain a comprehensive understanding of the significance of different
components in our malware detection model and to determine the most effective
architecture, we performed a systematic ablation study, varying
hyperparameters and settings. Table 1 presents a summary of our findings. In
the table, “EL” and “LReLU” refer to the embedding layer and Leaky-ReLU
activation function, respectively. The presence of a ✓ indicates that the
embedding layer or Leaky-ReLU was utilized, while a ✗ denotes their absence
(for activation function, we use ReLU instead). The first column represents
the different numbers of SAGE layers chosen for the ablation study.

In this study, we introduce an fully-connected embedding layer before the GNN
architecture, which plays an essential role in capturing initial feature
representations. The absence of this embedding layer results in a performance
drop of approximately $2.76\%$. Furthermore, we incorporate 6 SAGE layers,
each connected to a hidden layer with 128 hidden units. We choose Leaky-ReLU
as the activation function for each SAGE layer.

###  3.2 Experiment results

The comparison results for malware detection are presented in Table 2 and Fig.
2. In this section, we select state-of-the-art deep learning-based malware
detection models as our baselines, as referenced in previous works [12, 18,
19, 7, 20, 15]. All these models are trained and tested on our malware dataset
to ensure a fair comparison.

As indicated in Table 2, our MGN demonstrates remarkable performance in
classifying malware and outperforms all other models in terms of both ACC and
AUROC. To provide a visual representation of these comparisons, Fig. 2 panels
(a) and (b) display quantitative results for ACC and AUROC, respectively.
Panels (c) and (d) respectively present the learning curve comparisons between
MGN and selected baselines (specifically, ARI-LSTM, EE-DNN, and H-CNN, which
utilize N-gram, Bytes, and Opcode as features, respectively). Hence, our
findings suggest that network-based features used in MGN can significantly
enhance the performance of distinguishing between malware and benign software
within the context of deep learning. For comprehensive information, please
refer to Table 2.

Table 3 presents a detailed breakdown of various malware types, along with
their respective performance metrics obtained through our method and ARI-LSTM
[18]. We choose to include ARI-LSTM in this table because of its notable
accuracy, as well as the similarity of its features to our node-based
features.

Table 2: Comparison of malware detection results (ACC and AUROC) across
different models. The best two results are highlighted in red and blue,
respectively.

Baselines Features ACC AUROC CNN [12] Image 93.09% 98.31% ARI-LSTM [18] N-gram
98.28% 99.5% Bi-GRU-CNN [15] Bytes 96.36% 99.43% EE-DNN [19] Bytes 97.45%
99.72% SA-CNN [7] Opcode 97.38% 99.66% H-CNN [20] Opcode 98.18% 99.74% MGN
Networks 98.55% 99.85%

Fig. 2: Performance comparison of MGN against baselines on the test set,
showing (a) ACC and (b) AUROC; (c) ACC and (d) AUROC comparisons of MGN
against baselines at different epochs. Table 3: Classification accuracy
comparison between our model (MGN) and the state-of-the-art model (ARI-LSTM)
across various malware types. The best results are highlighted in red.

Malware Samples Text Samples MGN ARI-LSTM Spyware 4757 950 98.32% 98.11%
Botnet 1548 300 98.67% 97.00% Trojan 4645 900 99.11% 98.89% Rootkit 3048 600
98.33% 97.67% Trojan-Backdoor 3097 600 98.50% 97.83% Worm 1548 300 100.00%
99.00% Ransomware 900 180 100.00% 100.00% Injection 900 180 98.89% 98.33%
Mixed 3933 750 100.00% 99.60%

Fig. 3: Two-dimensional t-SNE visualization of network topological features.
Blue circles and red squares represent benign and malicious networks,
respectively.

###  3.3 Interpretability Analysis

Figure 3 provides a clear two-dimensional t-SNE visualization, illustrating
the clustering behavior of network topological features which includes the
number of nodes and edges, average closeness-, average degree-, and average
betweenness-centrality.These features are derived from the network
representations of source files. We randomly selected around 900 instances
from both the benign and malicious network classes for visual clarity. This
visualization effectively highlights the capability of our proposed methods in
discerning the inherent topological distinctions between benign and malicious
codes. Consequently, it enhances the interpretability of our approach.

##  4 CONCLUSION

In this paper, we propose an innovative deep learning framework known as MGN,
designed for malware detection. MGN utilizes a graph-based representation and
harnesses the power of the LLVM compiler to capture intricate software
dependencies, resulting in the creation of a complex network. This network is
then subjected to classification using a Graph Neural Network (GNN)
architecture, significantly improving the precision of distinguishing between
benign and malicious programs. Through careful design of the model
architecture, MGN demonstrates superior performance compared to state-of-the-
art baselines, achieving higher accuracy and AUROC measurements. It is
important to highlight that MGN’s ability to transform software into the
network’s topology enhances its interpretability, setting it apart from other
baseline approaches.

## References

  * [1] Scott Steele Buchanan,  “Cyber-attacks to industrial control systems since stuxnet: A systematic review,”  2022\.
  * [2] Mamoru Mimura and Ryo Ito,  “Applying nlp techniques to malware detection in a practical environment,”  International Journal of Information Security, vol. 21, no. 2, pp. 279–291, 2022.
  * [3] TaeGuen Kim, BooJoong Kang, Mina Rho, Sakir Sezer, and Eul Gyu Im,  “A multimodal deep learning method for android malware detection using various features,”  IEEE Transactions on Information Forensics and Security, vol. 14, no. 3, pp. 773–788, 2018.
  * [4] Rajesh Kumar and Geetha Subbiah,  “Zero-day malware detection and effective malware analysis using shapley ensemble boosting and bagging approach,”  Sensors, vol. 22, no. 7, pp. 2798, 2022.
  * [5] Weizhong Qiang, Lin Yang, and Hai Jin,  “Efficient and robust malware detection based on control flow traces using deep neural networks,”  Computers & Security, p. 102871, 2022.
  * [6] Charlotte Pelletier, Geoffrey I Webb, and François Petitjean,  “Deep learning for the classification of sentinel-2 image time series,”  in IGARSS 2019-2019 IEEE International Geoscience and Remote Sensing Symposium. IEEE, 2019, pp. 461–464.
  * [7] Bin Zhang, Wentao Xiao, Xi Xiao, Arun Kumar Sangaiah, Weizhe Zhang, and Jiajia Zhang,  “Ransomware classification using patch-based cnn and self-attention network on embedded n-grams of opcodes,”  Future Generation Computer Systems, vol. 110, pp. 708–720, 2020\.
  * [8] Mario Di Mauro, Giovanni Galatro, and Antonio Liotta,  “Experimental review of neural-based approaches for network intrusion management,”  IEEE Transactions on Network and Service Management, vol. 17, no. 4, pp. 2480–2495, 2020.
  * [9] Shi Dong, Yuanjun Xia, and Tao Peng,  “Network abnormal traffic detection model based on semi-supervised deep reinforcement learning,”  IEEE Transactions on Network and Service Management, vol. 18, no. 4, pp. 4197–4212, 2021.
  * [10] Chenzhong Yin, Phoebe Imms, Mingxi Cheng, Anar Amgalan, Nahian F Chowdhury, Roy J Massett, Nikhil N Chaudhari, Xinghe Chen, Paul M Thompson, Paul Bogdan, et al.,  “Anatomically interpretable deep learning of brain age captures domain-specific cognitive impairment,”  Proceedings of the National Academy of Sciences, vol. 120, no. 2, pp. e2214634120, 2023.
  * [11] Enmin Zhu, Jianjie Zhang, Jijie Yan, Kongyang Chen, and Chongzhi Gao,  “N-gram malgan: Evading machine learning detection via feature n-gram,”  Digital communications and networks, vol. 8, no. 4, pp. 485–491, 2022.
  * [12] Daniel Gibert, Carles Mateu, Jordi Planes, and Ramon Vicens,  “Using convolutional neural networks for classification of malware represented as images,”  Journal of Computer Virology and Hacking Techniques, vol. 15, pp. 15–28, 2019.
  * [13] Iman Almomani, Aala Alkhayer, and Walid El-Shafai,  “An automated vision-based deep learning model for efficient detection of android malware attacks,”  IEEE Access, vol. 10, pp. 2700–2720, 2022.
  * [14] Junwei Tang, Ruixuan Li, Yu Jiang, Xiwu Gu, and Yuhua Li,  “Android malware obfuscation variants detection method based on multi-granularity opcode features,”  Future Generation Computer Systems, vol. 129, pp. 141–151, 2022\.
  * [15] Rajasekhar Chaganti, Vinayakumar Ravi, and Tuan D Pham,  “Deep learning based cross architecture internet of things malware detection and classification,”  Computers & Security, vol. 120, pp. 102779, 2022.
  * [16] Yao Xiao, Yuankun Xue, Shahin Nazarian, and Paul Bogdan,  “A load balancing inspired optimization framework for exascale multicore systems a complex networks approach,”  in Proceedings of the 36th International Conference on Computer-Aided Design. IEEE Press, 2017, pp. 217–224.
  * [17] William L. Hamilton, Rex Ying, and Jure Leskovec,  “Inductive representation learning on large graphs,”  in NIPS, 2017.
  * [18] Rakshit Agrawal, Jack W Stokes, Karthik Selvaraj, and Mady Marinescu,  “Attention in recurrent neural networks for ransomware detection,”  in ICASSP 2019-2019 IEEE international conference on acoustics, speech and signal processing (ICASSP). IEEE, 2019, pp. 3222–3226.
  * [19] Daniel Gibert, Carles Mateu, and Jordi Planes,  “An end-to-end deep learning architecture for classification of malware’s binary content,”  in International Conference on Artificial Neural Networks. Springer, 2018, pp. 383–391.
  * [20] Daniel Gibert, Carles Mateu, and Jordi Planes,  “A hierarchical convolutional neural network for malware classification,”  in 2019 International joint conference on neural networks (IJCNN). IEEE, 2019, pp. 1–8.


11institutetext: Université Côte d’Azur, CNRS, I3S, UMR 7271, Sophia
Antipolis, France
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext:
Amadeus S.A.S, Sophia Antipolis, France
22email<EMAIL_ADDRESS>33institutetext: Data Science Department,
EURECOM, France
33email<EMAIL_ADDRESS>
# Multi-objective Consensus Clustering Framework for Flight Search
Recommendation

Sujoy Chatterjee 1122 Nicolas Pasquier 11 Simon Nanty 22 Maria A. Zuluaga 2233

###### Abstract

In the travel industry, online customers book their travel itinerary according
to several features, like cost and duration of the travel or the quality of
amenities. To provide personalized recommendations for travel searches, an
appropriate segmentation of customers is required. Clustering ensemble
approaches were developed to overcome well-known problems of classical
clustering approaches, that each rely on a different theoretical model and can
thus identify in the data space only clusters corresponding to this model.
Clustering ensemble approaches combine multiple clustering results, each from
a different algorithmic configuration, for generating more robust consensus
clusters corresponding to agreements between initial clusters. We present a
new clustering ensemble multi-objective optimization-based framework developed
for analyzing Amadeus customer search data and improve personalized
recommendations. This framework optimizes diversity in the clustering ensemble
search space and automatically determines an appropriate number of clusters
without requiring user’s input. Experimental results compare the efficiency of
this approach with other existing approaches on Amadeus customer search data
in terms of internal (Adjusted Rand Index) and external (Amadeus business
metric) validations.

###### Keywords:

Clustering Ensemble Multi-objective optimization.

##  1 Introduction

In the travel industry, the volume of sales mainly relates two factors like
click rate (i.e., inquiry rate) and translation of it to conversion rate.
Multiple factors can hinder the customers from purchasing a ticket in spite of
searching for a flight itinerary. The click to conversation rate can be
increased if certain number of offers can be recommended to a certain set of
customers. Therefore, personalized recommendation based on similarity of
customers can be very effective to improve the business strategy of the travel
company. The customers can be segregated depending on various features like
days of advance flight booking, distance covered during the travel, number of
their children. Hence, clustering algorithms have a major role in order to
segment the customers in a better way.

Clustering algorithms [10] are used in travel context to find sets of
customers with similar needs and requirements, and to identify hidden
relationships between their search query. However, traditional clustering
algorithm results depend significantly on the algorithmic configuration used,
i.e., the algorithm chosen and its parameterization, and its adequacy to the
data space properties. Hence, clustering the same set of customers with
different algorithmic configurations can produce significantly different
solutions.

Figure 1: Bi-dimensional data space showing different underlying clustering
models.

Choosing an adequate algorithmic configuration, and defining the final number
of clusters as required by most existing clustering approaches, are major
practical issues when the required prior knowledge of the data space
properties is unavailable. Consider for example the bi-dimensional data space
represented in Fig. 1 that shows different sub-spaces where groups of objects
correspond to different underlying clustering models, e.g., centroid, density
or model-based. Consensus clustering approaches combine multiple clustering
results, obtained from diverse algorithmic configurations, to generate a more
robust clustering solution. By combining the results of algorithms based on
different modeling assumptions and for different parameterizations, that is
identifying agreements between these _base clusterings_ and quantifying the
weight of repetitive groups of objects among clusters, these groups of objects
can be detected. Therefore, consensus clustering, that was shown to be an
effective approach to generate quality clustering solutions [2, 16, 17], is an
interesting solution for travel context where little prior knowledge of the
evolving data space is available. However, to the best of our knowledge, no
study on the integration of consensus clustering for better personalized
recommendation in travel context was reported in the literature.

In this paper, we study the integration of consensus clustering through a
multi-objective optimization process for the clustering of flight search
queries. This process aims to optimize the selection of flight recommendations
that are returned by the Amadeus flight search engine. For that purpose, a
clustering solution is used to segment the space of customers, so that the
search engine is optimized independently for each cluster, and customers with
different needs and requirements are provided with different recommendations.
In this context, we have no prior knowledge about the data space modeling
assumptions, like data distribution or natural number of clusters, and
choosing an appropriate algorithmic configuration is an important issue. Using
classical clustering approaches requires to apply the different clustering
algorithms with different parameterizations multiple times and compute the
Amadeus business metric for each clustering solution, implying numerous time
consuming computations. This metric is the difference between the estimated
booking probability of the flight recommendations output by the search engine
before and after the optimization of the flight search engine. In order to
reduce computation cost and optimize the search space exploration, i.e., the
potential consensus clusterings, we propose a new ensemble clustering
framework.

The clustering ensemble problem is usually posed as an optimization problem
where the average similarity of consensus solution with the base clusterings
is maximized in order to obtain a better aggregation. However, since a
consensus solution can be very similar to one base clustering whereas very
distant from others, and to remove any kind of bias toward a particular
clustering solution, minimizing the standard deviation of these similarity
values is also necessary. The proposed framework uses a multi-objective
clustering ensemble approach that simultaneously optimizes two objective
functions [4]: The maximization of the similarity between the consensus
solution and the base clusterings, and the minimization of the standard
deviation of these similarities for a consensus solution. A formal proof is
provided demonstrating that the proposed approach automatically generates a
number of clusters at least as appropriate as approaches that consider only
co-occurrences of two objects in base clusters for generating a consensus
clustering. This framework integrates the ensemble clustering solution and a
mapping function to categorize a new customer in an appropriate cluster to
improve the Amadeus flight search recommendation. We present an extensive
analysis, by generating diverse sets of base clusterings from multiple
perspectives, to demonstrate how the ensemble method performs in terms of
consensus solution for customer segmentation as well as improving the Amadeus
business metric for better personalized flight recommendation. Experimental
results with comparative analysis of state-of-the-art methods show that it
performs well in majority cases. Interestingly, it automatically produces the
number of clusters which is close to the best number of cluster produced by
other methods that require to specify it each time as input.

##  2 Related Work

Over the last few years, clustering ensemble has been employed as a useful
tool to overcome the drawback of classical clustering algorithms by deriving
better clustering solutions by consensus. For a given dataset, the clustering
ensemble of base clusterings can be produced by applying the same clustering
algorithm multiple times with different parameterizations, via sub sampling,
or projection of the dataset into different sub-spaces. The primary objective
of ensemble clustering algorithms is to combine base clustering solutions in
such a way that a robust solution is generated to improve the quality of the
results compared to base clustering solutions. Different approaches have been
developed to address this topic [1, 16, 2, 7, 12, 17], and the various state-
of-the-art methods can be classified into some major categories described
hereafter.

Several approaches consider the clustering ensemble problem as a clustering of
categorical data [15]. Another category of clustering ensemble methods relies
on generating a pair-wise similarity matrix. This similarity matrix basically
considers the co-association between the objects occurring together in a same
cluster for a clustering solution [6]. An alternative method does not rely on
an object-object co-association matrix but derives a consensus solution from a
cluster association matrix [13]. Other approaches consider clustering ensemble
as a graph, or hypergraph, partitioning problem, and various graph
partitioning algorithms were proposed to obtain the consensus solutions [6,
16]. Among graph partitioning based approaches, Strehl and Ghosh modeled this
as a hypergraph partitioning problem [16] and proposed three partitioning
approaches: (i) Cluster-Based Similarity Partitioning Algorithm (CSPA), (ii)
Hypergraph Partitioning Algorithm (HGPA) and (iii) Meta Clustering Algorithm
(MCLA). Another recently proposed graph partitioning based novel consensus
function namely, weak evidence accumulation clustering (WEAC) and four
variants of it [8] outperform several other existing baseline approaches. The
first three variants are basically agglomerative methods, namely average-link
(AL), complete-link (CL) and single-link (SL). The last one GP-MGLA is a graph
partitioning based consensus method. However, in all these approaches, the
number of clusters is required as input. Among other studies, the approach
proposed in [13] effectively generates a consensus clustering with an
automatically defined number of clusters. This approach visualizes the base
clustering solution as an undirected weighted graph, and Prim’s algorithm is
adapted to make a minimum-cost spanning tree of the weighted graph. Another
approach proposed by the same authors also generates automatically the number
of clusters, but requires to specify a relaxation parameter [14].

##  3 Problem Formulation

Let $X=\\{x_{1},x_{2},\ldots,x_{p}\\}$ denote a set of $p$ customers, where
$x_{i}\in\mathbb{R}^{d}$, $d$ the number of features used to describe the
search query and $Y$ be the set of $n$ clustering algorithms. Here each
$x_{j}$ denotes the customer who searches a query for flight booking. Suppose
$C=\\{c_{1},c_{2},\ldots,c_{n}\\}$ be the set of base clustering solutions
obtained after applying $n$ clustering algorithms. Each $c_{i}$ partitions $p$
customers into $k_{i}$ clusters such that
$c_{i}=\\{x_{1}^{i},x_{2}^{i},\ldots,x_{p}^{i}\\}$, where $c_{i}$ belongs to
the set of all possible partitions of $X$ and $x_{j}^{i}$ denotes the label of
$j^{th}$ customer according to the $i^{th}$ clustering:
$x_{j}^{i}\in\\{1,2,\ldots,k_{i}\\}$ $\forall$ $j\in\\{1,2,\ldots,p\\}$. Note
that, each $c_{i}$ might comprise different number of clusters $k_{i}$. Here,
the goal is to derive the best aggregated ensemble solution from the base
clustering ones, while automatically determining the number of clusters. In
the subsequent sections of the paper we use both the terms customers and
objects in an analogous way.

##  4 Clustering Ensemble Framework

The proposed framework integrating consensus clustering optimization in
Amadeus flight search engine is presented in Fig. 2. The upper part of the
chart shows the creation of the search space, that is the Refined Ensemble
Clustering, from the dataset. The lower part of the chart shows the semi-
supervised classification process for learning a customer classification model
using consensus clusters multi-objective optimization, combined internal and
external validation, characterization of cluster segments and prediction of
recommendation class.

Figure 2: Semi-supervised classification framework for customer segmentation.

The central four phases of the proposed ensemble clustering framework are
detailed in the following subsections. Initially, the base clustering
solutions are refined by estimating the maximum number of clusters that can be
present in the base clustering. To estimate this maximum number of clusters, a
weighted co-association matrix [7] is constructed and an iterative process is
applied on this matrix (Sec 4.1). Then, based on the estimated number of
clusters, the base clustering solutions are relabeled according to a reference
clustering solution (Sec 4.2), and thus some solutions are refined.
Ultimately, we combine the original base clustering with the refined set of
clustering solutions and thus this ensures the diversity of the clustering
solutions. In this step, we use a NSGA-II based multi-objective optimization
[5] to overcome the important complexity of the search for a single solution
that is optimal in terms of all the objective functions. Hence, in terms of
multi-objective optimization, optimality is usually denoted using the concept
of Pareto optimality [5]. A Pareto optimal set basically contains multiple
solutions making a trade-off between multiple objectives. This NSGA-II method
is applied on the set of refined clustering solutions to produce a final set
of non-dominated Pareto optimal solutions (Sec 4.3). Finally, the consensus
solution is integrated in the Amadeus application using a mapping function for
classifying new customers and make the Amadeus flight search engine return
more personalized recommendations (Sec 4.4).

###  4.1 Weighted Co-association Matrix based on Confidence

In this process, instead of a classical co-association matrix, a weighted co-
association matrix is constructed based on different factors like quality of
the clustering solution and pair-wise confidence of two objects. The quality
of a solution is measured by the average similarity of this solution in terms
of Adjusted Rand Index (ARI) [9] with respect to the other solutions. To
exemplify the pair-wise confidence of the objects remaining in a same cluster,
suppose we have two clustering solutions of 9 objects with respectively 3 and
8 clusters represented as clusterings {1,1,1,2,2,2,3,3,3} and
{1,2,3,4,4,5,6,7,8}. Two objects with the same label means that they are
assigned to the same cluster in the clustering. We can see that the $4^{th}$
and $5^{th}$ objects are in the same cluster in both clustering solutions.
However, since clustering solution 2 contains a larger number of clusters, the
selection criteria for clustering is more restrictive than in solution 1. This
means that the confidence of assigning two objects to the same cluster varies
depending on the number of partitions in the clustering solution. A higher
number of partitions means a better confidence in the grouping of objects in
the same cluster. Therefore, both the quality and the number of clusters of a
clustering solution are considered to build the weighted co-association
matrix. This co-association matrix can be treated as a similarity matrix,
where the edge weights depend on these two factors, being calculated on the
basis of how many solutions agree to group two particular objects in the same
clusters. Furthermore, the quality of the solution, in terms of average
similarity with respect to the other solutions, and the confidence of two
objects being members of the same clusters are also considered. In this
process, the solutions that contain a higher number of clusters are given more
weight than clustering solutions having less number of clusters. Besides,
quality being a major issue in this purpose, therefore more weight is imposed
on the quality metric (i.e., similarity) than the number of components. The
weight due to the confidence and quality are added to compute the final weight
as their similarity.

If $n$ is the number of base clustering and label of each object $j$ is
represented by $r_{j}$, then the similarity $Sim(i,j)$ of two objects $i$ and
$j$ is represented by using Eqn. 1.

$Sim(i,j)=\sum_{p=1}^{n}(I(r_{i}=r_{j})*cluster(p))+2*w\sum_{p=1}^{n}(I(r_{i}=r_{j})*weight(p))$
(1)

Here, $I$ represents an indicator function and it returns $1$ when the two
objects have same labels, otherwise it returns 0. In this Eqn 1, $cluster(p)$
is the number of clusters in the $p^{th}$ solution and $weight(p)$ is the
weight measured by the similarity of $p^{th}$ solution with other base
clustering solutions. Due to the difference of two ranges, i.e., variation in
number of clusters and similarity value in terms of ARI, $w$ is used to make
these two ranges in the same scale. To illustrate, consider there are $n$
number of base clustering solutions. So, the similarity value of each solution
can be computed by comparing it with other $(n-1)$ solutions using ARI metric
to obtain $(n-1)$ similarity values. The average similarity value is
calculated from these $(n-1)$ similarity values. At the same time, the number
of clusters present in each clustering solution can be computed, and we thus
measure the average number of clusters that can be present in a clustering
solution. Now, $w$ is calculated by the ratio between these two values (i.e.,
ratio of average number of clusters with respect to the average similarity
value).

The similarity matrix is then transformed into a graph where objects are
vertices and edge weights can be regarded as the strength of bonding between
the objects. This similarity matrix is then transformed into an adjacency
matrix according to a threshold value, and a minimal threshold value is chosen
by $(1/t)$ fraction of maximum edge weight. In this step, the value of $t$
should be chosen in such a manner that each object cannot form a separate
cluster. In our experiments, the value of $t$ was set to 10. Then, the
threshold value is increased by a small amount, and the induced deletion of
edges produces another adjacency matrix. From this adjacency matrix, the
strongly connected components are extracted and the number of connected
components is observed. This task is repeated for a number of time while
varying the threshold value in step-wise manner (step size). This fixed step
size is chosen based on sensitivity analysis such that each object cannot
produce a separate cluster. Therefore, in every step the adjacency matrix is
formed and the number of connected components are derived. It should be noted
that the number of connected components remains fixed for certain threshold
values. Hence, obtaining the same number of connected components over
successive iterations denotes the stability of this particular number of
connected components since several clustering solutions agree regarding that
specific number of components. A sorting over the number of connected
components is performed depending on the stability values and the value is
chosen from the clustering solutions having the highest similarity value. As
earlier mentioned, the ARI [9] is used to measure the similarity of a
clustering solution with respect to the others. The final number of clusters
cannot be directly selected from the base clustering with highest average
similarity since a few clustering solutions can have a high similarity but
have a number of connected components without sufficient stability. Finally,
the initial labeling of the base clusterings are changed according to this
estimated number of clusters as described in the following subsections.

###### Theorem 4.1

The weighted co-association matrix of a clustering solution being calculated
from the numbers of co-occurrences of two objects in the same cluster, the
confidence of objects co-occurrences, and the quality of the clustering
solution, the approach will generate a number of clusters that is at least as
close to the number of clusters in the best potential agreement than the
number of clusters calculated using a simple co-association matrix where only
the numbers of co-occurrences of two objects in clusters are considered.

###### Proof

Given two clustering solutions $S_{p}$ and $S_{q}$ with $m$ and $n$ number of
clusters respectively, suppose the confidence of two objects $i$ and $j$ of
remaining in same cluster are $Conf^{m}_{S_{p}}$ and $Conf^{n}_{S_{q}}$. Now
according to the proposed model, the values in the co-association matrix not
only depend on the number of co-occurrences of two objects being in a same
cluster. Rather, along with this, the confidence of two objects and the
quality of the solutions are also considered.

Suppose $G$ and $G^{\prime}$ are the graphs constructed from normal co-
association matrix (where only count of co-occurrence of two objects lying in
same clusters is considered) and weighted co-association matrix (where co-
occurrence, confidence and quality of the clustering solutions are
considered). Accordingly to the proposed model, the confidence of two objects
remaining in the same clusters is higher for clusterings with a greater number
of partitions than for clusterings with lower number of partitions. Therefore,
we write $Conf^{m}_{S_{p}}(i,j)\geq Conf^{n}_{S_{q}}(i,j)$ where $m>n$ and if
$(i,j)\in C^{m}_{S_{p}}$ then $(i,j)\in C^{n}_{S_{q}}$. Here, $C^{m}_{S_{p}}$
and $C^{n}_{S_{q}}$ are two clusters in clustering solution $S_{p}$ and
$S_{q}$ where the two objects $i$ and $j$ are the members.

Now, the weighted co-association matrix is constructed based on confidence,
co-occurrence and quality of the clustering solution. The edges are
iteratively removed by increasing repeatedly the threshold $\delta_{t}$ by a
very small amount and observing each time the number of connected components
obtained. This number of connected components basically denotes the number of
clusters. Let $N_{e}(G)$ and $N_{e}(G^{\prime})$ be the number of edges
deleted from graphs $G$ and $G^{\prime}$ each time.

Due to the weight in $G^{\prime}$ as mentioned previously, it can be written
that, $\forall\delta_{t}$: $N^{\delta_{t}}_{e}(G)\geq
N^{\delta_{t}}_{e}(G^{\prime})$, where $N^{\delta_{t}}_{e}(G)$ and
$N^{\delta_{t}}_{e}(G^{\prime})$ denote the number of edges $e$ with same
weight $\delta_{t}$ in graph $G$ and $G^{\prime}$, respectively. Therefore,
$\forall\delta_{t}$: $N^{\delta_{t}}_{c}(G)\geq
N^{\delta_{t}}_{c}(G^{\prime})$, where $N^{\delta_{t}}_{c}(G)$ and
$N^{\delta_{t}}_{c}(G^{\prime})$ are the number of connected components
extracted from $G$ and $G^{\prime}$ for each value of threshold $\delta_{t}$.
We can thus compare the changes in the number of connected components for any
two successive iterations in these two graphs, and we have
$\frac{d(N_{c}(G^{\prime}))}{dt}\leq\frac{d(N_{c}(G))}{dt}$ for any two
successive iterations. Hence, we obtain a number of clusters that is at least
as close to the number of clusters in the best agreement than the number of
clusters obtained using a classical co-association matrix, where only the co-
occurrences of two objects in a same cluster are considered.

###  4.2 Label Transformation

Label transformation aims to unify the labels of common clusters among
different clustering solutions. Let’s consider two clustering solutions
$c_{i}=$ $\\{x_{1}^{i},$ $x_{2}^{i},$ $\ldots,$ $x_{p}^{i}\\}$ and
$c_{j}=\\{x_{1}^{j},x_{2}^{j},$ $\ldots,$ $x_{p}^{j}\\}$ that partition the
$p$ customers into $k$ and $m$ clusters respectively. Here, each $x_{p}^{i}$
denotes the labeling of the $p^{th}$ object according to $c_{i}$ clustering
solution. However, since the cluster labels are symbolic and generated by
different processes, there is no correspondence between them in the different
clusterings. In order to represent the clustering solution $c_{i}$ according
to the representation of clusters in solution $c_{j}$, the number of objects
with different labels in $c_{j}$ and $c_{i}$ is counted for each label in
$c_{i}$. Majority voting is then performed among the labels to determine the
final corresponding label in $c_{i}$.

After estimating the most likely number of clusters, the base clustering
solutions containing a higher number of clusters than the estimated value are
transformed based on a reference solution containing this estimated number of
clusters. As mentioned in the last section, the final number of cluster is
selected based on the quality of the clustering solutions (highest similarity)
of the input clustering. Hence, at least one clustering solution with that
specific number of cluster should be present. To ensure the diversity in the
search space, the original base clustering solutions are combined with the
refined set of clustering solutions. After that, the multi-objective
optimization algorithm is applied to derive the non-dominated Pareto optimal
consensus solutions.

###  4.3 Multi-objective Optimization Algorithm

In this subsection, we outline the utilization of NSGA-II [5] with an aim to
produce non-dominated near-Pareto optimal solutions. This is explained step-
wise below.

  * $\bullet$

Encoding Scheme. Here, the parameters in the search space are represented in
the form of a string (i.e., chromosome). Each chromosome represents a
clustering solution and chromosomes are encoded with integer value denoting
the class label of each object. To exemplify, a chromosome is encoded like
$\\{r_{1},r_{2},\ldots,r_{n}\\}$, where $r_{i}$ represents the class label of
$i^{th}$ object. Suppose the encodings of two chromosomes are
$\\{3,3,2,2,2,1,1,1\\}$ and $\\{2,2,3,3,3,1,1,1\\}$. Here both chromosomes
represent the same clustering solutions where objects $\\{1,2\\}$ are in the
single cluster, objects $\\{3,4,5\\}$ are in another clusters, and objects
$\\{6,7,8\\}$ are in other clusters.

  * $\bullet$

Initial Population. In the initial population, the base clustering solutions
obtained after applying different clustering algorithms are taken. In addition
to that, the clustering solutions after refinement are included in it. In this
way, the diversity of the clustering solutions is maintained. Note that, the
number of clusters in each solution of the initial population is not necessary
the same.

  * $\bullet$

Selection. Each chromosome is associated with a fitness function that
corresponds to the amount of goodness (fitness value) of the solution encoded
in it. The competent chromosomes are selected for further breeding depending
on the concept of survival of “fittest”. In this context, crowded binary
tournament is selected as the selection strategy [5].

  * $\bullet$

Crossover. Crossover is a probabilistic procedure to exchange information
between two parent chromosomes. In this paper, we use the same crossover
operation as described in [3]. Note that, in the clustering ensemble problem,
we cannot directly apply the crossover operation. The reason is that two
chromosomes can depict the same clustering solution (same fitness value) but
with different representations. Then, applying single point/multi point
crossover can distort the quality of these solutions. To explain this in more
details, suppose there are two chromosomes representing same solutions
$\\{2,2,2,1,1,3\\}$ and $\\{3,3,3,2,2,1\\}$. If single point crossover is
performed in $3^{rd}$ position, then the new chromosomes become
$\\{2,2,3,1,1,3\\}$ and $\\{3,3,2,2,2,1\\}$. Hence, the fitness values are
decreased although the original solutions were the same. To overcome this
limitation we use a bipartite graph based approach described in [3].

  * $\bullet$

Mutation. In this operation, each chromosome goes through mutation with a
slight probability $M_{p}$. Here, a small float value is added or subtracted
to the label of the chromosomes. Note that, as the label of each object is an
integer, after the mutation operation the float values obtained are converted
into the nearest integer values.

In this algorithm, the two following objective functions are simultaneously
optimized. The first is based on the ARI measure to consider the similarity of
a clustering solution with other solutions. The second is based on the
standard deviation of similarity values to identify potential bias toward a
specific clustering solution. Therefore, the objective functions are
maximization of ARI similarity values and minimization of standard deviation
among similarity values for a clustering solution with respect to other
clustering solutions.

###  4.4 Mapping Function

This application aims to classify new customers in order to customize flight
recommendations according to the customer’s class. Since no labeled data
exist, the consensus clustering solutions are used in a semi-supervised
manner. Consensus clusters, corresponding each to a customer segment, are
characterized to discriminate them, and new customers are classified by
assigning them to the cluster they are the most similar to. The
characterization of each cluster is represented as the center point of the
cluster from the sample features. That is a mean vector of feature values of
samples in the cluster. The similarity between a new customer and each cluster
is then computed based on these vectors, and the customer is assigned to the
cluster with maximal similarity.

The mapping function for clustering solution $C^{i}$ is denoted by
$f:x\mapsto\mathrm{argmin}_{\\{1\leq l\leq k\\}}(d(\gamma_{l},x))$, where $x$
is a new customer, $k$ is the number of clusters in the solution, and
$\gamma_{l}=\sum_{j=1}^{p}I(l-x^{i}_{j})x_{j}/\sum_{j=1}^{p}I(l-x^{i}_{j})$ is
the centre of cluster $l$ where $I(x)=1$ for $x=0$ and 0 $\forall
x\in\mathbb{R}^{*}$.

##  5 Experimental Design & Results

In this section, we first detail the Amadeus dataset. Then, we discuss the
analysis of the proposed model with comparison to other existing models. In
the experiments, the crossover rate is 0.9, mutation rate is 0.01 and
population size is twice the number of the base clustering solutions.

###  5.1 Dataset Description and Preprocessing

To prepare the dataset, we extracted search queries of flight bookings for
flights departing from the US during one week on January 2018. There are 9
relevant features: Distance between two airports, geography, number of
passengers, number of children, advance purchase, stay duration, day of the
week of the departure, day of the week of the return, and day of the week of
search. In “Geography” the values are 0 for domestic flights (origin and
destination are in the same country), 1 for continental flights (origin and
destination belong to the same continent), and 2 for intercontinental flights.
As this dataset contains a very large number of customers (in millions), and
as many of them have very similar feature values, the populations are divided
into some strata based on similar characteristics. Then sampling is performed
on these sub-population to generated a stratified sampling of the whole
dataset while preserving the distribution properties of the original dataset.
For example, snapshots of the distribution of the “distance between airports”
feature values in the original dataset and in sample datasets are shown in
Fig. 3. Finally, three stratified sample datasets were generated with sizes of
500, 1000 and 1500 samples.

Figure 3: Snapshot of the distribution of feature “distance between two
airports” for original dataset (Left), sample of size 1000 (Middle) and sample
of size 1500 (Right) after stratified sampling.

###  5.2 Definition of Base Clusterings

After generating the sampled datasets, the $K$-means algorithm was applied,
with feature random subspace selection, for different values of $K$ to
generate base clusterings with different numbers of clusters. Two sets of
clustering solutions were generated for each sample-sized dataset. As there is
no ground truth available for these datasets, the number of clusters parameter
$K$ was not kept fixed, but was instead varied between two to eight while
applying the clustering algorithms for generating the base clustering
solutions. In the proposed approach, there is no constraint on the $K$
parameter values that are used to generate base clusterings. As described
earlier, for each of the three sample-sized datasets, two different sets of
base clusterings were generated. The first set of base clustering solutions
was generated by applying $K$-means ten times, fixing the $K$ parameter for
five (or six) of them, and varying the $K$ parameter to generate the remaining
five (or four) clustering solutions. To generate the second set of base
clustering solutions, the value of the $K$ parameter was varied for each
$K$-means execution.

###  5.3 Experimental Results

In the first experiment, the accuracy of consensus solutions produced by
different methods is measured using the classical ARI metric. Since in this
context no ground truth is available, internal validation of the solution is
performed by comparing it to the base clustering solutions. The average
similarity of the consensus solution with the base clustering solutions
denotes the goodness of the method. We made an extensive analysis on different
datasets and compared the algorithm with other state-of-the-art methods
described in [8, 16, 13]. Since the weak evidence accumulation clustering
(WEAC) method and four of it variants [8] were reported to outperform similar
existing other approaches, we choose it as one of the methods for comparison
purpose. The performance of the proposed model were also compared with the
well-known classical methods like CSPA, HGPA, MCLA [16]. If a very limited
number of ensemble algorithms automatically estimates the number of clusters,
the promising method DiCLENS [13] was also used for comparison purposes.
Specifically, DiCLENS is the most appropriate for comparison purposes as it
produces the number of cluster automatically, similarly to the proposed
method. The results on Amadeus travel dataset for the different samples sizes
are given in Tables 2-6.

In Tables 2-6, the consensus solution produced by each algorithm is compared
with all the base clustering solutions in terms of ARI. The average similarity
obtained is reported in the tables along with the highlighting of the two best
scores. As mentioned before, we generate two sets of base clustering solutions
for each sample (as described in section 5.2). It can be realized that the
better solution can be achieved if there is a knowledge about the number of
cluster or passing $K$ value each time while executing the algorithm. In
Tables 2-3, the result obtained for the first set of base clustering on the
three sample datasets are reported and effectiveness of the method is shown.
In Tables 4-6, the results obtained for the second set of base clustering for
each sample, where each clustering solution contains different number of
clusters which makes the problem more difficult, are reported. It can be
observed that for both set of experiments, the proposed method gives
consistently good performances even though the number of clusters is not given
as input. Furthermore, the proposed method produces in several cases the same
best quality clustering solution produced by the other methods. Also, the
number of clusters predicted automatically by the proposed method is very
close to the one that generates the best ensemble among all methods. Besides,
defining the number of clusters for executing the other state-of-the-art
approaches (like WEAC, CSPA, MCLA, etc) is extremely difficult because there
is no initial knowledge of the value upto which the number of cluster should
be varied. It is seen that in majority cases the proposed approach outperforms
DiCLENS and produces equally good solutions when compared with any other
state-of-the-art approaches in terms of ARI measure. The non-dominated Pareto
front where each point corresponds to the rank-1 solution for different data
are demonstrated in Fig. 4. In these Pareto front all of the solutions are
equally good, however, the final solution is selected based on the highest
similarity with the base clusterings.

Table 1: Performance values on the base clustering with 500 samples. Here, six out of ten input clustering solutions contain five clusters and the other solutions contain three, four, six and seven clusters. Algorithm | K=3 | K=4 | K=5 | K=6 | K=7 | K=8
---|---|---|---|---|---|---
CSPA | 0.5919 | 0.5633 | 0.5539 | 0.6472 | 0.5388 | 0.4778
MCLA | 0.6117 | 0.7293 | 0.8218 | 0.7217 | 0.8066 | 0.6263
HGPA | 0.2176 | -0.0052 | 0.3447 | 0.2692 | 0.2388 | 0.0089
WEAC-SL | 0.3972 | 0.6654 | 0.8275 | 0.8056 | 0.7924 | 0.7770
WEAC-AL | 0.3637 | 0.5964 | 0.8275 | 0.8066 | 0.7917 | 0.7683
WEAC-CL | 0.6001 | 0.6654 | 0.8275 | 0.8149 | 0.8002 | 0.6913
GP-MGLA | 0.6001 | 0.6939 | 0.8275 | 0.7240 | 0.6995 | 0.6731
DiCLENS | – | – | 0.8275 | – | – | –
Proposed | – | – | 0.8275 | – | – | –

Table 2: Performance values on the base clustering with 1000 samples. Here, six out of ten input clustering solutions contain seven clusters and the other solutions contain three, four, five and six clusters. Algorithm | K=4 | K=5 | K=6 | K=7 | K=8 | K=9
---|---|---|---|---|---|---
CSPA | 0.5132 | 0.5376 | 0.7162 | 0.7044 | 0.6201 | 0.5814
MCLA | 0.6025 | 0.6139 | 0.7822 | 0.8173 | 0.8139 | 0.7455
HGPA | -0.0030 | 0.2010 | 0.3302 | 0.4642 | -0.0048 | -0.0049
WEAC-SL | 0.4768 | 0.6188 | 0.7490 | 0.8177 | 0.8140 | 0.8020
WEAC-AL | 0.3353 | 0.5507 | 0.7490 | 0.8177 | 0.8166 | 0.8043
WEAC-CL | 0.6025 | 0.7184 | 0.7490 | 0.8177 | 0.8166 | 0.7964
GP-MGLA | 0.6047 | 0.7184 | 0.7583 | 0.8177 | 0.7975 | 0.7788
DiCLENS | – | 0.7183 | – | – | – | –
Proposed | – | – |  | – | 0.8177 | –

Table 3: Performance values on the base clustering with 1500 samples. Here, six out of ten input clustering solutions contain five clusters and the other solutions contain three, four, six and seven clusters. Algorithm | K=3 | K=4 | K=5 | K=6 | K=7 | K=8
---|---|---|---|---|---|---
CSPA | 0.4464 | 0.3896 | 0.4580 | 0.4002 | 0.3865 | 0.3504
MCLA | 0.4494 | 0.5476 | 0.4962 | 0.4352 | 0.3622 | 0.3589
HGPA | -0.0009 | 0.2474 | 0.3913 | 0.3544 | 0.2761 | 0.2743
WEAC-SL | 0.4882 | 0.5584 | 0.5581 | 0.5573 | 0.5557 | 0.5531
WEAC-AL | 0.4049 | 0.5584 | 0.5567 | 0.5428 | 0.5391 | 0.5308
WEAC-CL | 0.4882 | 0.5584 | 0.5581 | 0.5442 | 0.5359 | 0.4789
GP-MGLA | 0.4882 | 0.5581 | 0.5025 | 0.5009 | 0.4866 | 0.4839
DiCLENS | – | 0.5581 | – | – | – | –
Proposed | – | 0.5584 | – | – | – | –

Table 4: Performance values on the base clustering with 500 samples. The 5 clustering solutions each contains different numbers of clusters ranging from 3 to 7. Algorithm | K=2 | K=3 | K=4 | K=5 | K=6 | K=7
---|---|---|---|---|---|---
CSPA | – | 0.5583 | 0.5644 | 0.5410 | 0.6214 | 0.5422
MCLA | – | 0.5841 | 0.7088 | 0.6480 | 0.7263 | 0.5462
HGPA | 0.2176 | 0.3487 | -0.0054 | 0.1360 | 0.6188 | 0.4892
WEAC-SL | 0.1847 | 0.3689 | 0.6283 | 0.6166 | 0.7425 | 0.7291
WEAC-AL | 0.0991 | 0.2950 | 0.5152 | 0.7525 | 0.7263 | 0.7211
WEAC-CL | 0.4638 | 0.5919 | 0.6945 | 0.7525 | 0.7263 | 0.7163
GP-MGLA | 0.4638 | 0.5947 | 0.7088 | 0.7525 | 0.7263 | 0.7113
DiCLENS | 0.1847 | – | – | – | – | –
Proposed | – | – | – | 0.7378 | – | –

Table 5: Performance values on the base clustering with 1000 samples. The 5 clustering solutions each contains different numbers of clusters ranging from 5 to 9. Algorithm | K=4 | K=5 | K=6 | K=7 | K=8 | K=9
---|---|---|---|---|---|---
CSPA | 0.5278 | 0.5472 | 0.7094 | 0.6695 | 0.5985 | 0.5967
MCLA | 0.6497 | 0.6879 | 0.7772 | 0.6712 | 0.7502 | 0.6941
HGPA | -0.0030 | 0.3478 | 0.3814 | 0.5099 | -0.0047 | -0.0047
WEAC-SL | 0.6038 | 0.6787 | 0.7722 | 0.7713 | 0.7863 | 0.7810
WEAC-AL | 0.5247 | 0.6910 | 0.7716 | 0.7713 | 0.7711 | 0.7861
WEAC-CL | 0.6485 | 0.7651 | 0.7722 | 0.7883 | 0.7882 | 0.7861
GP-MGLA | 0.6484 | 0.7683 | 0.7722 | 0.7865 | 0.7724 | 0.7555
DiCLENS | – | 0.7683 | – | – | – | –
Proposed | – | – | – | 0.7865 | – | –

Table 6: Performance values on the base clustering with 1500 samples. The 5 clustering solutions each contains different number of clusters ranging from 3 to 7. Algorithm | K=3 | K=4 | K=5 | K=6 | K=7
---|---|---|---|---|---
CSPA | 0.3978 | 0.4553 | 0.4985 | 0.4916 | 0.4262
MCLA | 0.4863 | 0.5438 | 0.5203 | 0.4957 | 0.3452
HGPA | 0.1735 | -0.0011 | -0.0015 | 0.3053 | 0.3305
WEAC-SL | 0.2460 | 0.3661 | 0.4973 | 0.5516 | 0.5527
WEAC-AL | 0.1776 | 0.3371 | 0.5736 | 0.5714 | 0.5589
WEAC-CL | 0.5130 | 0.5522 | 0.5736 | 0.5714 | 0.5589
GP-MGLA | 0.5186 | 0.5389 | 0.5698 | 0.5615 | 0.5508
DiCLENS | – | – | 0.5581 | – | –
Proposed | – | – | – | 0.5553 | –

Figure 4: Pareto front for Amadeus data of sample size 500 (Left) and 1500
(Right).

In this work, consensus clustering techniques are integrated in the flight
recommendation selection optimizer of the Amadeus flight search engine.
Consensus clustering solutions are used for customer segmentation with the
objective to optimize the selection strategy according to the diverse
categories of users and their different needs. The flight selection depends on
a quantity defined as a linear combination of different criteria, including
the recommendation price and diverse convenience criteria of the flights. The
linear combination of weights is optimized to maximize the booking probability
of the returned recommendations. This booking probability is estimated using a
Customer Choice Model [11] and a mapping function is necessary to assign a new
customer to a particular cluster. If the mapping function described in Sect.
4.4 was used, the $K$-Nearest Neighbors approach was also tested to predict
the label of a new customer, by finding the $K$-closest customers of this new
customer and performing a majority voting over their labels. However,
considering only $K$ neighbors for predicting the label seems to induce some
information loss, and therefore a better accuracy can be obtained using the
method described in Sect. 4.4.

Experiments presented in Table 7 were conducted on the first set of base
clustering solutions, along with the consensus solutions for 500 customers, to
perform the optimization process. The performances were then evaluated
according to the Amadeus business metric used during this optimization
process: The relative difference between the sum of all the booking
probabilities of the flight recommendations returned by the optimized solution
and by the reference solution. This reference solution is defined by setting
all weights to zero except for the recommendation price, and it corresponds to
the default configuration of the flight search engine. The Amadeus business
metric indicates to which extent the optimized solution improves the
attractiveness of the recommendations returned by the search engine. The
obtained percentage reported in the table represents how much the proposed
clustering technique improves the internal objective function used to select
the flight recommendations in the flight search engine. Although there is not
a direct link between this improvement and the conversion rate, this
percentage represents a surrogate measure to it: The difference of conversion
rate induced by the new configuration.

Table 7: Performance measure on booking probability improvement in terms of Amadeus business metric. Algorithm | K=3 | K=4 | K=5 | K=6 | K=7
---|---|---|---|---|---
Base clusterings | 49% | 8.9% | 24.4%,21.6%,12.2%,4.4%,21.5%,18.6% | 21.6% | 21.7%
CSPA | 29.7% | 14% | 27.6% | 36.5% | 19.4%
MCLA | 22.6% | 19.7% | 12.7% | 13.3% | 27.7%
HGPA | 31.3% | 13.5% | 31.9% | 37.3% | 22.5%
WEAC-SL | 6.9% | 36.8% | 13.2% | 11.6% | 21.0%
WEAC-AL | 22.7% | 31.2% | 19.8% | 21.2% | 12.8%
WEAC-CL | 20.8% | 28.6% | 32.2% | 36.1% | 26.6%
GP-MGLA | 16.8% | 19.7% | 30.0% | 27.6% | 29.6%
DiCLENS | – | – | 28.6% | – | –
Proposed | – | – | 23.6% | – | –

The proposed consensus clustering solution gives a better average improvement
than most of the base clustering solutions. It is a good compromise among
consensus solutions as it constantly gives good ARI values and its business
metric is over the median of all other consensus methods. Additionally, it
saves time compared to the current process in which we compare $N$ base
clustering solutions based on the result of the optimization process, the
processing time can be divided by $N$. This is an important feature since the
optimization process is the bottleneck part of the application.

It can be seen that some consensus algorithms such as HGPA or CSPA, give
higher improvements in term of Amadeus business metric than the proposed
method for some $K$ values. However, as shown in Tables 1-6, HGPA has a very
low ARI, which indicates that it failed to combine the base clustering
solutions. As it deviates significantly from base clustering solutions, we
cannot rely on its solution, and a similar reasoning is applicable to other
algorithms. In the current Amadeus process, retrieving the business metric for
one clustering solution is time consuming, and it is not feasible to compute
it for all consensus solutions before selecting one of them, as we did in this
study. Therefore, we need to choose a reliable algorithm showing acceptable
results in terms of both ARI and business metric. During the baseline
experiments assuming some prior business knowledge about the main features, an
improvement of 23.3% was obtained, which is equivalent to the improvement for
the proposed model that does not use any prior knowledge. We assume the
solution is composed of 6 segments (Business domestic, Business international,
Week-end domestic, Week-end international, Others domestic and Others
international). Furthermore, this assumption that is not data-dependent may
not be applicable for all search query datasets, depending on the market, the
time period, etc. Hence, it is more reliable to depend upon multiple diverse
clustering solutions and an appropriate consensus generation process.

##  6 Conclusion

In the travel industry, identifying segments of customers that have close
needs and requirements is a key step for generating better personalized
recommendation. We propose a multi-objective optimization based consensus
clustering framework to improve customer segmentation and provide better
personalized recommendation in the Amadeus flight search engine. This
framework aims to overcome the issues encountered when the segregation of
customers relies on a single clustering algorithm that is based on modeling
assumptions that do not match, partly or entirely, with the data space
regarding the number of clusters, distributions, etc. In the context of the
selection of flight recommendations returned by Amadeus flight search engine,
the proposed framework hold some properties required to generate relevant
consensus clustering such as demonstrated by the theoretical proof of its
adequate estimation of the number of clusters. This consensus clustering based
solution was integrated in the Amadeus flight search engine, and its
capability to generate better personalized recommendation, while reducing
calls to the time consuming part of current Amadeus process, were
demonstrated. The efficiency of the proposed approach regarding application
objectives and performances was also shown throughout experiments conducted on
Amadeus customer search query data to compare it with other existing
approaches. As a future direction, we intend to study how other objective
functions can be deployed in order to obtain a better clustering solution
aiming to improve booking probability.

## References

  * [1] Alqurashi, T., Wang, W.: Clustering ensemble method. International Journal of Machine Learning and Cybernetics pp. 1–20 (2018)
  * [2] Ayad, H.G., Kamel, M.S.: Cumulative Voting Consensus Method for Partitions with Variable Number of Clusters. IEEE TPAMI 30(1), 160–173 (2008)
  * [3] Chatterjee, S., Mukhopadhyay, A.: Clustering Ensemble: A Multiobjective Genetic Algorithm based Approach. In: Proc. of Intl. Conf. of CIMTA. pp. 443–449 (2013)
  * [4] Chatterjee, S., Pasquier, N., Mukhopadhyay, A.: Multi-objective clustering ensemble for varying number of clusters. In: Proc. of KARE workshop in 14th Intl. Conf. on SITIS. pp. 387–395. IEEE (2018)
  * [5] Deb, K., Pratap, A., Agrawal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation 6, 182–197 (2002)
  * [6] Fern, X.Z., Brodley, C.E.: Random projection for high dimensional data clustering: A cluster ensemble approach. In: Proc. of ICML. pp. 186–193 (2003)
  * [7] Fred, A., Jain, A.: Evidence Accumulation Clustering Based on the K-Means Algorithm. In: Structural, Syntactic, and Statistical Pattern Recognition, LNCS 2396. pp. 442–451. Springer-Verlag (2002)
  * [8] Huang, D., Lai, J.H., Wang, C.D.: Combining multiple clusterings via crowd agreement estimation and multi-granularity link analysis. Neurocomput. 170(C) (2015)
  * [9] Hubert, L., Arabie, P.: Comparing Partitions. Journal of Classification 2(1), 193–218 (1985)
  * [10] Jain, A.K., Dubes, R.C., Flynn, P.J.: Data clustering: A review. ACM Computing Surveys 31(3), 264–323 (1999)
  * [11] Lhéritier, A., Bocamazo, M., Delahaye, T., Acuna-Agost, R.: Airline itinerary choice modeling using machine learning. Journal of Choice Modelling (2018)
  * [12] Liu, S., Kang, Q., An, J., Zhou, M.C.: A weight-incorporated similarity-based clustering ensemble method. Proceedings of the 11th IEEE International Conference on Networking, Sensing and Control pp. 719–724 (2014)
  * [13] Mimaroglu, S., Aksehirli, E.: Diclens: Divisive clustering ensemble with automatic cluster number. IEEE/ACM TCBB 99(2), 408–420 (2011)
  * [14] Mimaroglu, S., Erdil, E.: Obtaining better quality final clustering by merging a collection of clusterings. Bioinformatics 26(20), 2645–2646 (2010)
  * [15] Nguyen, N., Caruana, R.: Consensus clusterings. In: Seventh IEEE International Conference on Data Mining (ICDM 2007). pp. 607–612 (2007)
  * [16] Strehl, A., Ghosh, J.: Cluster ensembles - a knowledge reuse framework for combining partitionings. Journal of Machine Learning Research 3, 583–617 (2002)
  * [17] Zhong, C., Yue, X., Zhang, Z., Lei, J.: A clustering ensemble: Two-level-refined co-association matrix with path-based transformation. Pattern Recognition 48(8), 2699–2709 (2015)