| Popis: |
Çok gruplu veri sınıflandırması, verinin çoklu gruplara atanmasını içeren gözetimli bir makina öğrenmesi problemidir. Veri sınıflandırması problemleri için eğitim kümesinin hiperkutu, hiperdüzlem ve çokyüzlü bölgeler aracılığıyla ayrılmasına dayalı çeşitli yöntemler bulunmaktadır. Çokyüzlü yaklaşımlar ya ikili sınıflandırma problemi için tasarlanmıştır ya da global en iyi çözüm üstüne odaklanmamıştır. Hiperkutu yöntemleri modelin veriye uydurulması açısından kısıtlayıcıdır. Bununla birlikte, eğitim modelleri en iyi sınıflandırıcıların kurulması için karmaşıktırlar ve belli büyüklüğe kadar olan örneklere uygulanabilirler.Çok gruplu veri sınıflandırması problemini bir karma tamsayılı doğrusal programlama (KTDP) modeli kullanarak ele almaktayız. Her bir grubun veri kümesini, farklı grupların altkümeleri bir hiperdüzlemle ayrılabilecek şekilde altkümelere bölüyoruz. Bir altkümeyi ayıran hiperdüzlemler çokyüzlü bir bölge oluşturmaktadır ve farklı grupların bölgeleri ayrıktır. En iyi ayrışmayı bulmak için bölge sayısı ve yanlış sınıflandırılan veri noktalarının toplamını en azlayan bir KTDP modeli kullanılmaktadır. Çizge teorisine dayanan bir ön işleme aşaması, grupların çiftli ayrımını dikkate akarak problemi ayrıştırmak ya da basitleştirmek amacıyla önerilmektedir. Her bir veri kümesi için grup çiftlerinin doğrusal ayrıştırılabilirlik ilişkisini temsil eden bir yönsüz çizge olduğunu gösterdik. Çizgenin bağlı bileşenleri oluşturulur ve düğüm kümesinde birden fazla eleman olan her bir bağlı bileşen için KTDP modeli çözülür. Bağlı bileşenlerin en iyi çözümlerinin bütününden yola çıkarak ana KTDP modeli için eşdeğer bir en iyi çözüm bulunduğunu gösterdik.Bununla birlikte, doğrusal ayrılabilir altkümeleri oluşturmak için KTDP tabanlı yeni bir algoritma sunmaktayız. Her bir özyinelemede, yeni altkümenin eleman sayısını enbüyüten bir KTDP modeli kullanarak atanmamış örnek kümesinden örnek altkümesi oluşturmaktayız. Diğer grupların altkümelerinden doğrusal ayrılabilir olan yeni oluşturulan altküme atanmamış örnek kümesinden kaldırılır. Geriye kalan örnekler yeni altkümeler oluşturmak için kullanılır ve algoritma örneklerin tamamı atandığında sonlanır. Algoritma tarafından üretilen farklı grupların altkümelerinin doğrusal ayrılabilir olduğunu ve genel KTDP için uygun çözüm oluşturmak için kullanılabileceğini gösterdik. Buna ek olarak, algoritma birkaç özyinelemeyle veri kümesini eksiltmek için kullanılabilir, böylelikle KTDP modeli sadeleştirilmiş olur.Test aşaması için altkümelerin dışbükey zarflarını ve hiperdüzlemlerle tanımlanan çokyüzlü bölgeleri temel alan sınıflandırıcılar kurduk. Hiperdüzlemler destek vektör makinelerindeki gibi ayıracın genişliğinin enbüyütülmesiyle oluşturulur. Yaklaşımımızı 15 yapay veri kümesi ve 52 denektaşı problem üzerinde değerlendirdik ve literatürdeki yöntemlerle karşılaştırdık. Önerilen sınıflandırıcılarla tamamlanan eniyileme tabanlı yaklaşımımızın tahmin ölçüsü açısından rekabet eden sonuçlar verdiği neticesine vardık. Multi-class data classification is a supervised machine learning problem that involves assigning data to multiple groups. There are various methods for data classification problems that are based on the separation of training sets by means of hyperboxes, hyperplanes and polyhedral regions. Polyhedral approaches are either designed for binary classification problem or do not focus on global optimal solutions. Hyperbox methods are restrictive in fitting a model to the data. In addition, the training models are complex to build optimal classifiers and they are applicable on instances up to a certain size.We address the multi-class data classification problem by a mixed integer linear programming model (MILP). We split data set of each class into subsets such that the subsets of different classes are separable by a hyperplane. The hyperplanes that separate a subset form a polyhedral region and the regions of different classes are disjoint. A MILP model is used to find the optimal separation by minimizing the total number of regions and misclassified data points. A preprocessing step, which is based on graph theory, is proposed to decompose or simplify the problem considering pairwise separation of classes. We have shown that there is an undirected graph for each dataset representing the linear separability relation of class pairs. Connected components of the graph is formed and MILP model is solved for each connected component with more than one element in the vertex set. We have shown that for the collection of the optimal solutions to the connected components, there is an equivalent optimal solution to the main MILP model.In addition, we present a novel MILP-based algorithm to form the linearly separable subsets. At each iteration we form a subset of samples out of the set of unassigned samples by a MILP model that maximizes the cardinality of the new subset. The generated subset which is linearly separable from the subsets of other classes is removed from the unassigned sample set. The rest of the samples are used for generating new subsets and the algorithm terminates when all the samples are assigned. We have shown that the subsets of different classes generated by the algorithm are linearly separable and can be used to construct a feasible solution to the general MILP model. Furthermore the algorithm can be used to reduce the dataset in few iterations so that MILP model is simplified.We build classifiers based on the convex hulls of the subsets and the polyhedral regions defined by the hyperplanes for the testing phase. The hyperplanes are generated by maximizing the margin as in the support vector machines. We evaluated our approach on 15 artificial datasets and 52 benchmark problems and compared with the methods from the literature. We conclude that our optimization based approach complemented with the proposed classifiers, provides competitive results in terms of prediction accuracy. 203 |
