OpenRaiser/Intern-Atlas huggingface dataset:
Locating secret messages in images
Authors: Ian Davidson, Goutam Paul
Venue: KDD
Year: 2004

Steganography involves hiding messages in innocuous media such as images, while steganalysis is the field of detecting these secret messages. The ultimate goal of steganalysis is two-fold: making a binary classification of a file as stego-bearing or innocent, and secondly, locating the hidden message with an aim to extracting, sterilizing or manipulating it. Almost all steganalysis approaches (known as attacks) focus on the first of these two issues. In this paper, we explore the difficult related problem: given that we know an image file contains steganography, locate which pixels contain the message. We treat the hidden message location problem as outlier detection using probability/energy measures of images motivated by the image restoration community. Pixels contributing the most to the energy calculations of an image are deemed outliers. Typically, of the top third of one percent of most energized pixels (outliers), we find that 87% are stego-bearing in color images and 61% in grayscale images. In all image types only 1% of all pixels are stego-bearing indicating our techniques provides a substantial lift over random guessing.
Kernel k-means: spectral clustering and normalized cuts
Authors: Inderjit S. Dhillon, Yuqiang Guan, Brian Kulis
Venue: KDD
Year: 2004

Kernel k-means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. Despite significant research, these methods have remained only loosely related. In this paper, we give an explicit theoretical connection between them. We show the generality of the weighted kernel k-means objective function, and derive the spectral clustering objective of normalized cut as a special case. Given a positive definite similarity matrix, our results lead to a novel weighted kernel k-means algorithm that monotonically decreases the normalized cut. This has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, such as local search and acceleration schemes, may be used to improve the quality as well as speed of kernel k-means. Finally, we present results on several interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set.
A microeconomic data mining problem: customer-oriented catalog segmentation
Authors: Martin Ester, Rong Ge, Wen Jin, Zengjian Hu
Venue: KDD
Year: 2004

The microeconomic framework for data mining [7] assumes that an enterprise chooses a decision maximizing the overall utility over all customers where the contribution of a customer is a function of the data available on that customer. In Catalog Segmentation, the enterprise wants to design k product catalogs of size r that maximize the overall number of catalog products purchased. However, there are many applications where a customer, once attracted to an enterprise, would purchase more products beyond the ones contained in the catalog. Therefore, in this paper, we investigate an alternative problem formulation, that we call Customer-Oriented Catalog Segmentation, where the overall utility is measured by the number of customers that have at least a specified minimum interest t in the catalogs. We formally introduce the Customer-Oriented Catalog Segmentation problem and discuss its complexity. Then we investigate two different paradigms to design efficient, approximate algorithms for the Customer-Oriented Catalog Segmentation problem, greedy (deterministic) and randomized algorithms. Since greedy algorithms may be trapped in a local optimum and randomized algorithms crucially depend on a reasonable initial solution, we explore a combination of these two paradigms. Our experimental evaluation on synthetic and real data demonstrates that the new algorithms yield catalogs of significantly higher utility compared to classical Catalog Segmentation algorithms.
Regularized multi--task learning
Authors: Theodoros Evgeniou, Massimiliano Pontil
Venue: KDD
Year: 2004

Past empirical work has shown that learning multiple related tasks from data simultaneously can be advantageous in terms of predictive performance relative to learning these tasks independently. In this paper we present an approach to multi--task learning based on the minimization of regularization functionals similar to existing ones, such as the one for Support Vector Machines (SVMs), that have been successfully used in the past for single--task learning. Our approach allows to model the relation between tasks in terms of a novel kernel function that uses a task--coupling parameter. We implement an instance of the proposed approach similar to SVMs and test it empirically using simulated as well as real data. The experimental results show that the proposed method performs better than existing multi--task learning methods and largely outperforms single--task learning using SVMs.
k-TTP: a new privacy model for large-scale distributed environments
Authors: Bobi Gilburd, Assaf Schuster, Ran Wolff
Venue: KDD
Year: 2004

Secure multiparty computation allows parties to jointly compute a function of their private inputs without revealing anything but the output. Theoretical results [2] provide a general construction of such protocols for any function. Protocols obtained in this way are, however, inefficient, and thus, practically speaking, useless when a large number of participants are involved.The contribution of this paper is to define a new privacy model -- k-privacy -- by means of an innovative, yet natural generalization of the accepted trusted third party model. This allows implementing cryptographically secure efficient primitives for real-world large-scale distributed systems.As an example for the usefulness of the proposed model, we employ k-privacy to introduce a technique for obtaining knowledge -- by way of an association-rule mining algorithm -- from large-scale Data Grids, while ensuring that the privacy is cryptographically secure.
User-centered design for KDD
Authors: Eric Haseltine
Venue: KDD
Year: 2004

During initial development, KDD solutions often focus heavily on algorithms, architectures, software, hardware, and systems engineering challenges, without first thoroughly exploring how end-users will employ the new KDD technology. As a result of such "system-centered" design, many useless features are implemented that prolong development and significantly add to life cycle cost, while making the system hard to operate and use. This presentation will describe an alternate "user-centered" approach -- borrowed from the consumer products industry -- that can produce KDD solutions with shorter development cycles, lower costs, and much better usability.
Discovering complex matchings across web query interfaces: a correlation mining approach
Authors: Bin He, Kevin Chen-Chuan Chang, Jiawei Han
Venue: KDD
Year: 2004

To enable information integration, schema matching is a critical step for discovering semantic correspondences of attributes across heterogeneous sources. While complex matchings are common, because of their far more complex search space, most existing techniques focus on simple 1:1 matchings. To tackle this challenge, this paper takes a conceptually novel approach by viewing schema matching as correlation mining, for our task of matching Web query interfaces to integrate the myriad databases on the Internet. On this "deep Web," query interfaces generally form complex matchings between attribute groups (e.g., [author] corresponds to [first name, last name] in the Books domain). We observe that the co-occurrences patterns across query interfaces often reveal such complex semantic relationships: grouping attributes (e.g., [first name, last name]) tend to be co-present in query interfaces and thus positively correlated. In contrast, synonym attributes are negatively correlated because they rarely co-occur. This insight enables us to discover complex matchings by a correlation mining approach. In particular, we develop the DCM framework, which consists of data preparation, dual mining of positive and negative correlations, and finally matching selection. Unlike previous correlation mining algorithms, which mainly focus on finding strong positive correlations, our algorithm cares both positive and negative correlations, especially the subtlety of negative correlations, due to its special importance in schema matching. This leads to the introduction of a new correlation measure, $H$-measure, distinct from those proposed in previous work. We evaluate our approach extensively and the results show good accuracy for discovering complex matchings.
Graphical models for data mining
Authors: David Heckerman
Venue: KDD
Year: 2004

I will discuss the use of graphical models for data mining. I will review key research areas including structure learning, variational methods, a relational modeling, and describe applications ranging from web traffic analysis to AIDS vaccine design.
Diagnosing extrapolation: tree-based density estimation
Authors: Giles Hooker
Venue: KDD
Year: 2004

There has historically been very little concern with extrapolation in Machine Learning, yet extrapolation can be critical to diagnose. Predictor functions are almost always learned on a set of highly correlated data comprising a very small segment of predictor space. Moreover, flexible predictors, by their very nature, are not controlled at points of extrapolation. This becomes a problem for diagnostic tools that require evaluation on a product distribution. It is also an issue when we are trying to optimize a response over some variable in the input space. Finally, it can be a problem in non-static systems in which the underlying predictor distribution gradually drifts with time or when typographical errors misrecord the values of some predictors.We present a diagnosis for extrapolation as a statistical test for a point originating from the data distribution as opposed to a null hypothesis uniform distribution. This allows us to employ general classification methods for estimating such a test statistic. Further, we observe that CART can be modified to accept an exact distribution as an argument, providing a better classification tool which becomes our extrapolation-detection procedure. We explore some of the advantages of this approach and present examples of its practical application.
Mining the space of graph properties
Authors: Glen Jeh, Jennifer Widom
Venue: KDD
Year: 2004

Existing data mining algorithms on graphs look for nodes satisfying specific properties, such as specific notions of structural similarity or specific measures of link-based importance. While such analyses for predetermined properties can be effective in well-understood domains, sometimes identifying an appropriate property for analysis can be a challenge, and focusing on a single property may neglect other important aspects of the data. In this paper, we develop a foundation for mining the properties themselves. We present a theoretical framework defining the space of graph properties, a variety of mining queries enabled by the framework, techniques to handle the enormous size of the query space, and an experimental system called F-Miner that demonstrates the utility and feasibility of property mining.
Why collective inference improves relational classification
Authors: David D. Jensen, Jennifer Neville, Brian Gallagher
Venue: KDD
Year: 2004

Procedures for collective inference make simultaneous statistical judgments about the same variables for a set of related data instances. For example, collective inference could be used to simultaneously classify a set of hyperlinked documents or infer the legitimacy of a set of related financial transactions. Several recent studies indicate that collective inference can significantly reduce classification error when compared with traditional inference techniques. We investigate the underlying mechanisms for this error reduction by reviewing past work on collective inference and characterizing different types of statistical models used for making inference in relational data. We show important differences among these models, and we characterize the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data.
A system for automated mapping of bill-of-materials part numbers
Authors: Jayant Kalagnanam, Moninder Singh, Sudhir Verma, Michael Patek, Yuk Wah Wong
Venue: KDD
Year: 2004

Part numbers are widely used within an enterprise throughout the manufacturing process. The point of entry of such part numbers into this process is normally via a Bill of Materials, or BOM, sent by a contact manufacturer or supplier. Each line of the BOM provides information about one part such as the supplier part number, the BOM receiver's corresponding internal part number, an unstructured textual part description, the supplier name, etc. However, in a substantial number of cases, the BOM receiver's internal part number is absent. Hence, before this part can be incorporated into the receiver's manufacturing process, it has to be mapped to an internal part (of the BOM receiver) based on the information of the part in the BOM. Historically, this mapping process has been done manually which is a highly time-consuming, labor intensive and error-prone process. This paper describes a system for automating the mapping of BOM part numbers. The system uses a two step modeling and mapping approach. First, the system uses historical BOM data, receiver's part specifications data and receiver's part taxonomic data along with domain knowledge to automatically learn classification models for mapping a given BOM part description to successively lower levels of the receiver's part taxonomy to reduce the set of potential internal parts to which the BOM part could map to. Then, information about various part parameters is extracted from the BOM part description and compared to the specifications data of the potential internal parts to choose the final mapped internal part. Mappings done by the system are very accurate, and the system is currently being deployed within IBM for mapping BOMs received by the corporate procurement/manufacturing divisions.
When do data mining results violate privacy?
Authors: Murat Kantarcioglu, Jiashun Jin, Chris Clifton
Venue: KDD
Year: 2004

Privacy-preserving data mining has concentrated on obtaining valid results when the input data is private. An extreme example is Secure Multiparty Computation-based methods, where only the results are revealed. However, this still leaves a potential privacy breach: Do the results themselves violate privacy? This paper explores this issue, developing a framework under which this question can be addressed. Metrics are proposed, along with analysis that those metrics are consistent in the face of apparent problems.
Towards parameter-free data mining
Authors: Eamonn J. Keogh, Stefano Lonardi, Chotirat (Ann) Ratanamahatana
Venue: KDD
Year: 2004

Most data mining algorithms require the setting of many input parameters. Two main dangers of working with parameter-laden algorithms are the following. First, incorrect settings may cause an algorithm to fail in finding the true patterns. Second, a perhaps more insidious problem is that the algorithm may report spurious patterns that do not really exist, or greatly overestimate the significance of the reported patterns. This is especially likely when the user fails to understand the role of parameters in the data mining process.Data mining algorithms should have as few parameters as possible, ideally none. A parameter-free algorithm would limit our ability to impose our prejudices, expectations, and presumptions on the problem at hand, and would let the data itself speak to us. In this work, we show that recent results in bioinformatics and computational theory hold great promise for a parameter-free data-mining paradigm. The results are motivated by observations in Kolmogorov complexity theory. However, as a practical matter, they can be implemented using any off-the-shelf compression algorithm with the addition of just a dozen or so lines of code. We will show that this approach is competitive or superior to the state-of-the-art approaches in anomaly/interestingness detection, classification, and clustering with empirical tests on time series/DNA/text/video datasets.
Learning to detect malicious executables in the wild
Authors: Jeremy Z. Kolter, Marcus A. Maloof
Venue: KDD
Year: 2004

In this paper, we describe the development of a fielded application for detecting malicious executables in the wild. We gathered 1971 benign and 1651 malicious executables and encoded each as a training example using n-grams of byte codes as features. Such processing resulted in more than 255 million distinct n-grams. After selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive Bayes, decision trees, support vector machines, and boosting. Ultimately, boosted decision trees outperformed other methods with an area under the roc curve of 0.996. Results also suggest that our methodology will scale to larger collections of executables. To the best of our knowledge, ours is the only fielded application for this task developed using techniques from machine learning and data mining.
Learning spatially variant dissimilarity (SVaD) measures
Authors: Krishna Kummamuru, Raghu Krishnapuram, Rakesh Agrawal
Venue: KDD
Year: 2004

Clustering algorithms typically operate on a feature vector representation of the data and find clusters that are compact with respect to an assumed (dis)similarity measure between the data points in feature space. This makes the type of clusters identified highly dependent on the assumed similarity measure. Building on recent work in this area, we formally define a class of spatially varying dissimilarity measures and propose algorithms to learn the dissimilarity measure automatically from the data. The idea is to identify clusters that are compact with respect to the unknown spatially varying dissimilarity measure. Our experiments show that the proposed algorithms are more stable and achieve better accuracy on various textual data sets when compared with similar algorithms proposed in the literature.
Effective localized regression for damage detection in large complex mechanical structures
Authors: Aleksandar Lazarevic, Ramdev Kanapady, Chandrika Kamath
Venue: KDD
Year: 2004

In this paper, we propose a novel data mining technique for the efficient damage detection within the large-scale complex mechanical structures. Every mechanical structure is defined by the set of finite elements that are called structure elements. Large-scale complex structures may have extremely large number of structure elements, and predicting the failure in every single element using the original set of natural frequencies as features is exceptionally time-consuming task. Traditional data mining techniques simply predict failure in each structure element individually using global prediction models that are built considering all data records. In order to reduce the time complexity of these models, we propose a localized clustering-regression based approach that consists of two phases: (1) building a local cluster around a data record of interest and (2) predicting an intensity of damage only in those structure elements that correspond to data records from the built cluster. For each test data record, we first build a cluster of data records from training data around it. Then, for each data record that belongs to discovered cluster, we identify corresponding structure elements and we build a localized regression model for each of these structure elements. These regression models for specific structure elements are constructed using only a specific set of relevant natural frequencies and merely those data records that correspond to the failure of that structure element. Experiments performed on the problem of damage prediction in a large electric transmission tower frame indicate that the proposed localized clustering-regression based approach is significantly more accurate and more computationally efficient than our previous hierarchical clustering approach, as well as global prediction models.
Incremental maintenance of quotient cube for median
Authors: Cuiping Li, Gao Cong, Anthony K. H. Tung, Shan Wang
Venue: KDD
Year: 2004

Data cube pre-computation is an important concept for supporting OLAP(Online Analytical Processing) and has been studied extensively. It is often not feasible to compute a complete data cube due to the huge storage requirement. Recently proposed quotient cube addressed this issue through a partitioning method that groups cube cells into equivalence partitions. Such an approach is not only useful for distributive aggregate functions such as SUM but can also be applied to the holistic aggregate functions like MEDIAN.Maintaining a data cube for holistic aggregation is a hard problem since its difficulty lies in the fact that history tuple values must be kept in order to compute the new aggregate when tuples are inserted or deleted. The quotient cube makes the problem harder since we also need to maintain the equivalence classes. In this paper, we introduce two techniques called addset data structure and sliding window to deal with this problem. We develop efficient algorithms for maintaining a quotient cube with holistic aggregation functions that takes up reasonably small storage space. Performance study shows that our algorithms are effective, efficient and scalable over large databases.
Clustering moving objects
Authors: Yifan Li, Jiawei Han, Jiong Yang
Venue: KDD
Year: 2004

Due to the advances in positioning technologies, the real time information of moving objects becomes increasingly available, which has posed new challenges to the database research. As a long-standing technique to identify overall distribution patterns in data, clustering has achieved brilliant successes in analyzing static datasets. In this paper, we study the problem of clustering moving objects, which could catch interesting pattern changes during the motion process and provide better insight into the essence of the mobile data points. In order to catch the spatial-temporal regularities of moving objects and handle large amounts of data, micro-clustering [20] is employed. Efficient techniques are proposed to keep the moving micro-clusters geographically small. Important events such as the collisions among moving micro-clusters are also identified. In this way, high quality moving micro-clusters are dynamically maintained, which leads to fast and competitive clustering result at any given time instance. We validate our approaches with a through experimental evaluation, where orders of magnitude improvement on running time is observed over normal K-Means clustering method [14].