6845908
Mining ratio rules via principal sparse non-negative matrix factorization
Association rules are traditionally designed to capture statistical relationship among itemsets in a given database. To additionally capture the quantitative association knowledge, Korn et al. (1998) proposed a paradigm named ratio rules for quantifiable data mining. However, their approach is mainly based on principle component analysis (PCA) and as a result, it cannot guarantee that the ratio coefficient is nonnegative. This may lead to serious problems in the rules' application. In this paper, we propose a method, called principal sparse nonnegative matrix factorization (PSNMF), for learning the associations between itemsets in the form of ratio rules. In addition, we provide a support measurement to weigh the importance of each rule for the entire dataset.
6802371
Improving web search results using affinity graph
In this paper, we propose a novel ranking scheme named Affinity Ranking (AR) to re-rank search results by optimizing two metrics: (1) diversity -- which indicates the variance of topics in a group of documents; (2) information richness -- which measures the coverage of a single document to its topic. Both of the two metrics are calculated from a directed link graph named Affinity Graph (AG). AG models the structure of a group of documents based on the asymmetric content similarities between each pair of documents. Experimental results in Yahoo! Directory, ODP Data, and Newsgroup data demonstrate that our proposed ranking algorithm significantly improves the search performance. Specifically, the algorithm achieves 31% improvement in diversity and 12% improvement in information richness relatively within the top 10 search results.
432736
ReCoM: reinforcement clustering of multi-type interrelated data objects
Most existing clustering algorithms cluster highly related data objects such as Web pages and Web users separately. The interrelation among different types of data objects is either not considered, or represented by a static feature space and treated in the same ways as other attributes of the objects. In this paper, we propose a novel clustering approach for clustering multi-type interrelated data objects, ReCoM (Reinforcement Clustering of Multi-type Interrelated data objects). Under this approach, relationships among data objects are used to improve the cluster quality of interrelated data objects through an iterative reinforcement clustering process. At the same time, the link structure derived from relationships of the interrelated data objects is used to differentiate the importance of objects and the learned importance is also used in the clustering process to further improve the clustering results. Experimental results show that the proposed approach not only effectively overcomes the problem of data sparseness caused by the high dimensional relationship space but also significantly improves the clustering accuracy.
14828051
MRSSA: an iterative algorithm for similarity spreading over interrelated objects
We introduce the Multiple Relationship Similarity Spreading Algorithm (MRSSA) to enhance IR effectiveness. This method has similarity computed in an iterative "spreading" fashion for multiple object types, combining both inter- and intra-object relationships. We demonstrate the value of this approach in the context of the WWW, where the key objects are web pages and queries, Relationships considered are derived from hyperlinks (in- and out-links) and click-through logs.
17711119
IRC: an iterative reinforcement categorization algorithm for interrelated Web objects
Most existing categorization algorithms deal with homogeneous Web data objects, and consider interrelated objects as additional features when taking the interrelationships with other types of objects into account. However, focusing on any single aspects of these interrelationships and objects does not fully reveal their true categories. In this paper, we propose a categorization algorithm, the iterative reinforcement categorization algorithm (IRC), to exploit the full interrelationships between the heterogeneous objects on the Web. IRC attempts to classify the interrelated Web objects by iterative reinforcement between individual classification results of different types via the interrelationships. Experiments on a clickthrough log dataset from MSN search engine show that, with the Fl measures, IRC achieves a 26.4% improvement over a pure content-based classification method, a 21% improvement over a query metadata-based method, and a 16.4% improvement over a virtual document-based method. Furthermore, our experiments show that IRC converges rapidly.
459986
A New Statistical Approach To Chinese Pinyin Input
Chinese input is one of the key challenges for Chinese PC users. This paper proposes a statistical approach to Pinyin-based Chinese input. This approach uses a trigram-based language model and a statistically based segmentation. Also, to deal with real input, it also includes a typing model which enables spelling correction in sentence-based Pinyin input, and a spelling model for English which enables modeless Pinyin input.
38006851
Approximation Algorithms for Independent Sets in Map Graphs
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.
17642246
Evolving an Experience Base for Software Process Research
Since 1996 the USC Center for Software Engineering has been accumulating a large amount of software process experience through many real-client project software engineering practices. Through the application of the Experience Factory approach, we have collected and evolved this experience into an experience base (eBASE) which has been leveraged successfully for empirically based software process research. Through eBASE we have realized tangible benefits in automating, organizational learning, and strategic advantages for software engineering research. We share our rationale for creating and evolving eBASE, give examples of how the eBASE has been used in recent process research, discuss current limitations and challenges with eBASE, and what we hope to do achieve in the future with it.
13469823
On-line learning of rectangles and unions of rectangles
We design efficient algorithms for on-line learning of axis-parallel rectangles (and for the union of two such rectangles) in the common model for on-line learning with equivalence queries. With regard to the learning of rectangles in arbitrary dimensionsd we solve the following open problem:Is there an algorithm for on-line learning of rectangles Πi=1d {ai,ai+1,...,bi} over a discrete domain {1,...,n}d whose error bound is polylogarithmic in the sizend of the domain (i.e. polynomial ind and logn)?We give a positive solution by introducing a new design technique that appears to be of some interest on its own. The new learning algorithm for rectangles consists of 2d separate search strategies that search for the parametersa1,b1,...,ad,bd of the target rectangle. A learning algorithm with this type of modular design tends to fail because of the well known “credit assignment problem”: Which of the 2d local search strategies should be “blamed” when the global algorithm makes an error? We propose here a rather radical solution to this problem:each local search strategy that is possibly involved in an error of the global algorithm will be blamed. With this radical solution it is unavoidable that frequently local search strategies will be blamed incorrectly. We overcome this difficulty by employing local search strategies (“error tolerant binary search”) that are able totolerate such incorrect credit assignments. The structure of this learning algorithm is reminiscent of “finite injury priority constructions” in recursive function theory.Section 4 contains another application of this design technique: an algorithm for learning the union of two rectangles in the plane.
2974790
The complexity of the matrix eigenproblem
The eigenproblem for an n-by-n matrix A is the problem of the approximation (within a relative error bound 2-‘) of all the eigenvalues of the matrix A and computing the associated eigenspaces of all these eigenvalues. We show that the arithmetic complexity of this problem is bounded by O(n3 + (nlog’n)log b). If the characteristic and minimum polynomials of the matrix A coincide with each other (which is the ca8e for generic matrices of all classes of general and special matrices that we consider), then the latter deterministic cost bound can be replaced by the randomized bound O(K.a(2n) + n* + (n log’n) log b) where Ka(2n) denotes the cost of the computation of the 2n 1 vectors A’v, i = 1,. ,2n 1, maximized over all n-dimensional vectors v; Ka(2n) = O(M(n)logn), for M(n) = o(n2.3’6) denoting the arithmetic complexity of n x n matrix multiplication. This bound on the complexity of the eigenproblem is optimal up to a logarithmic factor and implies much faster solution of the eigenprohlem for the important special classes of matrices. In particular, we prove the bound O(n’ log n + (n log’ n) log b) on the randomized arithmetic complexity of the eigenproblem for generic matrices of the classes of n x n Toeplitz, Hank& Toeplitzlike, Hank&like and Toeplits-likeplus-Hank&like matrices. Then again, this bound is optimal (up to a logarithmic factor) for each of the latter classes of input matrices. We also prove similar nearly optimal upper bounds for the generic Caucby-like, Vandermonde-like and sparse matrices. All our complexity estimates for the eigenproblem improve the known ones by order of magnitude.
23002052
Transition matrices in the measurement and control of synchronous sequential machines
Abstract This paper develops a matrix approach to the solution of the measurement and control problems in synchronous sequential machines. The control problem in sequential machines is concerned with finding input sequences that take a given machine from a known initial state to a predesignated terminal state. There may be many different measurement problems of interest in sequential machines. One important measurement problem is the identification of the unknown initial state of the machine, called the initial-state identification problem or diagnosing problem; another important measurement problem is the identification of the terminal state of the machine, known as the terminal-state identification problem or homing problem, of which a special case is the synchronizing problem. These measurement problems may be solved by applying predetermined input sequences to the machine and noting the resulting output sequences. The conventional approach to the solution of these measurement and control problems is to make use of the information contained in the transition table of the machine in conjunction with its response tree, which is basically an exhaustive tree search process. In the present paper, instead of using the transition table and the corresponding response tree, we use only the transition matrix representation of the machine and its higher order forms to solve the aforementioned problems. The suggested approach is very systematic and completely algorithmic, and thus lends itself to easy computer implementation.