Dimension reduction and feature selection are fundamental tools for machine learning and data mining. Most existing methods, however, assume that objects are represented by a single vectorial descriptor. In reality, some description methods assign unordered sets or graphs of vectors to a single object, where each vector is assumed to have the same number of dimensions, but is drawn from a different probability distribution. Moreover, some applications (such as pose estimation) may require the recognition of individual vectors (nodes) of an object. In such cases it is essential that the nodes within a single object remain distinguishable after dimension reduction. In this paper we propose new discriminant analysis methods that are able to satisfy two criteria at the same time: separating between classes and between the nodes of an object instance. We analyze and evaluate our methods on several different synthetic and real-world datasets.
The relationships between elements of coefficient matrix, elements of vector and elements of vector in general binary problem are considered. Some of them allow us to establish the values of selected elements of feasible or optimal vector . This procedure reduces the dimension of basic problem and can be install in branch and bound method. It gives positive effects.
PL
Przedstawiono kilka własności problemów binarnych, które pozwalają redukować wymiar zadania poprzez wyszukiwanie i ustalanie wartości niektórych zmiennych. W dopuszczalnych wektorach binarnych danego zadania wartości te muszą być przyjęte. Procedurę wykorzystującą te własności wmontowano w metodę podziału i oszacowań, w szczególności do algorytmu przeglądu pośredniego dla zadań binarnych.
The paper deals with the issue of reducing the dimension and size of a data set (random sample) for exploratory data analysis procedures. The concept of the algorithm investigated here is based on linear transformation to a space of a smaller dimension, while retaining as much as possible the same distances between particular elements. Elements of the transformation matrix are computed using the metaheuristics of parallel fast simulated annealing. Moreover, elimination of or a decrease in importance is performed on those data set elements which have undergone a significant change in location in relation to the others. The presented method can have universal application in a wide range of data exploration problems, offering flexible customization, possibility of use in a dynamic data environment, and comparable or better performance with regards to the principal component analysis. Its positive features were verified in detail for the domain’s fundamental tasks of clustering, classification and detection of atypical elements (outliers).
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Standard methods of multivariate statistics fail in the analysis of high-dimensional data. This paper gives an overview of recent classification methods proposed for the analysis of high-dimensional data, especially in the context of molecular genetics. We discuss methods of both biostatistics and data mining based on various background, explain their principles, and compare their advantages and limitations. We also include dimension reduction methods tailor-made for classification analysis and also such classification methods which reduce the dimension of the computation intrinsically. A common feature of numerous classification methods is the shrinkage estimation principle, which has obtained a recent intensive attention in high-dimensional applications.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Marginal Fisher Analysis (MFA) is a novel dimensionality reduction algorithm. However, the two nearest neighborhood parameters are difficult to select when constructing graphs. In this paper, we propose a nonparametric method called Marginal Discriminant Projection (MDP) which can solves the problem of parameters selection in MFA. Experiment on several benchmark datasets demonstrated the effectiveness of our proposed method, and appreciate performance was achieved when applying on coal mine safety data dimensionality reduction.
PL
W artykule zaproponowano nieparametryczna metodę nazwaną MDOP (marginal discriminant projection) która pomaga rozwiązać problem selekcji danych w algorytmie MFA (marginal Fisher analysis). Metodę zastosowano do redukcji danych w systemach bezpieczeństwa klopalni węglowych.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Przedmiotem niniejszego artykułu jest wielowymiarowa analiza danych, która realizowana jest poprzez uzupełnienie standardowych procedur ekstrakcji cech odpowiednimi miarami zachowania struktury topologicznej zbioru. Podejście to motywuje obserwacja, że nie wszystkie elementy zbioru pierwotnego w toku redukcji są właściwie zachowane w ramach reprezentacji w przestrzeni o zmniejszonej wymiarowości. W artykule przedstawiono najpierw istniejące miary zachowania topologii zbioru, a następnie omówiono możliwości ich włączenia w klasyczne procedury eksploracyjnej analizy danych. Załączono również ilustracyjne przykłady użycia omawianego podejścia w zadaniach analizy skupień i klasyfikacji.
EN
This paper deals with high-dimensional data analysis accomplished through supplementing standard feature extraction procedures with topology preservation measures. This approach is based on an observation that not all elements of an initial dataset are equally preserved in its low-dimensional embedding space representation. The contribution first overviews existing topology preservation measures, then their inclusion in the classical methods of exploratory data analysis is discussed. Finally, some illustrative examples of presented approach in the tasks of cluster analysis and classification are given.
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Dimension reduction is an important topic in data mining and machine learning. Especially dimension reduction combined with feature fusion is an effective preprocessing step when the data are described by multiple feature sets. Canonical Correlation Analysis (CCA) and Discriminative Canonical Correlation Analysis (DCCA) are feature fusion methods based on correlation. However, they are different in that DCCA is a supervised method utilizing class label information, while CCA is an unsupervised method. It has been shown that the classification performance of DCCA is superior to that of CCA due to the discriminative power using class label information. On the other hand, Linear Discriminant Analysis (LDA) is a supervised dimension reduction method and it is known as a special case of CCA. In this paper, we analyze the relationship between DCCA and LDA, showing that the projective directions by DCCA are equal to the ones obtained from LDA with respect to an orthogonal transformation. Using the relation with LDA, we propose a new method that can enhance the performance of DCCA. The experimental results show that the proposed method exhibits better classification performance than the original DCCA.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The dimensionality and the amount of data that need to be processed when intensive data streams are observed grow rapidly together with the development of sensors arrays, CCD and CMOS cameras and other devices. The aim of this paper is to propose an approach to dimensionality reduction as a first stage of training RBF nets. As a vehicle for presenting the ideas, the problem of estimating multivariate probability densities is chosen. The linear projection method is briefly surveyed. Using random projections as the first (additional) layer, we are able to reduce the dimensionality of input data. Bounds on the accuracy of RBF nets equipped with a random projection layer in comparison to RBF nets without dimensionality reduction are established. Finally, the results of simulations concerning multidimensional density estimation are briefly reported.
The paper presents a novel method of reducing the dimensionality of large datasets (e.g. human faces databases). It does not incorporate any usual pre-processing stage (like down-scaling or filtering). Its main advantage is associated with efficient representation of images leading to the accurate recognition. The reduction is realized by modified Linear Discriminant Analysis. In the paper, the authors present its mathematical principles together with some results of practical recognition experiments on popular facial databases (ORL, BioID).
10
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W monografii przedstawiono metodykę konstruowania i badania algorytmów decyzyjnych, która jest nowym podejściem do problemów przetwarzania i podejmowania decyzji na podstawie wielowymiarowych obserwacji. Polega ona na transformacji danych do postaci jednowymiarowej za pomocą quasi-odwrotności dobrze dobranej krzywej wypełniającej, a następnie na rozwiązaniu jednowymiarowego problemu decyzyjnego. W efekcie transformacji uzyskuje się redukcję wymiaru problemu i jego znaczącą kompresję, bez utraty istotnych informacji przestrzennych zawartych w danych wielowymiarowych. Prowadzi to do możliwości konstruowania szybkich algorytmów podejmowania decyzji, które mogą działać na bieżąco, na podstawie aktualnie uzyskiwanych obserwacji. Podejście to rozwija kierunki badań prowadzone obecnie w automatyce, polegające na projektowaniu elastycznych systemów, łączących konwencjonalne techniki z różnorodnymi metodami uczenia, które wykorzystują zgromadzone obserwacje pomiarowe i pozwalają na korygowanie pracy systemu. Opracowano układy równań funkcyjnych i rekurencyjne metody wyznaczania odwzorowań quasi-odwrotnych do wielowymiarowych krzywych typu Peano, Hilberta i Sierpińskiego. Wykazano, że transformacje te zachowują istotne informacje statystyczne zawarte w wielowymiarowych danych. Wyprowadzono teoretyczną zależność między wymiarami fraktalnymi danych przed i po transformacji. Udowodniono, że badana klasa krzywych wypełniających zachowuje ryzyko Bayesa dla dowolnego rozkładu obserwacji o ograniczonym nośniku. Zdefiniowano nową klasę krzywych wypełniających, które zachowują zadaną miarę probabilistyczną i wykorzystano ją w problemach kwantyzacji. Zbadano asymptotyczną wartość dystorsji wektorowych kwantyzatorów otrzymanych poprzez redukcję wymiaru obserwacji. Zdefiniowano też pojęcie powierzchni wypełniającej oraz odpowiednie odwzorowanie quasi-odwrotne oraz zbadano ich podstawowe własności. Wprowadzono pojęcie multi-karty, która jest uogólnieniem tradycyjnej karty kontrolnej i pozwala oceniać stan wielowymiarowego procesu na podstawie przekształconych, skalarnych obserwacji, zbadano też jej własności. Otrzymane rezultaty teoretyczne zastosowano w odniesieniu do wielowymiarowych problemów decyzyjnych, dotyczących rozpoznawania i monitorowania stanu procesu, diagnostyki i problemów statystycznego wykrywania zmian w procesie oraz problemów kwantyzacji. Zaowocowało to powstaniem szczegółowych metod, spełniających nałożone wymagania teoretyczne. W wielu przypadkach zaproponowano także proste obliczeniowo algorytmy heurystyczne. Podstawową cechą wszystkich opracowanych metod jest mała złożoność obliczeniowa procesu podejmowania decyzji.
EN
In the monograph, a methodology of constructing and validating decision algorithms is proposed. This methodology forms a new approach to the problems of multidimensional decision making. The main idea is to transform each multivariate observation to univariate one, using a quasi-inverse of a carefully chosen space-filling curve as a transformation. Then, the decision problem is solved for univariate data. The advantages of using such transformations lie in the dimensionality reduction and in data compression without loosing the information associated with the spatial structure of multivariate observations. These advantages allow us to construct fast decision algorithms, which can be easily implemented as on-line methods. The methodology proposed is contained in the stream of research which explores novel strategies for control of complex industrial processes. These strategies are directed towards the design of flexible control systems, which combine model--based classical techniques with a variety of learning based methods. The learning is based on past observations, which are used for a control system adaptation and enhancement. Important prerequisites for developing the decision making methodology are criteria for selecting space-filling curves and algorithms for calculating their quasi--inverses as quickly as possible. In the monograph, a method of forming functional equations for space-filling curves and their quasi-inverses is developed for the Peano, the Hilbert and the Sierpinski curves. It is also proved that these functional equations can be solved by backward recursions, providing exact values of the curves on dense sets in a finite number of iterations. It is also shown that the space-filling based transformations retain essential statistical information, which is important in decision-making. In particular, it is proved that the Bayes risk is invariant under these transformations for every distribution which has a bounded support. Also a fractal dimension, scaled by the dimension of the data, occurs to be invariant. A new class of curves which retain a prescribed probability measure is defined and used for solving vector quantization problems. In particular, an asymptotic distortion error of quantizers is investigated using the dimension error techniques. The notion of the space-filling curves is generalized also in another direction, namely, space-filling surfaces and their quasi-inverses are denned and investigated. The above theoretical results form foundations for deriving new classes of decision-making algorithms, which are applicable in a variety of control system tasks. In particular, the notion of a multi-chart is introduced, together with a new method of detecting system faults. In addition to new fast algorithms of vector quantization and pattern recognition, also their asymptotics is investigated, providing a theoretical foundations for their use in monitoring and diagnosis of a system state. In some cases simple heuristic algorithms, having solid support in the simulations, are also discussed. The important feature of all the decision algorithms, resulting from the methods considered in the monograph, is their low computational complexity.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.