9438100
Classification Based on Logical Concept Analysis
This paper studies the problem of classification by using a concept lattice as a search space of classification rules. The left hand side of a classification rule is composed by a concept, including its extension and its intension, and the right hand side is the class label that the concept implies. Particularly, we show that logical concepts of the given universe are naturally associated with any consistent classification rules generated by any partition-based or covering-based algorithm, and can be characterized as a special set of consistent classification rules. An algorithm is proposed to find a set of the most general consistent concepts.
37471711
Coarsening Classification Rules on Basis of Granular Computing
The task of classification, as a well-studied field of machine learning and data mining, has two main purposes: describing the classification rules in the training dataset and predicting the unseen new instances in the testing dataset. Normally, one expects a high accuracy for precisely descriptive use. However, a higher accuracy is intended to generate longer rules, which are not easy to understand, and may overfit the training instances. This motivates us to propose the approach of coarsening the classification rules, namely, reasonably sacrifice the accuracy of description in a controlled level in order to improve the comprehensibility and predictability. The framework of granular computing provides us a formal and systematic methodology for doing this. In this paper, a modified PRISM classification algorithm is presented based on the framework of granular computing.
7261122
Multilevel Web personalization
Web personalization is one of the major concerns of Web intelligence. It is noticed that the two components of Web, users and services, can be understood from multiple views in forms of hierarchies, and each hierarchy is organized by a multilevel structure. A unified model is proposed for including all personalization styles. The unified model with multilevel hierarchy structures, add new understandings and insights into the Web personalization issues. More concise and precise recommendations can then be studied and pursued based on this multilevel model.
14058950
A Profit-Based Business Model for Evaluating Rule Interestingness
Different types of rules are mined from transaction databases often with the goal of improving sales and services. In this paper, we link the interestingness of rules with the context of business marketing. We consider the profits generated from some specific marketing strategies that are developed based on particular discovered rules. This leads to a profit-based business model for evaluating rule interestingness. With this additional utility, we investigate some relationships between different marketing strategies and fundamental properties of rules for profit increasing.
1206474
Interactive classification using a granule network
Classification is one of the main tasks in machine learning, data mining and pattern recognition. Compared with the extensively studied data-driven approaches, the interactively user-driven approaches are less explored. A granular computing model is suggested for re-examining the classification problems. An interactive classification method using the granule network is proposed, which allows multi-strategies for granule tree construction and enhances the understanding and interpretation of the classification process. This method is complementary to the existing classification methods.
32435431
Regularized Semi-supervised Classification on Manifold
Semi-supervised learning gets estimated marginal distribution PX with a large number of unlabeled examples and then constrains the conditional probability p(y | x) with a few labeled examples. In this paper, we focus on a regularization approach for semi-supervised classification. The label information graph is first defined to keep the pairwise label relationship and can be incorporated with neighborhood graph which reflects the intrinsic geometry structure of PX. Then we propose a novel regularized semi-supervised classification algorithm, in which the regularization term is based on the modified Graph Laplacian. By redefining the Graph Laplacian, we can adjust and optimize the decision boundary using the labeled examples. The new algorithm combines the benefits of both unsupervised and supervised learning and can use unlabeled and labeled examples effectively. Encouraging experimental results are presented on both synthetic and real world datasets.
7415922
A numerically stable algorithm for two server queue models
In this paper, we consider a queueing system in which there are two exponential servers, each having his own queue, and arriving customers will join the shorter queue. Based on the results given in Flatto and McKean, we rewrite the formula for the probability that there are exactlyk customers in each queue, wherek = 0, 1,…. This enables us to present an algorithm for computing these probabilities and then to find the joint distribution of the queue lengths in the system. A program and numerical examples are given.
10152279
An on-chip IP address lookup algorithm
This paper proposes a new data compression algorithm to store the routing table in a tree structure using very little memory. This data structure is tailored to a hardware design reference model presented in this paper. By exploiting the low memory access latency and high bandwidth of on-chip memory, high-speed packet forwarding can be achieved using this data structure. With the addition of pipeline in the hardware, IP address lookup can only be limited by the memory access speed. The algorithm is also flexible for different implementation. Experimental analysis shows that, given the memory width of 144 bits, our algorithm needs only 400kb memory for storing a 20k entries IPv4 routing table and five memory accesses for a search. For a 1M entries IPv4 routing table, 9Mb memory and seven memory accesses are needed. With memory width of 1,068 bits, we estimate that we need 100Mb memory and six memory accesses for a routing table with 1M IPv6 prefixes.
8299246
HyLog: A High Performance Approach to Managing Disk Layout
Our objective is to improve disk I/O performance in multi-disk systems supporting multiple concurrent users, such as file servers, database servers, and email servers. In such systems, many disk reads are absorbed by large in-memory buffers, and so disk writes comprise a large portion of the disk I/O traffic. LFS (Log-structured File System) has the potential to achieve superior write performance by accumulating small writes into large blocks and writing them to new places, rather than overwriting on top of their old copies (called Overwrite). Although it is commonly believed that the high segment cleaning overhead of LFS makes it a poor choice for workloads with random updates, in this paper we find that because of the fast improvement of disk technologies, LFS significantly outperforms Overwrite in a wide range of system configurations and workloads (including the random update workload) under modern and future disks. 
 
LFS performs worse than Overwrite, however, when the disk space utilization is very high due to the high cleaning cost. In this paper, we propose a new approach, the Hybrid Log-structured (Hy-Log) disk layout, to overcome this problem. Hy-Log uses a log-structured approach for hot pages to achieve high write performance, and Overwrite for cold pages to reduce the cleaning cost. We compare the performance of HyLog to that of Overwrite, LFS and WOLF (the latest improvement on LFS) under various system configurations and workloads. Our results show that, in most cases, Hylog performs comparably to the best of the other three approaches.
17699590
Adapting K-Means Algorithm for Discovering Clusters in Subspaces
Subspace clustering is a challenging task in the field of data mining. Traditional distance measures fail to differentiate the furthest point from the nearest point in very high dimensional data space. To tackle the problem, we design minimal subspace distance which measures the similarity between two points in the subspace where they are nearest to each other. It can discover subspace clusters implicitly when measuring the similarities between points. We use the new similarity measure to improve traditional k-means algorithm for discovering clusters in subspaces. By clustering with low-dimensional minimal subspace distance first, the clusters in low-dimensional subspaces are detected. Then by gradually increasing the dimension of minimal subspace distance, the clusters get refined in higher dimensional subspaces. Our experiments on both synthetic data and real data show the effectiveness of the proposed similarity measure and algorithm.