It is often necessary to combine multiple scores into a joint decision in many real-world applications. To that end, an essential challenge is to build a proper weighted scoring rule, which assigns more weight to the more important scores and derives

Conventional k-means only considers pair wise similarity during cluster assignment, which aims to minimizing the distance of points to their nearest cluster centroids. In high dimensional space like document datasets, however, two points may be nearest neighbors without belonging to the same class. Thus pair wise similarity alone is often insufficient for class prediction in such space. To that end, in this paper, we propose to augment k-means with pair wise constraints generated from group similarity-based hyper clique patterns, which consist of strongly affiliated objects and serve as more reliable seeds for classification. Experiments with real-world datasets show that, with such constraints from quality hyper clique patterns, we can improve the clustering results in terms of various external criteria. Also, our experiments indicate that even if few constraints are violated in the original result of k-means, imposing many quality constraints may still bring gain of performance.

This paper describes an attempt to devise a knowledge discovery model that is inspired from the two theoretical frameworks of selectionism and constructivism in human cognitive learning. The "selectionist" nature of human decision making indicates the use of an evolutionary paradigm for composing rudimentary neural network units, while the "constructivist" component takes the form of neural weight training during the learning process. We explore the possibility of amalgamating these two ideas into a neural learning system for the discovery of meaningful rules in the context of pattern discovery in data.

Ranking has been widely used in many applications. A ranking scheme usually employs a scoring rule that assigns a final numerical value to every object to be ranked. A scoring rule normally involves the use of one to many scores, and it gives more weight to the scores that are more important. In this paper, we give a scheme that can combine weights into scores in a natural way and compare our scheme to the formula given by Fagin. Also given are some additional properties that are desirable for weighted scoring rules. Finally, we discuss other interesting issues on weighted scoring rules.

Hypergraph partitioning has been considered as a promising method to address the challenges of high dimensionality in document clustering. With documents modeled as vertices and the relationship among documents captured by the hyperedges, the goal of graph partitioning is to minimize the edge cut. Therefore, the definition of hyperedges is vital to the clustering performance. While several definitions of hyperedges have been proposed, a systematic understanding of desired characteristics of hyperedges is still missing. To that end, in this paper, we first provide a unified clique perspective of the definition of hyperedges, which serves as a guide to define hyperedges. With this perspective, based on the concepts of hypercliques and shared (reverse) nearest neighbors, we propose three new types of clique hyperedges and analyze their properties regarding purity and size issues. Finally, we present an extensive evaluation using real-world document datasets. The experimental results show that, with shared (reverse) nearest neighbor based hyperedges, the clustering performance can be improved significantly in terms of various external validation measures without the need for fine tuning of parameters.

The claimed advantage of describing a document data set with a bipartite graph is that partitioning such a graph yields a co-clustering of words and documents. The topic of each cluster can then be represented by the top words and documents that have highest within-cluster degrees. However, such claims may fail if top words and documents are selected simply because they are very general and frequent. In addition, for those words and documents across several topics, it may not be proper to assign them to a single cluster. To that end, this paper introduces a new bipartite formulation that incorporates both word hypercliques and document hypercliques as super vertices. By co-preserving hyperclique patterns during the clustering process, our experiments on real-world data sets show that better clustering results can be obtained and the cluster topic can be more precisely identified. Also, we illustrate an application of the partitioned bipartite to search engines, returning clustered search results for keyword queries. We show that the topic of each cluster with respect to the current query can be identified more accurately with the words and documents from the patterns than with those top ones from the standard bipartite formulation.

The use of frequent itemsets has been limited by the high computational cost as well as the large number of resulting itemsets. In many real-world scenarios, however, it is often sufficient to mine a small representative subset of frequent itemsets with low computational cost. To that end, in this paper, we define a new problem of finding the frequent itemsets with a maximum length and present a novel algorithm to solve this problem. Indeed, maximum length frequent itemsets can be efficiently identified in very large data sets and are useful in many application domains. Our algorithm generates the maximum length frequent itemsets by adapting a pattern fragment growth methodology based on the FP-tree structure. Also, a number of optimization techniques have been exploited to prune the search space. Our experimental results show that our algorithm is very efficient and scalable

This paper describes a new bipartite formulation for word-document co-clustering such that hyperclique patterns, strongly affiliated documents in this case, are guaranteed not to be split into different clusters. Our approach for pattern preserving clustering consists of three steps: mine maximal hyperclique patterns, form the bipartite, and partition it. With hyperclique patterns of documents preserved, the topic of each cluster can be represented by both the top words from that cluster and the documents in the patterns, which are expected to be more compact and representative than those in the standard bipartite formulation. Experiments with real-world datasets show that, with hyperclique patterns as starting points, we can improve the clustering results in terms of various external clustering criteria. Also, the partitioned bipartite with preserved topical sets of documents naturally lends itself to different functions in search engines

The comprehensibility aspect of rule discovery is of emerging interest in the realm of knowledge discovery in databases. Of the many cognitive and psychological factors relating the comprehensibility of knowledge, we focus on the use of human amenable concepts as a representation language in expressing classification rules. Existing work in neural logic networks (or neulonets) provides impetus for our research; its strength lies in its ability to learn and represent complex human logic in decision-making using symbolic-interpretable net rules. A novel technique is developed for neulonet learning by composing net rules using genetic programming. Coupled with a sequential covering approach for generating a list of neulonets, the straightforward extraction of human-like logic rules from each neulonet provides an alternate perspective to the greater extent of knowledge that can potentially be expressed and discovered, while the entire list of neulonets together constitute an effective classifier. We show how the sequential covering approach is analogous to association-based classification, leading to the development of an association-based neulonet classifier. Empirical study shows that associative classification integrated with the genetic construction of neulonets performs better than general association-based classifiers in terms of higher accuracies and smaller rule sets. This is due to the richness in logic expression inherent in the neulonet learning paradigm.

The term weighting scheme, which is used to convert documents into vectors in the term spaces, is a vital step in automatic text categorization. The previous studies showed that term weighting schemes dominate the performance rather than the kernel functions of SVMs for the text categorization task. In this paper, we conducted experiments to compare various term weighting schemes with SVM on two widely-used benchmark data sets. We also presented a new term weighting scheme tf.rf for text categorization. The cross-scheme comparison was performed by using McNemar's tests. The controlled experimental results showed that the newly proposed tf.rf scheme is significantly better than other term weighting schemes. Compared with schemes related with tf factor alone, the idf factor does not improve or even decrease the term's discriminating power for text categorization. The binary and tf.chi representations significantly underperform the other term weighting schemes.

This paper introduces a novel motif discovery algorithm based on the use of constraint mechanism and constraint rules. The key idea is to convert sets of similar substrings of the DNA sequences into patterns, as early as possible, using constraint mechanism or constraint rules. The advantages are two folds. Firstly, the approach generates limited number of patterns while still guaranteeing that the actual motifs are contained in the pattern set. Secondly, the procedure for deriving patterns is very cost-effective since it can be considered as that we use many "look ahead" to speed up the procedure. Therefore, the algorithm has the advantages of the high sensitivity of pattern-driven algorithms as well as the efficiency of sample-driven algorithms.

Data privacy refers to the issue of how to preserve the confidential information in individual data cells while still being able to provide an accurate estimation of the original summation values for range queries. There are three major goals in data privacy:l)Security - the data must be protected from being revealed; 2)Accuracy - results of analysis are valuable in a business's decision making and 3)Accessibility - data should be as easy to be accessed as possible. However, the open nature of data warehouses creates a security conflict. Another conflict is between security and accuracy of the query results. With the increase in the number of data warehouses and OLAP users, the misuse of data warehouse is steadily growing, which has led to the needs for proper techniques to support all three goals of data privacy. We propose a novel and simple but effective solution to fulfill all three goals.

Various iterative refinement clustering methods are dependent on the initial state of the model and are capable of obtaining one of their local optima only. Since the task of identifying the global optimization is NP-hard, the study of the initialization method towards a sub-optimization is of great value. This paper reviews the various cluster initialization methods in the literature by categorizing them into three major families, namely random sampling methods, distance optimization methods, and density estimation methods. In addition, using a set of quantitative measures, we assess their performance on a number of synthetic and real-life data sets. Our controlled benchmark identifies two distance optimization methods, namely SCS and KKZ, as complements of the k-means learning characteristics towards a better cluster separation in the output solution.

This paper investigates wrapper induction from web sites whose layout may change over time. We formulate the reinduction as an incremental learning problem and identify that wrapper induction from an incomplete label is a key problem to be solved. We propose a novel algorithm for incrementally inducing LR wrappers and show that this algorithm asymptotically identifies the correct wrapper as the number of tuples is increased. This property is used to propose a LR wrapper reinduction algorithm. This algorithm requires examples to be provided exactly once and there-after the algorithm can detect the layout changes and reinduce wrappers automatically. In experimental studies, we observe that the reinduction algorithm is able to achieve near perfect performance.

Spatial prediction needs to account for spatial information, which makes conventional radial basis function (RBF) networks inappropriate, for they assume independent and identical distribution. In this paper, we fuse spatial information at different layers of RBF. Experiments show fusion at hidden layer gives the best result and suggest that the optimal value is around one for the coefficient, which is used in the linear combination at the output layer.

Transaction clustering has received attention in recent developments of data mining. Traditional clustering methods are not useful to solve this problem. Transaction data sets are different from the traditional data sets in their high dimensionality, sparsity and numerous outliers. We introduce a new efficient algorithm for transaction clustering. The proposed algorithm is based on a caucus, which is fine-partitioned demographic groups based on purchase features of customers. Due to the important role caucus plays, we also present a heuristic method of caucus generation with the use of entropy. Experiments on real and synthetic data sets show that our approach can achieve a better result than existed methods.

An important issue that needs to be addressed when using data mining tools is the validity of the rules outside of the data set from which they are generated. Rules are typically derived from the patterns in a particular data set. When a new situation occurs, the change in the set of rules obtained from the new data set could be significant. In this paper, we provide a novel model for understanding how the differences between two situations affect the changes of the rules, based on the concept of fine partitioned groups that we call caucuses. Using this model, we provide a simple technique called combination data set, to get a good estimate of the set of rules for a new situation. Our approach works independently of the core mining process and it can be easily implemented with all variations of rule mining techniques. Through experiments with real-life and synthetic data sets, we show the effectiveness of our technique in finding the correct set of rules under different situations.

Existing data cleansing methods are costly and will take very long time to cleanse large databases. Since large databases are common nowadays, it is necessary to reduce the cleansing time. Data cleansing consists of two main components, detection method and comparison method. In this paper, we first propose a simple and fast comparison method, TI-Similarity, which reduces the time for each comparison. Based on TI-Similarity, we propose a new detection method, RAR, to further reduce the number of comparisons. With RAR and TI-Similarity, our new approach for cleansing large databases is composed of two processes: Filtering process and Pruning process. In filtering process, a fast scan on the database is carried out with RAR and TI-Similarity. This process guarantees the detection of potential duplicate records but may introduce false positives. In pruning process, the duplicate result from the filtering process is pruned to eliminate the false positives using more trustworthy comparison methods. The performance study shows that our approach is efficient and scalable for cleansing large databases, and is about an order of magnitude faster than existing cleansing methods.

The Mobile IP analysis model does not give much investigation of the situation when the correspondent node (CN) is also a mobile node. Triangle routing reflects the assumption of a stationary CN. When the CN is also mobile, the routing path is not a triangle any more. Moreover, the binding update (BU) between two mobile nodes is more complex than the binding update from a mobile node to a stationary node. When two mobile nodes transfer bulk data between them, the efficiency will be greatly affected by the binding update mechanisms. This paper presents our study on bulk data transfer between two mobile nodes. We present a comprehensive list of possible BU transmission methods, and we show our performance evaluations of them. By analyzing the results, we found several important factors that affect efficiency in terms of traffic load and average bit rate. Finally, we present our improvement on BU transmission method and its evaluation results. The results showed that our improvement is very helpful when the CN is mobile.

A new method for gauging text similarity of image-based documents using word shape recognition is proposed in this paper. Image features are directly extracted instead of using OCR (optical character recognition). The proposed method forms so-called vertical bar patterns by detecting local extrema points in word units extracted by segmenting the document images. These vertical bar patterns form the feature vector of a document. The pair-wise similarity of document images is measured by calculating the scalar product of two document feature vectors. The proposed method is robust to changing fonts and styles, and is less affected by degradation of document qualities. To test the validity of the method, four corpora of document images were used and the ability of the method to retrieve relevant documents is reported.

We propose a word shape recognition method for retrieving image-based documents. Document images are segmented at the word level first. Then the proposed method detects local extrema points in word segments to form so-called vertical bar patterns. These vertical bar patterns form the feature vector of a document. The scalar product of two document feature vectors is calculated to measure the pairwise similarity of document images. The proposed method is robust to changing fonts and styles, and is less affected by degradation of document qualities. Three groups of words in different fonts and image qualities were used to test the validity of our method. Real-life document images were also used to test the method's ability of retrieving relevant documents.

There are several payment protocols mediated by trusted third party functioning as bank (or credit card) agents. But these protocols do not integrate all parts of the protocol together. These agents only establish payment intention but not handle settlement. These protocols rely on traditional payment systems and logistics pathways to complete transactions thus the efficiency is low. In addition, though the agents in these protocols took up some services of the traditional financial conglomerates, risk analysis of the agents is unintentionally neglected. Here we developed an integrative and instantaneous payment protocol-virtual card payment protocol. Broker in our protocol is a bank agent, a financial conglomerate, a logistics assistant, a creditor to score participants' performance and an arbitrator to solve dispute between customers and merchants. In this protocol, one transaction is divided into 3 parts and different parts of the transaction apply different security level. Settlement can be instantaneously handled totally online, without direct involvement of traditional payment systems. Logistics is integrated to process through Internet. We define this technique "pay-on-delivery-online". Since inconsistency in transactions causes customer to complain, we introduce complaint-processing to build trust among involved participants. To dissipate risk concentration in Broker, we propose an algorithm to quantify participants' trustworthiness by estimating participants' transaction history with statistic analysis. Since it assumes that the participants' performance can only be evaluated by those that have established business with them, the model is more objective than poll online and is like the credit scoring or behavioral scoring in real world banking systems.

The high frequency of applications involving large, ordered, nested lists suggests that list is the "next most" natural data type after set. A list differs from a set through positioning and nesting elements within the list. Directly supporting such position-related operations will greatly improve the performance of database systems targeting at the above applications. Unlike other attributes, the position will be changed by insertion and deletion within a list and known methods are not appropriate for indexing the position. We present an indexing structure, called the P-tree (where P for position), to index a set of lists. The P-tree generalizes the B-tree by dealing with a set of lists rather than a set of records, while preserving all the properties of the B-tree.

This work is on the use of multiple attributes or features and spatial relationships, with the help of a user interface based on an iconic paradigm, to retrieve images represented by iconic pictures. An icon has texture, color and text attributes. Texture is represented by 3 statistical textural properties, namely, coarseness, contrast and directionality. For text, the vector space model is used. For color, a representation based on a modified color histogram method which is less storage-intensive is proposed. The final icon similarity is the combination of the attribute similarity values using a proven adaptive algorithm. 2-D strings and its variants are commonly used to represent spatial relationships and perform spatial reasoning. However, the basic methods do not perform similarity ranking. We extended the method to include similarity ranking by using different similarity functions for different spatial relationships and an efficient embedding algorithm. Furthermore, our method, on top of other benefits, solves the problem of query expressiveness which all methods based on 2-D string representations suffer from.

Cartesian product files have been shown to exhibit attractive properties for partial match queries. The Disk Modulo (DM) allocation method is shown to have good performance on the distribution of Cartesian product files into an m-disk system. However, there was no explicit expression made before to represent the DM method's response time to a given partial match query. In this paper, based upon discrete Fourier transform, we derive one formula for such a computation. After obtaining this representation, the performance characteristics of the DM method can now be given an analytic interpretation. Some theoretical results are derived from this formula. We also use our formula to analyze the performance of several popular Disk Modulo algorithms.