The traditional paradigm in data analysis typically assumes that each data instance is independent of another. However, often data instances may be connected or linked to other instances via various types of relationships. The instances themselves may be described by various attributes. What emerges is a network or graph of instances (or nodes), connected by links (or edges). Both the nodes and edges in the graph may have several attributes that may be numerical or categorical, or even more complex (e.g., time series data). Increasingly, today's massive data is in the form of such graphs or networks. Examples include the World Wide Web (with its Web pages and hyperlinks), social networks (wikis, blogs, tweets, and other social media data), semantic networks (ontologies), biological networks (protein interactions, gene regulation networks, metabolic pathways), citation networks for scientific literature, and so on. In this chapter we look at the analysis of the link structure in graphs that arise from these kinds of networks. We will study basic topological properties as well as models that give rise to such graphs.

GRAPH CONCEPTS

Graphs

Formally, a graph G = (V, E) is a mathematical structure consisting of a finite nonempty set V of vertices or nodes, and a set E ⊆ V × V of edges consisting of unordered pairs of vertices.

Given n points in a d-dimensional space, the goal of hierarchical clustering is to create a sequence of nested partitions, which can be conveniently visualized via a tree or hierarchy of clusters, also called the cluster dendrogram. The clusters in the hierarchy range from the fine-grained to the coarse-grained – the lowest level of the tree (the leaves) consists of each point in its own cluster, whereas the highest level (the root) consists of all points in one cluster. Both of these may be considered to be trivial clusterings. At some intermediate level, we may find meaningful clusters. If the user supplies k, the desired number of clusters, we can choose the level at which there are k clusters.

There are two main algorithmic approaches to mine hierarchical clusters: agglomerative and divisive. Agglomerative strategies work in a bottom-up manner. That is, starting with each of the n points in a separate cluster, they repeatedly merge the most similar pair of clusters until all points are members of the same cluster. Divisive strategies do just the opposite, working in a top-down manner. Starting with all the points in the same cluster, they recursively split the clusters until all points are in separate clusters. In this chapter we focus on agglomerative strategies. We discuss some divisive strategies in Chapter 16, in the context of graph partitioning.

Graph data is becoming increasingly more ubiquitous in today's networked world. Examples include social networks as well as cell phone networks and blogs. The Internet is another example of graph data, as is the hyperlinked structure of the World Wide Web (WWW). Bioinformatics, especially systems biology, deals with understanding interaction networks between various types of biomolecules, such as protein–protein interactions, metabolic networks, gene networks, and so on. Another prominent source of graph data is the Semantic Web, and linked open data, with graphs represented using the Resource Description Framework (RDF) data model.

The goal of graph mining is to extract interesting subgraphs from a single large graph (e.g., a social network), or from a database of many graphs. In different applications we may be interested in different kinds of subgraph patterns, such as subtrees, complete graphs or cliques, bipartite cliques, dense subgraphs, and so on. These may represent, for example, communities in a social network, hub and authority pages on the WWW, cluster of proteins involved in similar biochemical functions, and so on. In this chapter we outline methods to mine all the frequent subgraphs that appear in a database of graphs.

The representative-based clustering methods like K-means and expectation maximization are suitable for finding ellipsoid-shaped clusters, or at best convex clusters. However, for nonconvex clusters, such as those shown in Figure 15.1, these methods have trouble finding the true clusters, as two points from different clusters may be closer than two points in the same cluster. The density-based methods we consider in this chapter are able to mine such nonconvex clusters.

THE DBSCAN ALGORITHM

Density-based clustering uses the local density of points to determine the clusters, rather than using only the distance between points. We define a ball of radius ε around a point x ∈ Rd, called the ε-neighborhood of x, as follows:

Nε(x) = Bd(x, ε) = {y | δ(x,y) ≤ ε}

Here δ(x,y) represents the distance between points x and y, which is usually assumed to be the Euclidean distance, that is, δ(x, y) = ||x − y||2. However, other distance metrics can also be used.

For any point x ∈ D, we say that x is a core point if there are at least minpts points in its ε-neighborhood. In other words, x is a core point if |Nε(x)| ≥ minpts, where minpts is a user-defined local density or frequency threshold.

Introduction

Outlier detection is an important subject in machine learning and data analysis. The term outlier refers to abnormal observations that are inconsistent with the bulk of the data distribution [16, 32, 98, 240, 265, 266, 287]. Some sample applications are as follows.

1. • Detection of imposters or rejection of unauthorized access to computer networks.

2. • Genomic research – identifying abnormal gene or protein sequences.

3. • Biomedical, e.g. ECG arrythmia monitoring.

4. • Environmental safety detection, where outliers indicate abnormality.

5. • Personal safety, with security aids embedded in mobile devices.

For some real-world application examples, see e.g Hodge and Austin [98].

The standard approach to outlier detection is density-based, whereby the detection depends on the outlier's relationship with the bulk of the data. Many algorithms use concepts of proximity and/or density estimation in order to find outliers. However, in high-dimensional spaces the data become increasingly sparse and the notion of proximity/density has become less meaningful, and consequently model-based methods have become more appealing [1, 39]. It is also a typical assumption that a model is to be trained from only one type of (say, positive) training patterns, making it a fundamentally different problem, and thereby creating a new learning paradigm leading to one-class-based learning models.

SVM-type learning models are naturally amenable to outlier detection since certain support vectors can be identified as outliers.

Introduction

The objective of cluster discovery is to subdivide a given set of training data, X ≡ (x1, x2,…, xN}, into a number of (say K) subgroups. Even with unknown class labels of the training vectors, useful information may be extracted from the training dataset to facilitate pattern recognition and statistical data analysis. Unsupervised learning models have long been adopted to systematically partition training datasets into disjoint groups, a process that is considered instrumental for classification of new patterns. This chapter will focus on conventional clustering strategies with the Euclidean distance metric. More specifically, it will cover the following unsupervised learning models for cluster discovery.

1. • Section 5.2 introduces two key factors – the similarity metric and clustering strategy – dictating the performance of unsupervised cluster discovery.

2. • Section 5.3 starts with the basic criterion and develops the iterative procedure of the K-means algorithm, which is a common tool for clustering analysis. The convergence property of the K-means algorithm will be established.

3. • Section 5.4 extends the basic K-means to a more flexible and versatile expectation-maximization (EM) clustering algorithm. Again, the convergence property of the EM algorithm will be treated.

4. • Section 5.5 further considers the topological property of the clusters, leading to the well-known self-organizing map (SOM).

5. • Section 5.6 discusses bi-clustering methods that allow simultaneous clustering of the rows and columns of a data matrix.

Introduction

The rapid advances in information technologies, in combination with today's internet technologies (wired and mobile), not only have profound impacts on our daily lifestyles but also have substantially altered the long-term prospects of humanity. In this era of big data, diversified types of raw datasets with huge data-size are constantly collected from wired and/or mobile devices/sensors. For example, in Facebook alone, more than 250 million new photos are being added on a daily basis. The amount of newly available digital data more than doubles every two years. Unfortunately, such raw data are far from being “information” useful for meaningful analysis unless they are processed and distilled properly. The main purpose of machine learning is to convert the wealth of raw data into useful knowledge.

Machine learning is a discipline concerning the study of adaptive algorithms to infer from training data so as to extract critical and relevant information. It offers an effective data-driven approach to data mining and intelligent classification/prediction. The objective of learning is to induce optimal decision rules for classification/prediction or to extract the salient characteristics of the underlying system which generates the observed data. Its potential application domains cover bioinformatics, DNA expression and sequence analyses, medical diagnosis and health monitoring, brain–machine interfaces, biometric recognition, security and authentication, robot/computer vision, market analysis, search engines, and social network association.

In machine learning, the learned knowledge should be represented in a form that can readily facilitate decision making in the classification or prediction phase.

The traditional curse of dimensionality is often focused on the extreme dimensionality of the feature space, i.e. M. However, for kernelized learning models for big data analysis, the concern is naturally shifted to the extreme dimensionality of the kernel matrix, N, which is dictated by the size of the training dataset. For example, in some biomedical applications, the sizes may be hundreds of thousands. In social media applications, the sizes could be easily of the order of millions. This creates a new large-scale learning paradigm, which calls for a new level of computational tools, both in hardware and in software.

Given the kernelizability, we have at our disposal two learning models, respectively represented by two different kernel-induced vector spaces. Now our focus of attention should be shifted to the interplay between two kernel-induced representations. Even though the two models are theoretically equivalent, they could incur very different implementation costs for learning and prediction. For cost-effective system implementation, one should choose the lower-cost representation, whether intrinsic or empirical. For example, if the dimension of the empirical space is small and manageable, an empirical-space learning models will be more appealing. However, this will just be the opposite if the number of training vectors is extremely large, which is the case for the “big data” learning scenario. In this case, one must give a serious consideration to the intrinsic model whose cost can be controlled by properly adjusting the order of the kernel function.

Unsupervised cluster discovery is instrumental for data analysis in many important applications. It involves a process of partitioning the training dataset into disjoint groups. The performance of cluster discovery depends on several key factors, including the number of clusters, the topology of node vectors, the objective function for clustering, iterative learning algorithms (often with multiple initial conditions), and, finally, an evaluation criterion for picking the best result among multiple trials. This part contains two chapters: Chapter 5 covers unsupervised learning models employing the conventional Euclidean metric for vectorial data analysis while Chapter 6 focuses on the use of kernel-induced metrics and kernelized learning models, which may be equally applied to nonvectorial data analysis.

Chapter 5 covers several conventional unsupervised learning models for cluster discovery, including K-means and expectation-maximization (EM) learning models, which are presented in Algorithms 5.1 and 5.2, along with the respective proofs of the monotonic convergence property, in Theorems 5.1 and 5.2. By imposing topological sensitivity on the cluster (or node) structure, we can extend the basic K-means learning rule to the SOM learning model presented in Algorithm 5.3. Finally, for biclustering problems, where features and objects are simultaneously clustered, several useful coherence models are proposed.

Chapter 6 covers kernel-based cluster discovery, which is useful both for vectorial and for nonvectorial data analyses.

Machine learning has successfully led to many promising tools for intelligent data filtering, processing, and interpretation. Naturally, proper metrics will be required in order to objectively evaluate the performance of machine learning tools. To this end, this chapter will address the following subjects.

• It is commonly agreed that the testing accuracy serves as a more reasonable metric for the performance evaluation of a learned classifier. Section A.1 discusses several cross-validation (CV) techniques for evaluating the classification performance of the learned models.

• Section A.2 explores two important test schemes: the hypothesis test and the significance test.

Cross-validation techniques

Suppose that the dataset under consideration has N samples to be used for training the classfier model and/or estimating the classfication accuracy. Before the training phase starts, a subset of training dataset must be set aside as the testing dataset. The class labels of the test patterns are assumed to be unknown during the learning phase. These labels will be revealed only during the testing phase in order to provide the necessary guideline for the evaluation of the performance.

Some evaluation/validation methods are presented as follows.