O-PCF algorithm for one-class classification. (English) Zbl 1462.62379
Summary: One-class classification, or outlier detection, is of great importance when data can be properly obtained from only one target class. The problem has many applications in various areas when the outlier class, defined as the complementary set to the target class, is absent. In this paper, we develop a novel one-class classification algorithm called the one-class polyhedral conic functions (O-PCF) algorithm. In this algorithm, the decision boundary for the target class is defined by PCFs’ level sets. The level set of a PCF is a convex polyhedron; thus, only convex decision boundaries can be obtained with one PCF. However, the target class may have a non-convex structure. Thus, the O-PCF algorithm divides the target class into \(k\) clusters and obtains a PCF for each cluster. O-PCF constructs the final classifier as the minimum of \(k\) PCFs to generate non-convex separating surfaces. The performance of the O-PCF algorithm is presented in comparison with other methods in the literature. The test results lead us to conclude that the O-PCF algorithm outperforms the other methods in many cases.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62G32 | Statistics of extreme values; tail inference |
| 60F10 | Large deviations |
| 68T10 | Pattern recognition, speech recognition |
| 65K05 | Numerical mathematical programming methods |
| 90C90 | Applications of mathematical programming |
Keywords:
one-class classification; polyhedral conic functions (PCF); outlier detection; mathematical programmingReferences:
| [1] | Bagirov, A. M.; Ugon, J.; Webb, D.; Ozturk, G.; Kasimbeyli, R., A novel piecewise linear classifier based on polyhedral conic and max-min separabilities, TOP, 21, 3-24 (2013) · Zbl 1263.65051 · doi:10.1007/s11750-011-0241-5 |
| [2] | Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K., Learnability and the vapnik-chervonenkis dimension, J. ACM, 36, 929-965 (1989) · Zbl 0697.68079 · doi:10.1145/76359.76371 |
| [3] | Campbell, C. and Bennett, K.P., A linear programming approach to novelty detection, in Proceedings of the 13th International Conference on Neural Information Processing Systems, NIPS’00, Denver, CO, MIT Press, Cambridge, MA, USA, 2000, pp. 374-380. |
| [4] | Cevikalp, H. and Triggs, B., Polyhedral conic classifiers for visual object detection and classification, in 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, Hawaii, 2017 July. |
| [5] | Chang, C. C.; Lin, C. J., LIBSVM: A library for support vector machines, ACM Trans. Intell. Syst. Technol., 2, 27:1-27:27 (2011) · doi:10.1145/1961189.1961199 |
| [6] | Cimen, E., Gesture recognition with polyhedral conic functions based classifiers, Master’s thesis, Graduate School of Science, Anadolu University, 2013, (in Turkish). |
| [7] | Cimen, E.; Ozturk, G., Arrhythmia classification via k-means based polyhedral conic functions algorithm, 798-802 |
| [8] | de Ridder, D., Tax, D., and Duin, R., An experimental comparison of one-class classification methods, in Proceedings of the 4th Annual Conference of the Advanced School for Computing and Imaging, Delft, 1998. |
| [9] | Elkan, C. and Noto, K., Learning classifiers from only positive and unlabelled data, in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, Las Vegas, Nevada, USA, ACM, New York, NY, USA, 2008, pp. 213-220. Available at doi:10.1145/1401890.1401920. |
| [10] | Erfani, S. M.; Rajasegarar, S.; Karunasekera, S.; Leckie, C., High-dimensional and large-scale anomaly detection using a linear one-class \(####\) SVM \(####\) with deep learning, Pattern Recognit., 58, 121-134 (2016) · doi:10.1016/j.patcog.2016.03.028 |
| [11] | Gasimov, R. N.; Ozturk, G., Separation via polyhedral conic functions, Optim. Methods Softw., 21, 527-540 (2006) · Zbl 1113.90095 · doi:10.1080/10556780600723252 |
| [12] | Github: Python 2.7 code for o-pcf algorithm (2017), https://github.com/emrecimen/O-PCF-Algorithm. |
| [13] | Hao, P. Y., Fuzzy one-class support vector machines, Fuzzy Sets Syst., 159, 2317-2336 (2008) · Zbl 1186.68367 · doi:10.1016/j.fss.2008.01.013 |
| [14] | Gurobi, I., Gurobi optimizer reference manual (2016), Available at http://www.gurobi.com. |
| [15] | Japkowicz, N., Concept-learning in the absence of counterexamples: an autoassociation-based approach to classification, Ph.D. diss., New Brunswick Rutgers, The State University of New Jersey, 1999. |
| [16] | Khan, S.S. and Madden, M.G., One-class classification: Taxonomy of study and review of techniques, CoRR abs/1312.0049 (2013), Available at http://arxiv.org/abs/1312.0049. |
| [17] | Lichman, M., UCI machine learning repository (2013), Available at http://archive.ics.uci.edu/ml. |
| [18] | Liu, B., Dai, Y., Li, X., Lee, W.S., and Yu, P.S., Building text classifiers using positive and unlabelled examples, in Third IEEE International Conference on Data Mining, Melbourne, Florida, USA, 2003, pp. 179-186. |
| [19] | Manevitz, L. M.; Yousef, M., One-class svms for document classification, J. Mach. Learn. Res., 2, 139-154 (2002) · Zbl 1002.68597 |
| [20] | Moya, M.M., Koch, M.W., and Hostetler, L.D., One-class classifier networks for target recognition applications, Tech. Rep., Sandia National Labs., Albuquerque, NM (United States), 1993. |
| [21] | Ozturk, G.; Bagirov, A. M.; Kasimbeyli, R., An incremental piecewise linear classifier based on polyhedral conic separation, Mach.Learn., 101, 397-413 (2015) · Zbl 1343.62037 · doi:10.1007/s10994-014-5449-9 |
| [22] | Ozturk, G.; Ciftci, M. T., Clustering based polyhedral conic functions algorithm in classification, J. Ind. Manage. Optim., 11, 921-932 (2015) · Zbl 1456.68162 · doi:10.3934/jimo.2015.11.921 |
| [23] | Pestov, V., Pac learnability versus vc dimension: a footnote to a basic result of statistical learning, CoRR abs/1104.2097 (2011), Available at http://arxiv.org/abs/1104.2097. |
| [24] | Schölkopf, B.; Platt, J. C.; Shawe-Taylor, J. C.; Smola, A. J.; Williamson, R. C., Estimating the support of a high-dimensional distribution, Neural Comput., 13, 1443-1471 (2001) · Zbl 1009.62029 · doi:10.1162/089976601750264965 |
| [25] | Tax, D.M., One-class classification (2001). |
| [26] | Tax, D. M.; Duin, R. P., Support vector domain description, Pattern Recognit. Lett., 20, 1191-1199 (1999) · doi:10.1016/S0167-8655(99)00087-2 |
| [27] | Valiant, L. G., A theory of the learnable, Commun. ACM, 27, 1134-1142 (1984) · Zbl 0587.68077 · doi:10.1145/1968.1972 |
| [28] | Vapnik, V.; Chervonenkis, A., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264-280 (1971) · Zbl 0247.60005 · doi:10.1137/1116025 |
| [29] | Vapnik, V.; Levin, E.; Cun, Y. L., Measuring the vc-dimension of a learning machine, Neural Comput., 6, 851-876 (1994) · doi:10.1162/neco.1994.6.5.851 |
| [30] | Yu, H., SVMC: Single-class classification with support vector machines, in Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI’03, Acapulco, Mexico, Available at http://dl.acm.org/citation.cfm?id=1630659.1630743, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003, pp. 567-572. |
| [31] | Yu, H., Single-class classification with mapping convergence, Mach. Learn., 61, 49-69 (2005) · Zbl 1469.62294 · doi:10.1007/s10994-005-1122-7 |
| [32] | Zeugmann, T., PAC Learning, in Encyclopedia of Machine Learning and Data Mining, C. Sammut and G.I. Webb, eds., Springer US, Boston, MA, 2017, pp. 949-959. · Zbl 1434.68001 |
| [33] | Zhang, R., Zhang, S., Muthuraman, S., and Jiang, J., One class support vector machine for anomaly detection in the communication network performance data, in Proceedings of the 5th Conference on Applied Electromagnetics, Wireless and Optical Communications, ELECTROSCIENCE’07, Tenerife, Canary Islands, Spain, World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, Wisconsin, USA, 2007, pp. 31-37. Available at http://dl.acm.org/citation.cfm?id=1503549.1503556. |
| [34] | Zhang, Y., Meratnia, N., and Havinga, P., Adaptive and online one-class support vector machine-based outlier detection techniques for wireless sensor networks, in 2009 International Conference on Advanced Information Networking and Applications Workshops, Bradford, UK, May, 2009, pp. 990-995. |
| [35] | Zhu, F.; Yang, J.; Gao, C.; Xu, S.; Ye, N.; Yin, T., A weighted one-class support vector machine, Neurocomputing, 189, 1-10 (2016) · doi:10.1016/j.neucom.2015.10.097 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
