Spectral clustering methods are claimed to possess ability to represent clusters of diverse shapes, densities etc.They constitute an approximation to graph cuts of various types (plain cuts, normalized cuts, ratio cuts).They are applicable to unweighted and weighted similarity graphs.We perform an evaluation of these capabilities for clustering tasks of increasing complexity.

Abstract This paper performs an investigation of Kleinberg’s axioms (from both an intuitive and formal standpoint) as they relate to the well-known k-mean clustering method. The axioms, as well as a novel variations thereof, are analyzed in Euclidean space. A few natural properties are proposed, resulting in k-means satisfying the intuition behind Kleinberg’s axioms (or, rather, a small, and natural variation on that intuition). In particular, two variations of Kleinberg’s consistency property are proposed, called centric consistency and motion consistency. It is shown that these variations of consistency are satisfied by k-means.

In a former paper [1] the concept of Bipartite PageRank was introduced and a theorem on the limit of authority flowing between nodes for personalized PageRank has been generalized. In this paper we want to extend those results to multimodal networks. In particular we deal with a hypergraph type that may be used for describing multimodal network where a hyperlink connects nodes from each of the modalities. We introduce a generalisation of PageRank for such graphs and define the respective random walk model that can be used for computations. We state and prove theorems on the limit of outflow of authority for cases where individual modalities have identical and distinct damping factors.

In this paper we make a comparison of two NMF based techniques of dataset characterization: clustering and hulling. The characteristics of a dataset should be understood as describing the content of a data set through several characteristic representatives. Hulling (defined later) characterizes the data by saying that the data points are somewhere between the representatives, while clustering characterizes the data by saying that the data points are close to one or the other representative. The precision of such a characteristic will be measured as a deviation from the idea of characterization, i.e. the distance of the actual data points from the closest representatives in the case of clustering and from the interior of the hull spanned by the representatives. We show that for low-dimensional data the hull-based characterization precision is much better than in case of clustering. Clustering and hulling are two examples of sophisticated optimization problems. Evolutionary algorithms are an excellent tool for solving such problems. However, in the case of large, high-dimensional data sets, their usefulness decreases. In this paper, we discuss heuristics for hulling for massive data. We hope that it will inspire the creation of an effective evolutionary algorithm dedicated to solving such problems.

Abstract Kleinberg introduced an axiomatic system for clustering functions. Out of three axioms, he proposed, two (scale invariance and consistency) are concerned with data transformations that should produce the same clustering under the same clustering function. The so-called consistency axiom provides the broadest range of transformations of the data set. Kleinberg claims that one of the most popular clustering algorithms, k-means does not have the property of consistency. We challenge this claim by pointing at invalid assumptions of his proof (infinite dimensionality) and show that in one dimension in Euclidean space the k-means algorithm has the consistency property. We also prove that in higher dimensional space, k-means is, in fact, inconsistent. This result is of practical importance when choosing testbeds for implementation of clustering algorithms while it tells under which circumstances clustering after consistency transformation shall return the same clusters. Two types of remedy are proposed: gravitational consistency property and dataset consistency property which both hold for k-means and hence are suitable when developing the mentioned testbeds.

We prove in this paper that the expected value of the objective function of the k-means++ algorithm for samples converges to population expected value. As k-means++, for samples, provides with constant factor approximation for k-means objectives, such an approximation can be achieved for the population with increase of the sample size. This result is of potential practical relevance when one is considering using subsampling when clustering large data sets (large data bases).

Abstract The widely discussed and applied Johnson–Lindenstrauss (JL) Lemma has an existential form saying that for each set of data points Q in n-dimensional space, there exists a transformation f into an $$n'$$ n′ -dimensional space ( $$n' n′

This paper, constituting an extension to the conference paper [1], corrects the proof of the Theorem 2 from the Gower’s paper [2, page 5]. The correction is needed in order to establish the existence of the kernel function used commonly in the kernel trick e.g. for k-means clustering algorithm, on the grounds of distance matrix. The correction encompasses the missing if-part proof and dropping unnecessary conditions.

This paper investigates the application of consensus clustering and meta-clustering to the set of all possible partitions of a data set. We show that when using a “complement” of Rand Index as a measure of cluster similarity, the total-separation partition, putting each element in a separate set, is chosen.

Pattern-based methods of IS-A relation extraction relyheavily on so called Hearst patterns.These are ways of expressing instance enumerations of a class in natural language.While these lexico-syntactic patterns prove quite useful, they may not capture all taxonomical relations expressed in text.Therefore in this paper we describe a novel method of IS-A relation extraction from patterns, which uses morpho-syntactical annotations along with grammatical case of noun phrases that constitute entities participating in IS-A relation.We also describe a method for increasing the number of extracted relations that we call pseudosubclass boosting which has potential application in any patternbased relation extraction method.Experiments were conducted on a corpus of about 0.5 billion web documents in Polish language.

Latency of user-based and item-based recommenders is evaluated. The two algorithms can deliver high quality predictions in dynamically changing environments. However, their response time depends not only on the size, but also on the structure of underlying datasets. This constitutes a major drawback when compared to two other competitive approaches i.e. content-based and model-based systems. Therefore, we believe that there exists a need for comprehensive evaluation of the latency of the two algorithms. During a typical worst case scenario analysis of collaborative filtering algorithms two assumption are made. The first assumption says that data are stored in dense collections. The second assumption states that large amount of computations can be performed in advance during the training phase. As a result it is advised to deploy user-based system when the number of users is relatively small. Item-based algorithms are believed to have better technical properties when the number of items is small. We consider a situation in which the two assumptions are not necessarily met. We show that even though the latency of the two methods depends heavily on the proportion of users to items, this factor does not differentiate the two methods. We evaluate the algorithms with several real-life datasets. We augment the analysis with both graph-theoretical and experimental techniques.

A reliable wireless ad hoc network has to be secured against a selfish behavior. In such a network environment nodes have no incentives to participate actively in packet forwarding. Thus, selfishness is a rational choice for network participants. In this paper we demonstrate how using a strategy based packet forwarding approach can increase throughput in such networks and at the same time can minimize the usage of resources of participating nodes. The strategy defines conditions under which packets are being forwarded. It is based on the notions of trust and activity of the node originating the packet. We demonstrate that selfish behavior becomes unattractive when a certain number of nodes is using this approach. A genetic algorithm (GA) is applied to evolve good strategies, while for evaluation purposes of the strategies a game theoretical model of the ad hoc network is used.

Cooperation enforcement is one of the key issues in ad hoc networks. In this paper we proposes a new strategy driven approach that aims at discouraging selfish behavior among network participants. Each node is using a strategy that defines conditions under which packets are being forwarded. Such strategy is based on the notion of trust and activity of the source node of the packet. This way network participants are forced to forward packets and to reduce the amount of time spent in a sleep mode. To evaluate strategies we use a new game theory based model of an ad hoc network. A genetic algorithm (GA) is applied to find good strategies. Experimental results show that our approach makes selfish behavior unattractive.

In this paper we address the problem of selfish behavior in ad hoc networks. We propose a strategy driven approach which aims at enforcing cooperation between network participants. Each node (player) is using a strategy that defines conditions under which packets are being forwarded. Such strategy is based on the notion of trust and activity of the source node of the packet. This way network participants are enforced to forward packets and to reduce the amount of time of being in a sleep mode. To evaluate strategies we use a new game theory based model of an ad hoc network. This model has some similarities with the iterated prisoner's dilemma under the random pairing game where randomly chosen players receive payoffs that depend on the way they behave. Our model of the network also includes a simple reputation collection and trust evaluation mechanisms. A genetic algorithm (GA) is applied to find good strategies. Experimental results show that approach can successfully enforce cooperation among ad hoc networks participants.

The paper presents an approach to knowledge integration coming from different databases. It is based on model tree construction from databases with both discrete and continuous attributes. The methodology of model trees is explained. Some information on implementation issues is given and preliminary results on a real dataset are presented.

In the literature, the optimization problem to identify a set of composite hypotheses H, which will yield the k largest P(H|Se ) where a composite hypothesis is an instantiation of all the nodes in the network except the evidence nodes [17] is of sig