In electronic sports, cyberathletes conceal their online training using di erent avatars (virtual identities), allowing them not being recognized by the opponents they may face in future competitions. In this article, we propose a method to tackle this avatar aliases identi cation problem. Our method trains a classi er on behavioural data and processes the confusion matrix to output label pairs which concentrate confusion. We experimented with Starcraft 2 and report our rst results.
In most of online competitive games, players need an \avatar" (an online identity) to log in the game network. Nothing forbids a player to have several avatars and actually, it is a very common practice for cyberathletes. Players generally have one o cial avatar for o cial tournaments, and several others to conceal their game tactics without being recognized by other players they may meet online: global rankings and leagues are public just as in chess and tennis, while game logs are available and prone to analysis by means of visualization and machine learning just as in standard sport analytics. Accordingly, we are facing a set of players, generating behavioural data, in an unknown one-to-many relationship with avatars (handling many-to-many relationships is left to future work). In this context, the avatar aliases identi cation problem aims at discovering the group of avatars belonging to the same player. Solving this problem is motivated by the growing need of e-sport structures to study the games and strategies of the opponents (match preparation), and the security challenges of game editors (detecting avatar usurpers).
Yan et al. showed that a classi er can be trained to predict with high
accuracy the avatars involved in a game play of Starcraft 2 [
Let A be a set of avatars and T be a set of traces such as for a given avatar a 2 A, the set Ta T is the set of all traces generated by a. Consider a classi er where labels are the avatars to predict. A classi er is a function : T ! A that assigns the avatar (t) 2 A to a given trace t 2 T . Let n = jAj be the number of avatars in A, from any classi er , one can derive a confusion matrix Cn n = (ci;j ) where ci;j = jft 2 Tai s:t: (t) = aj gj. Each row and column of C correspond to an avatar, while the value cij is the number of traces of avatar ai that are classi ed by as of avatar aj . The normalized confusion matrix is given by C~ = [ci;j =jTai j] where C~i;i = 1 for any i 2 [1; jAj] means all the traces of avatar ai are correctly classi ed by .
Our goal is to discover the group of avatars a1 a2 a3 a4 a5 that belong to the same player. Our intuition is a1 0.6 0.4 0 0 0 that a classi er will hardly di erentiate these avatar aa23 00.4 0.055 00..085 0.015 0.005 aliases, hence the confusion matrix values should be a4 0 0.05 0 0.7 0.25 high and concentrated around them. This is exem- a5 0 0 0 0.5 0.5 pli ed in Figure 1: avatars fa1; a2g are candidates Fig. 1. Confusion matrix to belong to the same player, fa4; a5g shall belong to another player, while a3 stays as singleton with a diagonal high value. A reasonable clustering of avatars would be given by ffa1; a2g; fa3g; fa4; a5gg.
More formally, given a normalized confusion matrix C~ , we would like to nd pairs of avatars ai; aj 2 U such that C~ij ' Cji ' Cii ' Cjj and C~ij + C~ji + ~ ~ ~ Cii + C~jj ' 2. These conditions come from the fact that, if ai; aj correspond to ~ the same player, traces in Tai have the same probability of being classi ed as ai or aj (the same for traces in Taj ). Furthermore, for a trace of avatar ai, it is required that the probability of classi cation is spread between ai and aj only, meaning that C~ij + C~ii ' 1 (similarly for aj ). 3
Our method rstly extracts fuzzy concepts from the confusion matrix, scores
and post-processes them to generate avatar pairs, candidates to be aliases.
Fuzzy concepts in a confusion matrix. Let us de ne the fuzzy set of
membership degrees LA where L = [0; 1], such as the mapping function : A ! LA
assigns membership values for the avatar ai in the fuzzy set LA based on the
normalized confusion matrix. Simply, this is a mapping that assigns to ai its
corresponding row in C~ which we denote C~i . We model a confusion matrix
~ as a pattern structure (A; (LA; u); ) [
(ai) u (aj ) = (ai) Example. The Figure 1 illustrates a confusion matrix obtained from a classi er . We have (a1) = fa10:6; a20:4; a03; a40; a05g, (a2) = fa01:4; a02:55; a03:05; a04; a05g and a0:4; a20:4; a03; a40; a05g. (a1) u (a2) = f 1
Actually, u corresponds to the fuzzy set intersection and (LA; v) is a partial
order over the elements of LA which can be represented as a semi-lattice. The
pattern structure (A; (LA; u); ) is provided with two derivation operators,
forming a Galois connection [
Computing and scoring concepts. From the confusion matrix we compute all
possible pattern concepts using the addIntent algorithm [
It is clear that the function s is decreasing w.r.t. the order of pattern concepts, i.e. (A1; d1) (A2; d2) =) s(d1) s(d2). Thus, pattern concepts can be mined up to a given score threshold analogously as formal concepts can be mined up to a given minimal support. We can appreciate that the higher the score of a given pattern, the more confused is the classi cation of traces of avatars a 2 A by in C~ and thus, they become candidates for merging. This property directly follows from the choice of our similarity operator u as a fuzzy set intersection, which behaves as a pessimistic operator (returning minimum values). Ranking avatar aliases. Consider the clustering condition previously formalized as C~ij ' Cji ' Cii ' Cjj and C~ii + C~ij + C~ji + C~jj ' 2. Consider that the ~ ~ ~ pair of avatars (ai; aj ) respects these conditions. It is easy to see that (ai; aj ) will necessarily be a candidate pair highly ranked from the previous step.
Cij ' Cjj ' min(C~ij ; C~jj ) and Cii ' Cji ' min(C~ii; C~ji) ~ ~ ~ ~ =)
min(C~ij ; C~jj ) + min(C~ii; C~ji) ' 1 Thus, the set of avatar clusters we are looking for are contained within the set of candidate pairs and moreover, they are highly ranked. In order to remove pairs from the list of candidates that do not hold the avatar cluster de nition, we propose a cosine similarity measure between a couple of vectors calculated for each avatar as follows. Let (ai; aj ) be a candidate pair, the cluster score is de ned as: cluster score(ai; aj ) = cosine(hC~ii; C~ij i; hC~jj ; C~jii).
The cluster score establishes a measure of how close is a candi- ai aj date pair from being an avatar cluster. The logic comes from the aaji 11 00 following scenario. Consider that the traces of avatar ai were all correctly classi ed meaning that C~ii = 1 and that the traces of avatar aj were all incorrectly classi ed as ai, meaning that C~ji = 1, thus we have the section of the normalized confusion matrix illustrated on the right hand side. We can observe that the pair (ai; aj ) will be contained in the set of candidate pairs and will be highly ranked, even though it is not an avatar cluster since it violates the rst condition. The cluster score for this particular case can be calculated as: cluster score(ai; aj ) = cosine(h1; 0i; h0; 1i) = 0, meaning that this candidate pair is not an avatar cluster. Notice that for the pair of avatars such that aii = 1 and ajj = 1, the cluster score is 1 (cosine between parallel vectors) while the pair is not an avatar cluster. However this pair would have a score s equal to 0 and would be at the bottom of the ranked candidate pairs. A third kind of pair occurs when the traces of ai and aj are all incorrectly classi ed as a third avatar ak. In such a case, the cluster score is 0. The post processing step is executed as follows. Given a ranked list of candidate pairs yielded from the previous step, each pair is evaluated using the cluster score. Given an arbitrary threshold , if the cluster score of the candidate pair is below this threshold, then it is rejected. Candidate pairs are re-ranked into a nal list of avatar clusters. 4
Data collections and objectives. We constructed two collections of Starcraft
2 replays to test our method. A replay contains all data necessary for the game
engine to replay the game. Replays are shared on dedicated websites1 and can
be parsed to extract relevant features2. The rst collection has been chosen
for studying the accuracy of classi ers to recognize avatars from their traces: we
have selected 955 professionals games of 171 unique players which cannot contain
avatar aliases3. The second collection, which have possible avatar aliases, is built
with all replays available on SpawningTool.com in July 2014, for a total 10,108
one-versus-one games and 3,805 players. This collection corresponds to a real
world situation, and is used for evaluating our avatar alias resolution approach.
Classifying avatars. Our method analyses the confusion matrix of a given
classi er . Good features, as well as a prediction method, should rst be chosen.
As features, we use the hotkey usage count [
Weka machine learning software 4 and evaluated using 10-fold cross validation from which we obtain a confusion matrix. We chose four di erent classi ers, namely K Nearest Neighbours (knn), Naive Bayes (nbayes), J48 decision tree (j48) and Sequential Minimization Optimization (smo). Parameters for each of the classi er were left as default. Figure 2 shows the ROC area and the precision obtained for 92 datasets created for Collection 1. The parameter ranged over 23 values in an exponential scale, initially from 10 to 90 seconds then from 100 to 900 and nally from 1000 to 5000 seconds (the longest game in this collection has around 5300 seconds) and thus, the x axis of each gure is in logarithmic scale. For each measure, four gures corresponding to four di erent settings of are presented. Each line corresponds to a di erent classi er. The gures present an empirical evaluation that the initial assumption, that avatars are very easily recognizable based in the signatures left in the traces they generate while playing, is true. For each di erent setting, ROC area is always around 100% showing the robustness of the approach under di erent parametrizations. Precision is always maintained over 60%, achieving its minimal value for the SMO classi er with = 5 and > 1000. Actually, this also supports the following assumptions. Firstly, it is hard to recognize users that have played a few games, meaning that the larger the value of the threshold, the more discriminative power has the classi er. Secondly, users are recognizable in the rst few minutes of the game. The precision curves show a slight concave behaviour hinting a maximum of the precision w.r.t. the time cut used for traces. Users can be e ciently discovered by their hotkeys binding settings. As the game progresses, traces may di er given that the number of options in the game greatly increase and vary in execution regarding di erent opponents.
1.0 0.9 C0.8 U A0.7 Main method evaluation strategy. As we do not have information about the users behind the avatars, it is not possible to evaluate the avatar pairs candidates using a \ground truth". Hence we performed an evaluation of our approach using three di erent strategies. First consider that an avatar of Starcraft 2 is given by its Battle.net account URL, made of a server name (Europe, America, etc.), a unique identi er, and an avatar name. We use the whole URL as avatar class labels in our classi ers. Note now that players have several accounts, on di erent servers, that may share the name. Players can also change the name of their avatar: it does not a ect the ID and server that identify their account. As our method returns an ordered list of pairs candidates merging, we consider the following indicators, for each pair.
{ Avatar names. Two avatars may have the same name but di erent battle net id. It is weak indicator as it can be a common name (e.g. Batman). { Battle.net account unique ID. Two avatars may have two di erent names but the same unique identi er. This is a strong indicator. { Surrogates. We create surrogate avatars a1; a2 from an avatar a 2 A by generating a partition in two di erent subsets of traces for each avatars. Our goal is to retrieve that a1 and a2 are avatar aliases. For splitting traces of an avatar into surrogates, we introduce a parameter as a balance between the traces distributed over the surrogate avatars ( = 0:5 yields that both surrogate avatars will have half associated traces). We introduce others parameters: is the proportion of avatars who are converted in surrogates aliases. We assume that professionals play a lot of games then we select the avatar which have played more than games. As we have observed, it is not necessary to analyse the entire replay to discriminate an avatar then we select the rst either actions or seconds. sureTotheevapluraecteisioounr, arpepcraollacahnwdefw-milelamsuerae- 20 SMO Top 20 : γ=0.05, θ=5, λ=0.9 SUNURAGLMES of the rst 100 ranked avatar clusters. FP Given the ranking r, we consider T P; F P 15 EGaLive-aLiveRC and F N stand for true positives, false pAospitaiivresisanad ffaallssee npeogsaittiivveeswrehsepnecwtievedlyo. ikanngR10 not have enough information to consider them as true positives, meaning that their 5 avatar names do not match, their URL is sdeit eorfensutrarnodgattheeayvaartearnso.tTphaeryt oafreouinr ofawcnt 00.6 0.7 0.8 Score 0.9 1.0 1.1 the kind of pairs we are looking for. As Fig. 3. Candidate pairs ranking. an example, the Figure 3 shows the initial candidate pairs extracted from a confusion matrix generated by a Sequential Minimization Optimization (SMO) classi cation with = 0:05, = 5 and = 0:9. Within the gure, a point represent a pair of avatars with a red circle if the avatars are surrogates, a green triangle if they have the same account, a yellow star if they have the same name and in the other cases a blue cross, annotated with the nick-names of the avatars. The only FP in this list is a couple of avatars that belong to the player known as aLive5. We also report on other three measures, namely P@10 (precision in the rst 10 elements of the ranking), mean average precision (MAP), the receiver operating characteristic (ROC) and the ROC area under the curve (AUC). Identifying multiple aliases. The goal of these experiments is to assess our approach for nding avatar aliases based of the evaluation introduced above. For generating datasets, we have selected three di erent values, namely 30; 60 and 90 seconds. We have picked the same values for as in the previous experiments. Surrogates were generated for the rst 5, 10, 15 and 20 percent of the most active users in the dataset ( ) and we have set the balance = 0:5. For each of the previously selected classi ers, the confusion matrix was processed by the Sephirot addIntent implementation6 to obtain a set of pattern concepts. Scoring and post processing were implemented in ad-hoc python scripts. Table 1 shows a summary for the evaluation results using the top 100 pairs of avatar clusters. Results indicate that our approach is very e cient at identifying surrogate avatars, particularly for KNN and the J48 classi ers achieving very high recall values. In the upper part of the table, while precision is low it is worth noticing that in the top 100, there are only 41 surrogates meaning that the maximum achievable precision is 0.41. The classi er KNN is particularly good in this measure achieving an almost perfect value (0.4 of 0.41). All four classi ers achieve a very high precision in the rst 10 results (P@10) while two of them get a perfect score. Indeed, one of the main characteristics of our approach is the good ranking it generates over the avatar pairs. This fact is con rmed by the good MAP and ROC area under the curve (AUC) values achieved by all four classi ers. Both these measures slightly degrade when including in the set of true positives URLs and names. This can be understood since not all avatars with the same name necessarily belong to the same user. Thus, pairs of avatars with the same name will be more evenly distributed over the ranking or can even be found at the bottom indicating that they do not belong to the same user. This fact is re ected in the gap between the high growth of precision and low degradation of recall, i.e. avatars with the same name are distributed between the pairs retrieved and those that were not. As we have discussed, avatars with the same URL necessarily belong to the same user. Hence, we would have expected that in the rst 10 pairs retrieved we could nd an even distribution of surrogates and URLs. Instead, for all classi ers, P@10 is more than 80% surrogates (while the rest is always URLs - P@10 in the medium part of the table). Table 2 shows a summary of results when looking for just surrogates while varying the balance in the distribution of traces between them. We can clearly observe that the performance of the approach quickly degrades as more imbalanced gets the distribution (the higher the value). Actually, for some classi ers it is not possible to obtain a single good result, even when we have lowered the threshold to 0.8. As URLs are not necessarily balanced, classi ers tend to predict the label of a trace belonging to an avatar with less traces to one with more traces. Issues
6 https://code.google.com/p/sephirot/
related to learning from imbalanced datasets are reviewed in [
Parameters: = 0:2;
KNN Balance F1 MAP Recall AUC Prec. P@10 = 0:5 0.905 0.964 0.909 0.732 0.9 1.0 = 0:6 0.750 0.957 0.868 0.929 0.660 1.0 = 0:7 0.184 0.706 0.269 0.949 0.140 0.7 We introduced the problem of avatar aliases identi cation when there exists no mapping between individuals and their avatars. This is an important problem for game editors, but also for e-sport structures. Our method relies on the fact that behavioural data hide individual characteristic patterns, which allows making predictive approaches very accurately. Nevertheless, this good performance quickly degrades when data hides avatar aliases, which is why we based our analysis on confusion matrices. As future work, we plan to study other competitive games, and how biclustering could tackle the problem. We also believe that our approach can be used to solve other application problems, such as identifying users on di erent devices (smart-phones, tablet, computer, etc.) regarding the usage traces they left. Incremental Algorithm for Constructing Concept Lattices. In Concept Lattices.