Description:
Anomaly or outlier detection is consider as one of the vital application of data mining, which deals with anomalies or outliers. Anomalies are considered as data points that are dramatically different from the rest of the data points. In this survey, we comprehensively present anomaly detection algorithms in an organized manner. We begin this survey with the definition of anomaly, then provide essential elements of anomaly detection, such as different types of anomaly, different application domains, and evaluation measures. Such anomaly detection algorithms are categorized in seven categories based on their working mechanisms, which includes total of 52 algorithms. The categories are anomaly detection algorithms based on statistics, density, distance, clustering, isolation, ensemble and subspace. For each category, we provide the time complexity of each algorithm and their general advantages and disadvantages. In the end, we compared all discussed anomaly detection algorithms in detail.
Description:
In the era of big data, an immense volume of information is being continuously generated. It is common to encounter errors or anomalies within datasets. These anomalies can arise due to system malfunctions or human errors, resulting in data points that deviate from expected patterns or values. Anomaly detection algorithms have been developed to identify such anomalies effectively from the data. However, these algorithms often fall short in providing insights into why a particular data point is considered as an anomaly. They cannot explain the specific feature subset(s) in which a,data point significantly differs from the majority of the data. To address this limitation, researchers have recently turned their attention,to a new research area called outlying aspect mining. This area focuses on discovering feature subset(s), known as aspects or subspaces, in which anomalous data points exhibit significant deviations from the remaining set of data. Outlying aspect mining algorithms aim to provide a more detailed,understanding of the characteristics that make a data point anomalous. Although outlying aspect mining is an emerging area of research only a few studies have been published so far. One of the key challenges in this field is scaling up these algorithms to handle large datasets, characterised by,either a large data size or high dimensionality. Many existing outlying aspect mining algorithms are not well-suited for such datasets, as they exhaustively enumerate all possible subspaces and utilise density or distance-based anomaly scores to rank subspaces. As a result, most of these algorithms struggle to handle datasets with dimensions exceeding 20. Addressing the scalability issue and developing efficient algorithms for outlying aspect mining in large datasets remain active area of research. The ability to identify and understand the specific feature subsets contributing to anomalies in big data holds great potential for various applications, including fraud detection, network intrusion detection, and anomaly-based decision support systems. Existing outlying aspect mining methods are suffering from three main problems. Firstly, these measures often rely on distance or density-based calculations, which can be biased toward high-dimensional spaces. As the dimensionality of the subspace increases, the density tends to decrease, making it difficult to assess the outlyingness of data points within specific subspaces accurately. Secondly, distances or density-based measures are computationally expensive, especially when dealing with large-scale datasets that contain millions of data points. As distance and density-based measures require computing pairwise distance, it makes them computationally expensive. In addition to that, existing work uses Z-Score normalisation to make density-based scoring measure dimensionally unbias. However, it adds additional computational overload on already computationally expensive measures. Lastly, existing outlying aspect mining uses brute-force methods to search subspaces. Thus, it is essential to tackle this efficiency issue because when the dimensionality of the data is high – candidate subspace grows exponentially, which is beyond computational resources. This research project aims to solve this challenge by developing efficient and effective methods for mining outlying aspects in high-dimensional and large datasets. I have explored and designed different scoring measures to find the outlyingness of a given data point in each subspace. The effectiveness and efficiency of these proposed measures have been verified with extensive experiments on synthetic and real-world datasets. To overcome the first problem, this thesis first identifies and analyses the condition under which Z-Score based normalisation scoring measure fails to find the most outlying aspects and proposes two different approaches called HMass and sGrid++, both measures are dimensionally unbiased in their raw form, which means they do not require any additional normalisation. sGrid++ is a simpler version of sGrid that is not only efficient and effective but also dimensionality unbiased. It does not require Z-score normalisation. HMass is a simple but effective and efficient histogram-based solution to rank outlying aspects of a given query in each subspace. In addition to detecting anomalies, HMass provides explanations on why the points are anomalous. Both sGrid++ and HMass do not require pair-wise calculation like distance or density-based measures; therefore, sGrid++ and HMass are computationally faster than distance and density-based measures, which solves the second issue of existing work. The effectiveness and efficiency of both sGrid++ and HMass are evaluated using synthetic and real-world datasets. In addition to that, I presented an exciting application of outlying aspect mining in the cybersecurity domain. To tackle the third problem, this thesis proposes an efficient and effective outlying aspect mining framework named OIMiner (for Outlying - Inlying Aspect Miner). It introduces a new scoring measure to compute outlying degree, called Simple Isolation score using Nearest Neighbor Ensemble (SiNNE), which not only detects the outliers but also provides an explanation on why the selected point is an outlier. SiNNE is a dimensionally unbias measure in its raw form, which means the scores produced by SiNNE are compared directly with subspaces having different dimensions. Thus, it does not require any normalisation to make the score unbiased. Our experimental results on synthetic and publicly available real-world datasets revealed that (i) SiNNE produces better or at least the same results as existing scores. (ii) It improves the run time of the existing outlying aspect mining algorithm based on beam search by at least two orders of magnitude. SiNNE allows the existing outlying aspect mining algorithm to run in datasets with hundreds of thousands of instances and thousands of dimensions, which was not possible before.
Description:
In the era of big data, an immense volume of information is being continuously generated. It is common to encounter errors or anomalies within datasets. These anomalies can arise due to system malfunctions or human errors, resulting in data points that deviate from expected patterns or values. Anomaly detection algorithms have been developed to identify such anomalies effectively from the data. However, these algorithms often fall short in providing insights into why a particular data point is considered as an anomaly. They cannot explain the specific feature subset(s) in which a,data point significantly differs from the majority of the data. To address this limitation, researchers have recently turned their attention,to a new research area called outlying aspect mining. This area focuses on discovering feature subset(s), known as aspects or subspaces, in which anomalous data points exhibit significant deviations from the remaining set of data. Outlying aspect mining algorithms aim to provide a more detailed,understanding of the characteristics that make a data point anomalous. Although outlying aspect mining is an emerging area of research only a few studies have been published so far. One of the key challenges in this field is scaling up these algorithms to handle large datasets, characterised by,either a large data size or high dimensionality. Many existing outlying aspect mining algorithms are not well-suited for such datasets, as they exhaustively enumerate all possible subspaces and utilise density or distance-based anomaly scores to rank subspaces. As a result, most of these algorithms struggle to handle datasets with dimensions exceeding 20. Addressing the scalability issue and developing efficient algorithms for outlying aspect mining in large datasets remain active area of research. The ability to identify and understand the specific feature subsets contributing to anomalies in big data holds great potential for various applications, including fraud detection, network intrusion detection, and anomaly-based decision support systems. Existing outlying aspect mining methods are suffering from three main problems. Firstly, these measures often rely on distance or density-based calculations, which can be biased toward high-dimensional spaces. As the dimensionality of the subspace increases, the density tends to decrease, making it difficult to assess the outlyingness of data points within specific subspaces accurately. Secondly, distances or density-based measures are computationally expensive, especially when dealing with large-scale datasets that contain millions of data points. As distance and density-based measures require computing pairwise distance, it makes them computationally expensive. In addition to that, existing work uses Z-Score normalisation to make density-based scoring measure dimensionally unbias. However, it adds additional computational overload on already computationally expensive measures. Lastly, existing outlying aspect mining uses brute-force methods to search subspaces. Thus, it is essential to tackle this efficiency issue because when the dimensionality of the data is high – candidate subspace grows exponentially, which is beyond computational resources. This research project aims to solve this challenge by developing efficient and effective methods for mining outlying aspects in high-dimensional and large datasets. I have explored and designed different scoring measures to find the outlyingness of a given data point in each subspace. The effectiveness and efficiency of these proposed measures have been verified with extensive experiments on synthetic and real-world datasets. To overcome the first problem, this thesis first identifies and analyses the condition under which Z-Score based normalisation scoring measure fails to find the most outlying aspects and proposes two different approaches called HMass and sGrid++, both measures are dimensionally unbiased in their raw form, which means they do not require any additional normalisation. sGrid++ is a simpler version of sGrid that is not only efficient and effective but also dimensionality unbiased. It does not require Z-score normalisation. HMass is a simple but effective and efficient histogram-based solution to rank outlying aspects of a given query in each subspace. In addition to detecting anomalies, HMass provides explanations on why the points are anomalous. Both sGrid++ and HMass do not require pair-wise calculation like distance or density-based measures; therefore, sGrid++ and HMass are computationally faster than distance and density-based measures, which solves the second issue of existing work. The effectiveness and efficiency of both sGrid++ and HMass are evaluated using synthetic and real-world datasets. In addition to that, I presented an exciting application of outlying aspect mining in the cybersecurity domain. To tackle the third problem, this thesis proposes an efficient and effective outlying aspect mining framework named OIMiner (for Outlying - Inlying Aspect Miner). It introduces a new scoring measure to compute outlying degree, called Simple Isolation score using Nearest Neighbor Ensemble (SiNNE), which not only detects the outliers but also provides an explanation on why the selected point is an outlier. SiNNE is a dimensionally unbias measure in its raw form, which means the scores produced by SiNNE are compared directly with subspaces having different dimensions. Thus, it does not require any normalisation to make the score unbiased. Our experimental results on synthetic and publicly available real-world datasets revealed that (i) SiNNE produces better or at least the same results as existing scores. (ii) It improves the run time of the existing outlying aspect mining algorithm based on beam search by at least two orders of magnitude. SiNNE allows the existing outlying aspect mining algorithm to run in datasets with hundreds of thousands of instances and thousands of dimensions, which was not possible before.
Description:
The growth of databases in the healthcare domain opens multiple doors for machine learning and artificial intelligence technology. Many medical devices are available in the medical field however, medical errors remain a severe challenge. Different algorithms are developed to identify and solve medical errors, such as detecting anomalous readings, anomalous health conditions of a patient, etc. However, they fail to answer why those entries are considered an anomaly. This research gap leads to an outlying aspect mining problem. The problem of outlying aspect mining aims to discover the set of features (a.k.a subspace) in which the given data point is dramatically different than others. In this paper, we present a framework that detects anomalies in healthcare data and then provides an explanation of anomalies. This paper aims to effectively and efficiently detect anomalies and explain why they are considered anomalies by detecting outlying aspects. First, we re-introduced four anomaly detection techniques and outlying aspect mining algorithms. Then, we evaluate the performance of anomaly detection techniques and choose the best anomaly detection algorithm. Later, we detect the top k anomaly as a query and detect their outlying aspect. Lastly, we evaluate their performance on 16 real-world healthcare datasets. The experimental results show that the latest isolation-based outlying aspect mining measure, SiNNE, has outstanding performance on this task and has promising results.