8367210
Sensor Sequence Modeling for Driving
Intelligent systems in automobiles need to be aware of the driving and driver context. Available sensor data stream has to be modeled and monitored in order to do so. Currently there exist no building blocks for hierarchical modeling of driving. By semi-supervised segmentation such building blocks can be discovered. We call them drivemes in analogy to phonemes. More parsimonious modeling of driving becomes now possible.
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.
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.
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.
46834678
Efficient Search of Reliable Exceptions
Finding patterns from data sets is a fundamental task of data mining. If we categorize all patterns into strong, weak, and random, conventional data mining techniques are designed only to find strong patterns, which hold for numerous objects and are usually consistent with the expectations of experts. While such strong patterns are helpful in prediction, the unexpectedness and contradiction exhibited by weak patterns are also very useful although they represent a relatively small number of objects. In this paper, we address the problem of finding weak patterns (i.e., reliable exceptions) from databases. A simple and efficient approach is proposed which uses deviation analysis to identify interesting exceptions and explore reliable ones. Besides, it is flexible in handling both subjective and objective exceptions. We demonstrate the effectiveness of the proposed approach through a set of real-life data sets, and present interesting findings.
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.
7016782
Adaptive Linking between Text and Photos Using Common Sense Reasoning
In a hypermedia authoring task, an author often wants to set up meaningful connections between different media, such as text and photographs. To facilitate this task, it is helpful to have a software agent dynamically adapt the presentation of a media database to the user's authoring activities, and look for opportunities for annotation and retrieval. However, potential connections are often missed because of differences in vocabulary or semantic connections that are "obvious" to people but that might not be explicit.ARIA (Annotation and Retrieval Integration Agent) is a software agent that acts an assistant to a user writing e-mail or Web pages. As the user types a story, it does continuous retrieval and ranking on a photo database. It can use descriptions in the story to semi-automatically annotate pictures. To improve the associations beyond simple keyword matching, we use natural language parsing techniques to extract important roles played by text, such as "who, what, where, when". Since many of the photos depict common everyday situations such as weddings or recitals, we use a common sense knowledge base, Open Mind, to fill in semantic gaps that might otherwise prevent successful associations.
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.
16166828
Maximal lifetime scheduling for K to 1 sensor-target surveillance networks
This paper addresses the maximal lifetime scheduling for k to 1 sensor-target surveillance networks. Given a set of sensors and targets in Euclidean plane, a sensor can watch only one target at a time and a target should be watched by k sensors (k ≥ 2) at anytime. Our task is to schedule sensors to watch targets, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. This is the first time in the literature that this scheduling problem of sensor surveillance systems has been formulated and the optimal solution has been found. Our solution consists of three steps: (1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; (2) decomposing the workload matrix into a sequence of schedule matrices by extending the Hall's theory, to achieve the maximal lifetime; (3) obtaining a target watching timetable for each sensor based on the schedule matrices. The time complexity of our optimal method is O(m2n3), where m, n are the number of targets and the number of sensors, respectively. We illustrate our optimal method by a numeric example and experiments in the end.
23957657
Terminology model discovery using natural language processing and visualization techniques
Medical terminologies are important for unambiguous encoding and exchange of clinical information. The traditional manual method of developing terminology models is time-consuming and limited in the number of phrases that a human developer can examine. In this paper, we present an automated method for developing medical terminology models based on natural language processing (NLP) and information visualization techniques. Surgical pathology reports were selected as the testing corpus for developing a pathology procedure terminology model. The use of a general NLP processor for the medical domain, MedLEE, provides an automated method for acquiring semantic structures from a free text corpus and sheds light on a new high-throughput method of medical terminology model development. The use of an information visualization technique supports the summarization and visualization of the large quantity of semantic structures generated from medical documents. We believe that a general method based on NLP and information visualization will facilitate the modeling of medical terminologies.
11306780
Mean-entropy discretized features are effective for classifying high-dimensional biomedical data
This paper studies an empirical feature selection heuristics for classifying high-dimensional bio-medical data. A feature's discriminating power can be measured by its entropy value. Based on this idea, we do not consider those features that are ignored by the entropy idea. Such a selection can usually reduce the dimensionality of the data by 90-95%. Then we rank the remaining features, and select features whose entropy is smaller than the average of all the remaining features' entropies. This round of selection can usually further reduce two thirds of the features. So, we can achieve a reduction from tens of thousands of features to only hundreds of important features. Furthermore, we also observe that learning algorithms, including our new tree-committee classifier, generally improve their accuracy after the feature selection. This heuristics appears to be more systematic than the prevailing use of specific numbers of top-ranked features for classification.