5595688
Discovering Interesting Association Rules by Clustering
There are a great many metrics available for measuring the interestingness of rules In this paper, we design a distinct approach for identifying association rules that maximizes the interestingness in an applied context More specifically, the interestingness of association rules is defined as the dissimilarity between corresponding clusters In addition, the interestingness assists in filtering out those rules that may be uninteresting in applications Experiments show the effectiveness of our algorithm.
7425380
Enhancing DWT for Recent-Biased Dimension Reduction of Time Series Data
In many applications, old data in time series become less important as time elapses, which is a big challenge to traditional techniques for dimension reduction. To improve Discrete Wavelet Transform (DWT) for effective dimension reduction in this kind of applications, a new method, largest-latest-DWT, is designed by keeping the largest k coefficients out of the latest w coefficients at each level of DWT transform. Its efficiency and effectiveness is demonstrated by our experiments.
15790608
Clustering High-Dimensional Data with Low-Order Neighbors
Density-based and grid-based clustering are two main clustering approaches. The former is famous for its capability of discovering clusters of various shapes and eliminating noises, while the latter is well known for its high speed. Combination of the two approaches seems to provide better clustering results. To the best of our knowledge, however, all existing algorithms that combine density-based clustering and grid-based clustering take cells as atomic units, in the sense that either all objects in a cell belong to a cluster or no object in the cell belong to any cluster. This requires the cells to be small enough to ensure the fine resolution of results. In high-dimensional spaces, however, the number of cells can be very large when cells are small, which would make the clustering process extremely costly. On the other hand, the number of neighbors of a cell grows exponentially with the dimensionality of datasets, which makes the complexity increase further. In this paper, we present a new approach that takes objects (or points) as the atomic units, so that the restriction of cell size can be relaxed without degrading the resolution of clustering results. In addition, a concept of ith-order neighbors is introduced to avoid considering the exponential number of neighboring cells. By considering only low-order neighbors, our algorithm is very efficient while losing only a little bit of accuracy. Experiments on synthetic and public data show that our algorithm can cluster high-dimensional data effectively and efficiently.
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.
38902380
Construction Algorithm of Principal Curves in the Sense of Limit
Principal curves have been defined as self-consistent, smooth, one-dimensional curves which pass through the middle of a multidimensional data set. They are nonlinear generalization of the first Principal Component. In this paper, we take a new approach by defining principal curves as continuous curves based on the local tangent space in the sense of limit. It is proved that this new principal curves not only satisfy the self-consistent property, but also are the unique existence for any given open covering. Based on the new definition, a new practical algorithm for constructing principal curves is given. And the convergence properties of this algorithm are analyzed. The new construction algorithm of principal curves is illustrated on some simulated data sets.
42961259
Authorship Attribution Via Combination of Evidence
Authorship attribution is a process of determining who wrote a particular document. We have found that different systems work well for particular sets of authors but not others. In this paper, we propose three authorship attribution systems, based on different ways of combining existing methodologies. All systems show better effectiveness than the state-of-art methods.
12919460
Decay rate for a PH/M/2 queue with shortest queue discipline
In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates.
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.
10708118
Fault modeling and simulation for crosstalk in system-on-chip interconnects
System-on-chips (SOCs) using ultra deep sub-micron (DSM) technologies and GHz clock frequencies have been predicted by the 1997 SIA Road Map. Recent studies, as well as experiments reported in this paper, show significant crosstalk effects in long on-chip interconnects of GHz DSM chips. Recognizing the importance of high-speed, reliable interconnects in GHz SOCs, we address in this paper the problem of testing for glitch and delay errors caused by crosstalk in buses and interconnects between components of a SOC. Since it is not possible to explicitly test for all the possible process variations and defects that can lead to crosstalk errors in SOC interconnects, we present an abstract model, Maximum Aggressor (MA) fault model, and its test requirements. The attractiveness of the model is that it can abstract crosstalk defects in interconnects with a linear number of faults, while the corresponding MA tests provide complete coverage for all level defects related to cross-coupling capacitance the interconnects. A SPICE-level fault simulation methodology is presented which allows simulation of a small subset of the potentially exponential number of defects. The simulation methodology also enables validation of the proposed fault model and the resulting test set.
7784369
Network bandwidth requirements for scalable on-demand streaming
Recently proposed streaming protocols are able to deliver multimedia files on-demand with the required server bandwidth growing only logarithmically with the file request rate. The same efficiencies are achieved for network bandwidth if delivery is over a true broadcast channel. This paper considers the required network bandwidth for on-demand streaming over multicast delivery trees. We consider both simple canonical delivery trees, and more complex cases in which delivery trees are constructed using both existing and new algorithms for various randomly generated network topologies and client site locations. Our results quantify the potential savings from the use of multicast trees that are configured to minimize network bandwidth rather than the latency to the content server. Further, we show that it is possible to achieve reasonably close to the minimum possible bandwidth usage for both network and server simultaneously, with a practical on-demand streaming protocol.