The present thesis examines a particular aspect of the general problem of anomaly detection, which has developed into an important paradigm of data mining during the past two decades. Anomaly detection tries to detect erroneous data output by a source by defining it as a deviation from the normal output.

The conventional approach to anomaly detection processes training data guaranteed to have been generated by a normal source state in order to build a profile of the normal system output. Clean training data, however, may be difficult to acquire, depending on the application.Therefore, several methods for detecting anomalies within an ensemble of data sequences or records, the majority of which is supposed to be normal, have been devised. Such approaches are usually subsumed under the category of unsupervised anomaly detection, although the term is sometimes used to refer to anomaly detection as defined above when discriminating it from the anomaly detection approach using training data to deduce a model of both the normal and the erroneous output.

Because unsupervised anomaly detection as defined above, although not ignored, has been studied much less exhaustively than (supervised) anomaly detection, especially with respect to real-world non-numerical sequence data, we decided to choose Unsupervised Anomaly Detection within Non-Numerical Sequence Data as the topic of our research, examining the following scenario:

1. We are given a set S of n sequences xb1 , xb2 , . . . , xbnー1 , xbn, the lengths being a multiple of the minimum length b, with x ∈ X={a1, a2, . . . , aZー1, aZ}, with the alphabet size Z not fixed in advance. The index i ∈ {1, 2, . . . , n ー 1, n} of the sequences may either be assigned at random or indicate the temporal order of sequence generation.

2. We suppose that the majority of 1ーρ (0 <= ρ <= ρmax=0.33) of the sequences was generated by one stationary normal source N (one-class scenario), while the remaining share ρ of the sequences was generated by one or more stationary abnormal sources A. Note that this scenario includes the case of ρ=0 (No anomalous data). The indices of the anomalous sequences may be random with respect to the overall index range, or cover a limited subsection of the range.

3. The task is to derive a measure for the normality of each sequence.

We present two distinct approaches to the above problem.

The first approach fuses together the set of sequences S into a single global sequence of length g. It uses a function called the average index difference to respectively generate a numerical value associated with every single symbol within the global sequence.

We introduce the average index difference function, which calculates the average of the index differences between a symbol or subsequence found at a particular index j and symbols or subsequence of identical value within the global sequence. We prove the convergence of the function to an expected value dependent only on the global index j but not on the symbol generation probability for the case of stationary ergodic symbol generation.

We present two algorithms based on this function.

The first algorithm exploits the fact that, if the abnormal sequences happen to be clustered within a subsection of the global sequence, the output value of the average index difference function is reciprocally related to the likelihood of the symbol to be representative of the anomalous data compared to the normal data and to have been generated within an anomalous sequence. This is because most of the identical symbols will be generated close to the index j, thus significantly decreasing the average index difference function value. The percentage c of symbols within a sequence featuring an average index difference below a certain threshold τth is used for final classification.

Because the first algorithm is hampered by supposing the abnormal sequences to be consecutively clustered within the overall sequence, we conceive the second algorithm, which extends the original average index difference function, allowing for an arbitrary location of the anomalous sequences within the global sequence. Furthermore, the algorithm extends the function to subsequences of symbols, the maximum length Mmax of which was set via an information theoretic criterion. It compares index differences between neighboring occurrences Δ (xM+1) to a ξ multiple of the empirical mean value Δ (xM+1) of those index differences, in order to identify gaps between anomalous blocks prior to the calculation of the average index difference.

Besides conceiving the algorithms, our contribution consists of showing how suitable settings for all the parameters both for the case of stationary ergodic generation and i.i.d. generation can be derived by theoretical considerations. We also deduce bounds for the computational cost of both algorithms, showing how the average index difference of every symbol within the sequence of length g can be computed in a time linear with g, and evaluate the performance of the two algorithms using both computer security-related real world data and artificial data, comparing our results to those of previous methods. Calculating the curves of the respective receiver operating characteristic, we deduce the thresholds from the set of scalar values returned by the algorithms by means of robust statistics.

Our second approach to the problem computes the matrix of pairwise distances of the set of sequences S by mapping them into a numerical space via a suitable kernel function, turning the scenario into a spatial classification problem.

The algorithm presented works as follows: First we map the sequences of S into a vector space using a suitable kernel, such that the vectors calculated from the sequences output by a stationary source will form a hypersphere. After calculating the matrix of pairwise distances of the vectors, we select a sequence close to the center of the hypersphere of the normal data as a representative of the normal data. This is done by using the distance matrix to calculate the radius β necessary to cover a share of θ of the n sequences for any sequence within S. The sequence with minimum β is chosen as representative of the normal data. Finally, the sequences are classified according to their distance from the representative sequence.

We theoretically explain the choice and parameter setting of the kernel function used for our experiments, the so-called spectrum kernel. Using the structural similarities between the kernel and a probabilistic suffix tree, we show how the optimized depth of the tree may be used for setting the dimensional parameter of the spectrum kernel. This parameter regulates the subsequence length for mapping. Moreover, we explain the setting of the key parameter of the algorithm, θ. We also bound the computational complexity of the algorithm, and evaluate the performance of the algorithm using both real world data and artificial data, comparing our results to those of previous methods.

When compared to previous methods, the two approaches presented stand out by the theoretical foundation of their parameter settings, which contrasts with the trial-and-error settings employed by most unsupervised anomaly detection algorithms. Moreover, experiments show equal or superior performance for real-world non-numerical sequence data. The first approach also establishes a unique method for comparing a particular block with all the other blocks in the data set by employing the average index difference function, which was first defined in a different context.

本論文は「Unsupervised Anomaly Detection within Non-Numerical Sequence Data (非数値系列データにおける教師無し異常検出)」と題し、4章から構成されている。さまざまな複雑なシステムにおいて、異常が発生した場合に、そのモニタリングデータから異常を自動的に検出できることが望まれている。しかし、異常は滅多に生起しないため、異常時のデータを事前に全て知ることは困難である。そのため、多くの異常検出アルゴリズムでは、正常時のデータを事前に得てその特性を解析し、その特性と比較することにより異常時データを検出することがなされている。そのような場合を教師有り異常検出というが、複雑なシステムにおいては、異常が全く含まれていないことが保証された正常データを事前に得ることが困難な場合も多い。そのような場合は、モニタリングデータのみを用いて異常の有無を検出しなければならない。このような場合を、教師無し異常検出というが、モニタリングデータが非数値データからなる場合は、数値データの場合に比べて、異常検出が特に難しくなる。本論文は、この最も難しい場合を取り扱っており、新しい異常検出アルゴリズムを提案すると共に、その性能を理論解析およびシミュレーションにより、評価している。また、従来法との比較を行い、提案手法の優れている点を明らかにしている。

第1章「Introduction」では、異常検出に関する研究の背景、目的および従来手法を紹介し、本研究の位置付けを与えている。さらに、本論文で取り扱う異常検出のフォーマルな問題設定を与えている。

第2章「Unsupervised Anomaly Detection based on Average Index Difference」では,同じシンボルが出現するインデックスの差の平均値を用いる新しい教師無し異常検出法を提案している。まず、2.1節で平均インデックス差関数を定義し、その関数の特性を理論的に明らかにしている。次に2.2節で、異常データ系列が1カ所に固まっている場合に対して、平均インデックス差を用いた教師無し異常検出アルゴリズムを提案している。さらに、その場合の平均インデックス差関数の特性を解析し、理論的に異常検出が可能であることを明らかにしている。2.3節では、異常データ系列が全系列の中に分散している場合を考え、そのような場合でも異常検出ができるアルゴリズムを提案している。理論解析により、そのアルゴリズムで異常検出が可能であることを示すと共に、適切なパラメータ値を理論的に導出している。2.4節では,数値実験により提案アルゴリズムの性能を評価している。人工的に作成したデータおよび実問題としてコンピュータネットワークの不正使用データを用いて異常検出を行った場合の性能を、従来知られている手法と比較し、提案手法の長所を明らかにしている。なお、本章において示された定理の証明は、「Appendix」にまとめて記載されている。

第3章「Unsupervised Anomaly Detection based on Representative Sequence Selection」では、データ系列を距離空間に写像し、その空間内の距離を利用して、データの異常を検出する手法を提案している。従来の手法と異なる点は、正常データの特性を求めるのではなく、正常データの代表点を求め、その代表点からの距離に基づき分類することにより、計算量が少なくてすむように工夫されている。3.1節で上記のような新しい異常検出アルゴリズムを提案し、パラメータが満たすべき条件を与えている.3.3節で上記アルゴリズムで使用する距離行列を与えるカーネル関数の定義を与えている.3.4節では提案アルゴリズムの計算コストを評価している。さらに、3.5節で、人工的なデータおよび実データとしてプロテインデータを使用して、性能評価を行なっている。一般に、正常データの分散が異常データの分散よりかなり大きい場合は異常検出が難しく、従来の手法ではうまく検出できていなかった。しかし,提案した異常検出アルゴリズムは、そのような場合でも異常検出の成功率が高いという優れた特長があることを明らかにしている。

第4章「Conclusion」では、本論文の成果をまとめると共に、今後の研究課題を明らかにしている。

なお、本論文の成果は、山本博資との共同研究であるが、論文提出者が主体となって新しいアルゴリズムの提案、解析、数値実験を行なったものであり、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。