|Computers, Materials & Continua |
Outlier Detection of Mixed Data Based on Neighborhood Combinatorial Entropy
1School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing, 210044, China
2Southern Marine Science and Engineering Guangdong Laboratory (Zhuhai), Zhuhai, 519080, China
3School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing, 210044, China
4International Business Machines Corporation (IBM), New York, 10504, USA
*Corresponding Author: Lina Wang. Email: email@example.com
Received: 02 February 2021; Accepted: 10 April 2021
Abstract: Outlier detection is a key research area in data mining technologies, as outlier detection can identify data inconsistent within a data set. Outlier detection aims to find an abnormal data size from a large data size and has been applied in many fields including fraud detection, network intrusion detection, disaster prediction, medical diagnosis, public security, and image processing. While outlier detection has been widely applied in real systems, its effectiveness is challenged by higher dimensions and redundant data attributes, leading to detection errors and complicated calculations. The prevalence of mixed data is a current issue for outlier detection algorithms. An outlier detection method of mixed data based on neighborhood combinatorial entropy is studied to improve outlier detection performance by reducing data dimension using an attribute reduction algorithm. The significance of attributes is determined, and fewer influencing attributes are removed based on neighborhood combinatorial entropy. Outlier detection is conducted using the algorithm of local outlier factor. The proposed outlier detection method can be applied effectively in numerical and mixed multidimensional data using neighborhood combinatorial entropy. In the experimental part of this paper, we give a comparison on outlier detection before and after attribute reduction. In a comparative analysis, we give results of the enhanced outlier detection accuracy by removing the fewer influencing attributes in numerical and mixed multidimensional data.
Keywords: Neighborhood combinatorial entropy; attribute reduction; mixed data; outlier detection
Outlier detection is frequently researched in the field of data mining technologies and is aimed at identifying abnormal data from a data set . It is widely applicable for credit card fraud detection, network intrusion detection, fault diagnosis, disaster prediction, and image processing [2–8]. Presently, outlier detection methods are conducted with statistical techniques , which include distance-based proximity, network-based and density-based proximity [10–12], data clustering , and rough set data modeling .
Statistical methods require the presence of a single feature and predicable data distribution. In real environment, many data distributions are unpredictable and multi-featured. In addition, their applications are restricted . Knorr et al.  proposed a distance-based method that required little information of the data set and was therefore suitable for any data distribution. Early outlier detection algorithms focused on mining global outliers. Contrarily, a multidimensional algorithm must outline data locally because its data sets are unevenly distributed, complex, and difficult to identify. Since Breunig et al.  put forward the concept of local outliers, local outlier detection has attracted considerable attention owing to its practical advantage in reducing time overhead and improving scalability. The local outlier detection algorithm starts by calculating the outlier value of local data and defining outlying data. Subsequently, the local outlier detection algorithm focuses on the local neighborhood determination to calculate local outliers [17,18]. A clustering algorithm divides a data set into several clusters to show similarities and differences of objects based on their respective clusters . When judging a local outlying object, a cluster is considered as its neighborhood, and the local outliers of the data are calculated in the neighborhood . Outlier detection based on information entropy theory  judges the amount of information in the outlier through entropy value and determines outlying data in light of their entropies . The introduction of information entropy weighting effectively improved the outlier detection accuracy .
Many studies [24–27] focused on rough set-based detection methods, which originated from intelligent systems. Although the studies provided insufficient and incomplete information, they were introduced into outlier detection to handle categorical data. Conventional outlier detection uses more numerical data than classical rough set-based methods as they deal with categorical data. However, the processing of mixed data of categorical and numerical attributes, ubiquitous in real applications, has received inadequate attention. Through the adoption of robust neighborhood, explorations were conducted to improve classical rough sets for better performance in numerical and mixed data. At present, neighborhood rough sets are effective for attribute reduction, feature selection, classification recognition, and uncertainty reasoning.
This study aims to use a novel approach by combining attribute reduction with outlier detection technology to improve the outlier detection accuracy, reduce calculation complexity, remove fewer influencing attributes and reduce data dimensions. Data-processing plays a significant role in attribute reduction by using experimental multi-type data to achieve an accuracy boost for outlier detection. Using the neighborhood combinatorial entropy model, we construct mixed data outlier detection algorithms after defining the local outlier factor (LOF) algorithm, neighborhood combinatorial entropy algorithm and relevant concepts. Comparative data analysis is conducted to verify the detection accuracy after attribute reduction.
The rest of the paper is structured as follows. Section 2 provides the LOF algorithm, providing related definitions. Section 3 discusses the neighborhood combinatorial entropy algorithm, providing related definitions. Section 4 constructs the mixed data outlier detection algorithms based on neighborhood combinatorial entropy. Section 5 carries out the experimental analysis on the advantages of attribute reduction prior to outlier detection. Finally, Section 6 concludes the paper.
2 Local Outlier Factor Algorithm
2.1 Related Definitions
The LOF algorithm is a representative outlier detection algorithm that computes local density deviation . It calculates a local outlier factor of each object, and judges whether the object is an outlier that deviates from other objects or a normal point.
Definition 1: We define the distance (Euclidean distance) between object x and object y; two objects in object set U are as follows:
where m represents the dimension of the objects; and and represent the coordinates of the ith dimension of objects and , respectively.
Definition 2: We define the kth nearest distance of an object in object set as:
where is the kth nearest neighbor to object in all dimensions (excluding object ). The Euclidean distance between object and object is the kth nearest distance of object x. As shown in Fig. 1, the object is the 5th closest neighbor to the object , which concludes that .
To determine the value of , the number of objects in the set satisfies the following: (1) the number of objects (object excluded) is at least so that ; (2) the number of object (object excluded) is at most , making .
Definition 3: We define the neighborhood of k nearest neighbors of the object in object set as:
Eq. (3) describes the set of objects within the kth nearest distance (including the kth nearest distance) of the object ; therefore, the number of objects in the neighborhood of conforms to . As shown in Fig. 1, the 5 nearest neighbors of object are the set .
Definition 4: We define the kth reachable distance from the object to object in object set as:
The kth reachable distance from to is longer between the kth nearest distance of and real distance from to . The distances from to the -nearest objects from are equal and are . The distance between the object and other objects apart from the above-mentioned k nearest objects is the real distance between the two objects.
As indicated in Fig. 2, the actual distance from to is smaller than the 5th nearest distance of . From the definition, . The actual distance from to is greater than the 5th nearest distance from ; thus, .
Definition 5: We define the local reachable density of the object in object set as:
refers to the density. The larger the value , the higher the density, and the more the objects belong to the same cluster. Contrarily, the smaller the value , the lower the density, revealing that the objects are likely to be outliers.
If the object is in the same cluster as the neighboring objects, the reachable distance is likely to be , the kth nearest distance of the object . Otherwise, the reachable distance may be , which is the true distance. From Eq. (4), , the kth nearest distance of object is smaller than , the true distance. Hence the denominator of Eq. (5) in the same cluster is smaller than that in different clusters. The values in the same cluster will be larger than those in different clusters. When the value is smaller, object x is likely to be an outlier.
Definition 6: We define the local outlier factor of the object in object set as:
represents the average ratio of the local reachable density of the objects in the neighborhood and the object to the local reachable density of the object . When the value is closer to 1, the local reachable density of the objects in the neighborhood is closer to the local reachable density of the object . The object is likely to be in the same cluster in its neighborhood. Otherwise, when the value is smaller than 1, the local reachable density of the object is higher than that of its neighborhood, revealing that the object tends to be in the dense points. If the value is larger than 1, the local reachable density of the object is lower than that of its neighborhood, revealing that the object is likely to be an outlier.
2.2 Analysis of LOF Algorithm
The LOF algorithm examines whether the point is an outlier, which is carried out by comparing the local density of each object x and its neighboring objects. The lower the density of object x, the more likely it is an outlier. The density is calculated using the distance between objects. The farther the distance, the lower the density, and the higher the outlier. In certain objects, the neighborhood of k nearest neighbors is introduced to expand its global determination as a substitute to direct global calculation. In this way, one or more clusters of dense points are determined based on local density, thereby realizing multiple clusters identification. The cluster is comprised of multi-type data, containing categorical attribute, numerical attribute or mixed attribute. However, the algorithm of Eq. (1) can only process numerical data. The accuracy of LOF algorithm is ineffective for categorical or unknown data types.
3 Neighborhood Combinatorial Entropy
The neighborhood combinatorial entropy calculation follows two aspects: neighborhood approximate accuracy and neighborhood conditional entropy. The neighborhood approximate accuracy is the ability to divide the system from the set perspective [28,29]; whereas, the neighborhood conditional entropy is the ability to divide the system from the knowledge perspective .
3.1 Related Definitions
The information system is an aspect of data mining, expressed in a four-dimensional form . In this system, is a non-empty limited set of objects; is a non-empty set of attributes; is the union of the attribute domain ; and f is the information function: , which is .
In addition, attributes are categorized into conditional and decision attributes. Therefore, attribute set is the union of conditional attribute set and decision attribute set , namely, . Moreover, the information system is defined as a decision-making system .
When neighborhood range is set manually, , a neighborhood threshold is added to the information system and transformed into a neighborhood information system . In this case, is also called the neighborhood radius.
Definition 7: We define the distance measure of two objects on attribute subset as:
In Eq. (7), is a subset of attributes,
represents the dimension of the object, namely, the number of attributes.
corresponds to the ith attribute.
and are in .
is the square of the distance between object and object in the ith dimension.
The calculations on the distance between two objects are different, which depend on attribute types ,
is a numerical attribute; and
By eliminating the influence of dimension and value range between the attributes, numerical attributes are pre-processed into dimensionless data where each attribute value falls within the range of [0, 1]
is categorical attribute; and
Categorical data are converted into numerical data, and their values are determined per their categories. From Eq. (8), the data values of all numerical attributes are within the range of [0, 1]. Thus, we set the maximum value of the distances of different types to 1, and that of the minimum value to 0. After converting categorical data into numerical data, the distance between different objects is obtained through numerical calculations
is an unknown attribute; and
Eq.(10) is a new classification due to the unknown attribute. The data in this category belongs to a cluster different from other data, and a maximum distance of 1 is defined according to different attribute classifications in the clusters.
When processing different data categories, corresponding formulas are selected. Subsequently, the distance of the mixed data is obtained by applying Eq. (7), and the application of mixed data is realized by adopting different distance calculation following different attribute types.
becomes the effective distance in the neighborhood information system. When combined with neighborhood threshold parameter , it defines neighborhood relationship.
Definition 8: In a neighborhood information system , the neighborhood of object on attribute subset B is:
Definition 9: We define the upper approximation and lower approximation of the attribute subset B in an object set , as:
Their relationship is expressed in Fig. 3.
Definition 10: We divide the object set into according to its decision attributes. The approximate accuracy of the neighborhood of attribute subset B is:
As shown in Fig. 3, , so . Compared with the upper approximation, the lower approximation of the set increases more significantly similar to the set . Similarly, the value of the neighborhood approximation accuracy increases. However, in a probability, as the attribute subset increases, the increase of the lower approximation in the set is equal to that of the upper approximation in the set . Therefore, the value of , the neighborhood approximate accuracy, remains unchanged. This case has no impact on the final result (refer to Definition 13 for a detailed analysis).
Definition 11:We define the neighborhood information entropy of attribute subset in the object set as:
represents the affiliation of the object in the neighborhood and . Neighborhood entropy simulates the classic information entropy and provides an overall uncertainty description for neighborhood information. As the neighborhood information entropy of a certain attribute subset grows larger, this attribute subset distinguish different objects in the set , particularly when and .
Definition 12: We define the neighborhood conditional entropy of attribute set , under the condition of as:
Since is for attribute set , attribute set is a conditional attribute, and and are conditional attribute sets. Eq. (16) reflects the uncertainty of conditional attribute set P to conditional attribute set . If is a set of decision attributes , represents the uncertainty of a set of conditional attributes to a set of decision attributes . The entropy value of neighborhood conditional entropy is monotonous and bounded, and its value decreases as the conditional attribute set increases.
Definition 13: We divide the object set into based on its decision attribute. The neighborhood combinatorial entropy of on attribute subset is defined as:
From Eq. (17), neighborhood combinatorial entropy is composed of Eqs. (14) and (16), reflecting uncertainties in set theory and knowledge, respectively. Thus, neighborhood combinatorial entropy interprets uncertainty from multiple angles, and its uncertainty is more comprehensive than that in either set theory or knowledge.
Though , the neighborhood approximation accuracy in Definition 10 is non-monotonic and does not exert influence on the final neighborhood combinatorial entropy. increases or remains unchanged as the attribute subset increases. However, neighborhood conditional entropy affects the result of neighborhood combinatorial entropy. Analysis in Definition 12 shows that neighborhood conditional entropy has strict monotonicity. Though remains constant in some cases, the neighborhood combinatorial entropy maintains its monotonicity.
From the above analysis, increases or remains unchanged as attribute subset increases. In Eq. (17), the neighborhood conditional entropy decreases as the attribute subset increases, and the neighborhood combinatorial entropy increases as the attribute subset increases. With changes in conditional attribute set, the higher the neighborhood combinatorial entropy value for a conditional attribute set, the more important a conditional attribute is to the whole system.
Definition 14: We define the significance of a conditional attribute (attribute subset excluded) to attribute subset as:
First, we set an attribute subset as an empty set. Then, we compare all conditional attributes according to Eq. (18). If takes the maximum value of of all conditional attributes except the attribute subset , the conditional attribute has the highest significance of all the conditional attributes except set , written into attribute subset . By iterative procedure, more conditional attributes are obtained in descending order of significance. Based on a threshold value of significance, conditional attributes are kept in the attribute subset ; otherwise, they are removed. When this procedure is completed, a data set of the attribute reduction is available.
3.2 Analysis of Neighborhood Combinatorial Entropy
From an information theory perspective, an entropy value reflects the importance of a condition attribute in an information system in determining whether the condition attribute is reduced. Entropy has the following properties: non-negativity, i.e., ; and maximum value, i.e., , reflecting a measure of significance in both the set and knowledge and the uncertainty of the set and knowledge. Therefore, the measurement of significance is a multi-angle operation.
4 Mixed Data Outlier Detection Algorithm Based on Neighborhood Combinatorial Entropy
In Algorithm 1, the LOF algorithm focuses on estimating Euclidean distance. Higher data dimension implies more squares and longer calculation time. In the LOF algorithm, a lower data dimension saves significant calculation time.
Algorithm 1 has limited capability for mixed data outlier detection. Algorithm 2 adopts different calculation methods for different attribute. Categorical and mixed data participate in data operation. After data treatment with Algorithm 3, attribute-reduced data are obtained and processed with LOF algorithm (Algorithm 1).
Attribute reduction filters out redundant data and shortens the calculation time without altering system applicability as some attributes are redundant and cause errors in the system. Filtering out errors improves the system’s accuracy. In Algorithm 2, neighborhood combinatorial entropy determines the significance of a conditional attribute in the attribute subset of the entire system. Applying Algorithms 2, 3 and the LOF algorithm for data processing reduces the data size processed by outlier detection, improve the outlier detection accuracy, and reduce misjudgment proportion.
5 Experimental Analysis
5.1 Experimental Data Set
5.1.1 220 Randomly Generated 2-Dimensional Data
First, 100 2-dimensional data of normal distribution are first randomly generated. To verify the LOF algorithm detection ability, the 100 random data are translated separately to form two clusters of data widely apart from one another. Hence, 200 data are generated. As presented in Fig. 4a, all dense points are divided into two clusters. The distribution of outliers is shown in Fig. 4b; blue dots are the 200 dense data, and yellow dots are the 20 outliers. The outlier points are relatively far from the two clusters of dense points, providing better references and contrast for the experiment on Algorithm 1.
5.1.2 220 Randomly Generated 8-Dimensional Data
A total of 200 8-dimensional dense data and 20 8-dimensional outlier data are randomly generated. The method generating the data is as same as that generating the randomly 2-dimensional data.
5.1.3 220 Randomly Generated 16-Dimensional Data
A total of 200 16-dimensional dense data and 20 16-dimensional outlier data are generated as the outlined in Fig. 4.
5.1.4 Wisconsin Breast Cancer Data Set
The Wisconsin breast cancer data set contains 699 objects with 10 attributes. From the 10 attributes, 9 attributes are numerical conditional attributes, and 1 is a decision attribute. All cases are in two categories: benign (458 cases) and malignant (241 cases). Some malignant examples are removed to form an unbalanced distribution of all the data, assisting the experimental data in accordance with the cases of few outliers in practical applications. The data set contains 444 benign instances (91.93%) and 39 malignant instances (8.07%). Fig. 5 presents the results of malignant objects as outliers.
5.1.5 Annealing Data Set
The annealing data set contains 798 objects with 38 attributes. Among the 38 attributes, 30 are classified condition attributes, 7 are numerical condition attributes, and 1 is decision attribute. The 798 objects are in 5 categories. The first category contains 608 objects (76.19%), and the remaining 4 categories contain 190 objects (23.81%). Classes 2–5 are all regarded as outliers. The distribution is visualized in Fig. 6.
Tab. 1 lists the multidimensional data, which includes pure numerical data and data comprising numerical and categorical attributes, all of which are within the capacity of the proposed algorithm and broadened application scope of attribute reduction algorithms.
5.2 Analysis of Results
There are 20 outliers in the randomly generated 2-dimensional data set. Given the number of outliers as 20, the objects corresponding to the first 20 largest values of local outlier factor in Eq.(6) are the same as those in Fig. 4b, so the detection accuracy rate is 100%.
For the 8-dimensional data, among the 20 detected outlier objects, only 18 are artificially outliers, and the others are misjudged. The experimental results are not as promising as the 2-dimensional data. In the 16-dimensional data, only 17 of the 20 artificially set objects are identified as outliers, and the others are misjudged. Tab. 2 shows the accuracy of outlier detection of the LOF algorithm on the three randomly generated data sets.
As shown in Tab. 2, the outlier detection accuracy on the randomly 2-dimensional data has the higher value in LOF algorithm than that on the 8-dimensional data or 16-dimensional data. In addition, the 8-dimensional data are better than the 16-dimensional data, revealing that detection accuracy decreases as dimension increases. Data dimension influences the accuracy of the outlier detection algorithm. Therefore, attributes reduction before outlier detection improves the accuracy of outlier detection.
The Wisconsin breast cancer data set comprises 39 presupposed outliers. Among the first 39 objects with the largest local outlier factor calculated by the LOF algorithm, 34 are real outliers, and the other 5 are misjudged dense points. The annealing data set has 190 outliers, of which 72 outliers are real outliers, and the others are misjudged. Tab. 3 shows the accuracy of the algorithm on real data sets.
Four multidimensional data sets (excluding 2-dimensional data) separately underwent data attribute reduction in Algorithm 2. In the process, the attribute subset is determined by calculating neighborhood combinatorial entropy. After attribute reduction, the attribute number of the randomly generated 8-dimensional data is still 8. By comparing the number of attributes, randomly generated 16-dimensional data reduced to 15, and 6 for the Wisconsin breast cancer data set, and 21 for the annealing data set. The variations of their attributes before and after reduction are illustrated in Fig. 7.
From Fig. 7, the system carries out data dimension reduction on data sets, and dimensions of some sets are not reduced, e.g., the 8-dimensional data. By comparing the results of the algorithms, all attributes in a data set have equal influence on the system application (none are filtered out).
Algorithm 1 is adopted to detect outliers from the data sets with reduced attributes. The results are listed in Tab. 4. After attribute reduction, among the top 20 objects with the largest local outlier factors of the 16-dimensional data, 17 are true outliers, and the others are incorrectly judged. The accuracy rate of outlier detection is 85.00%. For the Wisconsin breast cancer data set, after attribute reduction, among the top 39 objects with the largest local outlier factors, 36 are true outliers, and the others are misjudged. The accuracy rate rises to 92.31%. After attribute reduction, for the annealing data set, among the first 190 objects with the largest local outlier factors, 88 are true outliers, and 102 are erroneous. The detection accuracy rate reaches 46.32%. Fig. 8 presents the outlier detection results before and after attribute reduction.
As revealed in Fig. 8, attributes identified as useless are reduced by the system, leading to a smaller data size for processing and shortening detection time. For higher outlier detection rate, the attribute reduction algorithm filtered out the error-prone attributes from the system. In addition, enhanced accuracy is obtained in two attribute-reduced data sets, an indication of the validity and effectiveness of the proposed reduction algorithm.
The accuracy of the randomly generated 16-dimensional data remains stable before and after attribute reduction, revealing that the attribute filtering rate is minimal and close to zero, which influences the system. Thus, detection accuracy is intact through attribute reduction.
This study combined an attribute reduction algorithm with the LOF algorithm to improve the accuracy of outlier detection for highly dimension numerical and mixed data. Following the algorithms of attribute reduction and the LOF outlier detection, this study analyzed the monotonicity of the attribute reduction algorithm and explained the application of the data processed in outlier detection. We performed the experiments to apply the LOF algorithm on data sets of different dimensions, to assess its performance by calculating its detection accuracy. We also inserted significance determination and attribute reduction algorithms before the LOF algorithm for the five data sets and calculated new detection accuracy. Finally, we compared the feasibility and effectiveness of the two groups of data to assess their detection accuracy before and after data attribute reduction. In comparison, the proposed method reduced data dimensions, calculation time, and improved the outlier detection accuracy when attribute reduction algorithm was combined with outlier detection technology.
Funding Statement: The authors would like to acknowledge the support of Southern Marine Science and Engineering Guangdong Laboratory (Zhuhai) (SML2020SP007). The paper is supported under the National Natural Science Foundation of China (Nos. 61772280 and 62072249).
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|