16781216
Fast hierarchical clustering and its validation
Clustering is the task of grouping similar objects into clusters. A prominent and useful class of algorithm is hierarchical agglomerative clustering (HAC) which iteratively agglomerates the closest pair until all data points belong to one cluster. It outputs a dendrogram showing all N levels of agglomerations where N is the number of objects in the dataset. However, HAC methods have several drawbacks: (1) high time and memory complexities for clustering, and (2) inefficient and inaccurate cluster validation. In this paper we show that these drawbacks can be alleviated by closely studying the dendrogram. Empirical study shows that most HAC algorithms follow a trend where, except for a number of top levels of the dendrogram, all lower levels agglomerate clusters which are very small in size and close in proximity to other clusters. Methods are proposed that exploit this characteristic to reduce the time and memory complexities significantly and to make validation very efficient and accurate. Analyses and experiments show the effectiveness of the proposed method.
14543078
Resource description framework: metadata and its applications
Universality, the property of the Web that makes it the largest data and information source in the world, is also the property behind the lack of a uniform organization scheme that would allow easy access to data and information. A semantic web, wherein different applications and Web sites can exchange information and hence exploit Web data and information to their full potential, requires the information about Web resources to be represented in a detailed and structured manner. Resource Description Framework (RDF), an effort in this direction supported by the World Wide Web Consortium, provides a means for the description of metadata which is a necessity for the next generation of interoperable Web applications. The success of RDF and the semantic web will depend on (1) the development of applications that prove the applicability of the concept, (2) the availability of application interfaces which enable the development of such applications, and (3) databases and inference systems that exploit RDF to identify and locate most relevant Web resources. In addition, many practical issues, such as security, ease of use, and compatibility, will be crucial in the success of RDF. This survey aims at providing a glimpse at the past, present, and future of this upcoming technology and highlights why we believe that the next generation of the Web will be more organized, informative, searchable, accessible, and, most importantly, useful. It is expected that knowledge discovery and data mining can benefit from RDF and the Semantic Web.
7193073
A selective sampling approach to active feature selection
Feature selection, as a preprocessing step to machine learning, has been very effective in reducing dimensionality, removing irrelevant data, increasing learning accuracy, and improving result comprehensibility. Traditional feature selection methods resort to random sampling in dealing with data sets with a huge number of instances. In this paper, we introduce the concept of active feature selection, and investigate a selective sampling approach to active feature selection in a filter model setting. We present a formalism of selective sampling based on data variance, and apply it to a widely used feature selection algorithm Relief. Further, we show how it realizes active feature selection and reduces the required number of training instances to achieve time savings without performance deterioration. We design objective evaluation measures of performance, conduct extensive experiments using both synthetic and benchmark data sets, and observe consistent and significant improvement. We suggest some further work based on our study and experiments.
40702608
Feature Selection for Clustering
Clustering is an important data mining task. Data mining often concerns large and high-dimensional data but unfortunately most of the clustering algorithms in the literature are sensitive to largeness or high-dimensionality or both. Different features affect clusters differently, some are important for clusters while others may hinder the clustering task. An efficient way of handling it is by selecting a subset of important features. It helps in finding clusters efficiently, understanding the data better and reducing data size for efficient storage, collection and processing. The task of finding original important features for unsupervised data is largely untouched. Traditional feature selection algorithms work only for supervised data where class information is available. For unsupervised data, without class information, often principal components (PCs) are used, but PCs still require all features and they may be difficult to understand. Our approach: first features are ranked according to their importance on clustering and then a subset of important features are selected. For large data we use a scalable method using sampling. Empirical evaluation shows the effectiveness and scalability of our approach for benchmark and synthetic data sets.
8827382
Efficient Hierarchical Clustering Algorithms Using Partially Overlapping Partitions
Clustering is an important data exploration task. A prominent clustering algorithm is agglomerative hierarchical clustering. Roughly, in each iteration, it merges the closest pair of clusters. It was first proposed way back in 1951, and since then there have been numerous modifications. Some of its good features are: a natural, simple, and non-parametric grouping of similar objects which is capable of finding clusters of different shape such as spherical and arbitrary. But large CPU time and high memory requirement limit its use for large data. In this paper we show that geometric metric (centroid, median, and minimum variance) algorithms obey a 90-10 relationship where roughly the first 90iterations are spent on merging clusters with distance less than 10the maximum merging distance. This characteristic is exploited by partially overlapping partitioning. It is shown with experiments and analyses that different types of existing algorithms benefit excellently by drastically reducing CPU time and memory. Other contributions of this paper include comparison study of multi-dimensional vis-a-vis single-dimensional partitioning, and analytical and experimental discussions on setting of parameters such as number of partitions and dimensions for partitioning.
5365583
NeuroRule: A Connectionist Approach to Data Mining
Classification, which involves finding rules that partition a given da.ta set into disjoint groups, is one class of data mining problems. Approaches proposed so far for mining classification rules for large databases are mainly decision tree based symbolic learning methods. The connectionist approach based on neura.l networks has been thought not well suited for data mining. One of the major reasons cited is that knowledge generated by neural networks is not explicitly represented in the form of rules suitable for verification or interpretation by humans. This paper examines this issue. With our newly developed algorithms, rules which are similar to, or more concise than those generated by the symbolic methods can be extracted from the neural networks. The data mining process using neural networks with the emphasis on rule extraction is described. ExperimenM results and comparison with previously published works are presented.
34797702
Implicit Runge–Kutta methods based on Lobatto quadrature formula
Using W-transformation of Hairre and Wanner, high-order implicit Runge–Kutta (RK) methods based on Lobatto quadrature are studied. Methods constructed and presented include and extend the existing Lobatto III type RK methods. Two to four stages general Lobatto III methods with three parameters α, β, γ are constructed, and a particular one-parameter family Lobatto III C(γ) method is also presented.
6157335
Beating Common Sense into Interactive Applications
A long-standing dream of artificial intelligence has been to put commonsense knowledge into computers -- enabling machines to reason about everyday life. Some projects, such as Cyc, have begun to amass large collections of such knowledge. However, it is widely assumed that the use of common sense in interactive applications will remain impractical for years, until these collections can be considered sufficiently complete and commonsense reasoning sufficiently robust. Recently, at the Massachusetts Institute of Technology's Media Laboratory, we have had some success in applying commonsense knowledge in a number of intelligent interface agents, despite the admittedly spotty coverage and unreliable inference of today's commonsense knowledge systems. This article surveys several of these applications and reflects on interface design principles that enable successful use of commonsense knowledge.
893749
A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks
Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm
6771108
Fault-Tolerant Relay Node Placement in Wireless Sensor Networks
The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in an Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1 the network is connected, 2 the network is 2-connected. For case one, we propose a 6+e-approximation algorithm for any e>0 with polynomial running time when e is fixed. For case two, we propose two approximation algorithms with 24+e and 6/T+12+e, respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors.
653966
Fan-Type Theorem for Long Cycles Containing a Specified Edge
In this paper, we prove that if G is 3-connected noncomplete graph of order n satisfying min{max{d(u),d(v)}:d(u,v)=2}=μ, then for each edge e, G has a cycle containing e of length at least min{n,2μ}, unless G is a spanning subgraph of Kμ + Kcn−μ or K3+(lKμ−2∪Ks), where n=l(μ−2)+s+3,1≤s≤μ−2.