The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an O(k3) guarantee for this objective function and an O(k2) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of O(k2) for the squared distance measure and O(k) for the distance measure.

The k-means algorithm is widely used for clustering because of its computational efficiency. Given n points in d-dimensional space and the number of desired clusters k, k-means seeks a set of k cluster centers so as to minimize the sum of the squared Euclidean distance between each point and its nearest cluster center. However, the algorithm is very sensitive to the initial selection of centers and is likely to converge to partitions that are significantly inferior to the global optimum. We present a genetic algorithm (GA) for evolving centers in the k-means algorithm that simultaneously identifies good partitions for a range of values around a specified k. The set of centers is represented using a hyper-quadtree constructed on the data. This representation is exploited in our GA to generate an initial population of good centers and to support a novel crossover operation that selectively passes good subsets of neighboring centers from parents to offspring by swapping subtrees. Experimental results indicate that our GA finds the global optimum for data sets with known optima and finds good solutions for large simulated data sets.

This paper presents a clustering algorithm for partitioning a minimum spanning tree with a constraint on minimum group size. The problem is motivated by microaggregation, a disclosure limitation technique in which similar records are aggregated into groups containing a minimum of k records. Heuristic clustering methods are needed since the minimum information loss microaggregation problem is NP-hard. Our MST partitioning algorithm for microaggregation is sufficiently efficient to be practical for large data sets and yields results that are comparable to the best available heuristic methods for microaggregation. For data that contain pronounced clustering effects, our method results in significantly lower information loss. Our algorithm is general enough to accommodate different measures of information loss and can be used for other clustering applications that have a constraint on minimum group size.

Microaggregation is a technique used by statistical agencies to limit disclosure of sensitive microdata. Noting that no polynomial algorithms are known to microaggregate optimally, Domingo-Ferrer and Mateo-Sanz have presented heuristic microaggregation methods. This paper is the first to present an efficient polynomial algorithm for optimal univariate microaggregation. Optimal partitions are shown to correspond to shortest paths in a network.

An evolutionary algorithm (EA) approach is used to generate test vectors for the detection of shrinkage faults in programmable logic arrays (PLA). Three basic steps are performed during the generation of the test vectors: crossover, mutation and selection. A new mutation operator is introduced that helps increase the Hamming distance among the candidate solutions. Once crossover and mutation have occurred, the new candidate test vectors with higher fitness function scores replace the old ones. With this scheme, population members steadily improve their fitness level with each new generation. The resulting process yields improved solutions to the problem of the PLA test vector generation for shrinkage faults. PLA testing and fault simulation is computationally prohibitive in uniprocessor machines. However, PLAGA is well suited for powerful parallel processing machines with vectorization capability,.

A probabilistic framework can be used to assess the risk of disclosure of confidential information in statistical databases that use disclosure control mechanisms. The authors show how the method may be used to assess the strengths and weaknesses of two existing disclosure control mechanisms: the query set size restriction control and random sample query control mechanisms. Results indicate that neither scheme provides adequate security. The framework is then further exploited to analyze an alternative scheme combining query set size restriction and random sample query control. It is shown that this combination results in a significant decrease in the risk of disclosure.>