Linear and non linear dimensionality reduction for distributed knowledge discovery

Abstract

An increasing number of contemporary applications produce massive volumes of very high dimensional data. In scientific databases, for example, it is common to encounter large sets of observations, represented by hundreds or even thousands of coordinates. Unfortunately the rate of data generation and accumulation significantly outperforms our ability to explore and analyse it. Nevertheless, in order to extract knowledge from these datasets, we need to access the underlying, hidden information. However, the size and complexity of these collections makes their processing and analysis impractical or even ineffective [13, 47]. Therefore, scaling up knowledge discovery algorithms for data of both high dimensionality and cardinality has been recently recognized as one of the top-10 problems in data mining research [95]. In parallel, the evolution of the internet as well as the emergence of novel applications, such as peer-to-peer systems, has led to an unprecedented distribution of available information. Data is dispersed among network nodes, making the cost of centralizing and subsequent processing prohibitive. Consequently, distributed data mining and distributed knowledge discovery have also emerged as highly challenging tasks [95]. Nevertheless, the vast amount of generated data dictates methods that are fast, exhibit low requirements in terms of computational resources and can be applied to various network setups. Motivated by the previous analysis, this thesis attempts to provide a solution through the definition of efficient and effective dimensionality reduction algorithms. The proposed methods exhibit minor requirements in terms of computational resources without compromising the quality of the produced results; therefore can be exploited in the context of centralized and distributed preprocessing for knowledge discovery. Towards this end, • We introduce FEDRA1 (Chapter 3, [62, 63]), a dimensionality reduction algorithm which poses minimum time and space requirements and is ideal for large datasets of particularly high cardinality and dimensionality. • Inspired by the nature of landmark based dimensionality reduction algorithms (Chapter 2) we introduce the distributed adaptation of FEDRA ([62, 61]) and extend its underlying methodology in order to derive a framework for the decentralization of any landmark based dimensionality reduction algorithm (Chapter 3, Section 3.4) • We propose a distributed non linear dimensionality reduction algorithm, the Distributed Isomap ( Chapter 4, [66, 65]) which to the best of our knowledge comprises the first of this kind. Additionally, motivated by recent research results on text-mining ([41, 17, 101, 78, 71]) we propose its application for hard dimensionality reduction problems related with text-mining. • Finally, we introduce X-SDR2 (Chapter 5, [64]), a prototype that enables the integration and evaluation of any dimensionality reduction algorithm. X-SDR is an open source tool that supports the evaluation of methods through experimentation on artificial and real world datasets thus promoting itself as an ideal candidate platform for research and teaching in academia.