A k-means type clustering algorithm for subspace clustering of mixed numeric and categorical datasets

Almost all subspace clustering algorithms proposed so far are designed for numeric datasets. In this paper, we present a k-means type clustering algorithm that finds clusters in data subspaces in mixed numeric and categorical datasets. In this method, we compute attributes contribution to different clusters. We propose a new cost function for a k-means type algorithm. One of the advantages of this algorithm is its complexity which is linear with respect to the number of the data points. This algorithm is also useful in describing the cluster formation in terms of attributes contribution to different clusters. The algorithm is tested on various synthetic and real datasets to show its effectiveness. The clustering results are explained by using attributes weights in the clusters. The clustering results are also compared with published results.     

Genetic Threading

The biological function of proteins is dependent, to a large extent, on their native three dimensional conformation. Thus, it is important to know the structure of as many proteins as possible. Since experimental methods for structure determination are very tedious, there is a significant effort to calculate the structure of a protein from its linear sequence. Direct methods of calculating structure from sequence are not available yet. Thus, an indirect approach to predict the conformation of protein, called threading, is discussed. In this approach, known structures are used as constraints, to restrict the search for the native conformation. Threading requires finding good alignments between a sequence and a structure, which is a major computational challenge and a practical bottleneck in applying threading procedures. The Genetic Algorithm paradigm, an efficient search method that is based on evolutionary ideas, is used to perform sequence to structure alignments. A proper representation is discussed in which genetic operators can be effectively implemented. The algorithm performance is tested for a set of six sequence/structure pairs. The effects of changing operators and parameters are explored and analyzed.     

Resource-efficient routing and scheduling of time-constrained streaming communication on networks-on-chip

Network-on-chip-based multiprocessor systems-on-chip are considered as future embedded systems platforms. One of the steps in mapping an application onto such a parallel platform involves scheduling the communication on the network-on-chip. This paper presents different scheduling strategies that minimize resource usage by exploiting all scheduling freedom offered by networks-on-chip. It also introduces a technique to take the dynamism in applications into account when scheduling the communication of an application on the network-on-chip while minimizing the resource usage. Our experiments show that resource-utilization is improved when compared to existing techniques.     

Impacts in multibody systems: modeling and experiments

This paper outlines a novel approach to the modeling and analysis of impact involving multibody systems. This approach is based on an analysis of energy absorption and restitution during impact, using a decomposition of the kinetic energy, which decouples the parts associated with the spaces of admissible and constrained motions of the underlying unilateral constraints. Such a decomposition turns out to be useful in the analysis of energy dissipation during impact, and leads to a generalized definition of the energetic coefficient of restitution, which targets particularly collisions in multibody systems. The applicability of the approach reported is investigated by conducting an experimental study on a robotic testbed. It is shown that impact between multibody systems is considerably affected not only by the local dynamics characteristics of the interacting bodies, but also the configuration of the whole multibody system. The results reported here show that our decomposition can offer a sound characterization of impact in several problems of multibody systems.     

Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems

In this paper we investigate data structures obtained by a recursive partitioning of the multi- dimensional input domain into regions of equal size. One of the best known examples of such a structure is the quadtree . It is used here as a basis for more complex data structures. We also provide multidimensional versions of the stratified tree by van Emde Boas [vEB]. We show that under the assumption that the input points have limited precision (i.e., are drawn from the integer grid of size u ) these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for dynamic approximate nearest neighbor (under insertions and deletions) and exact on-line closest pair (under insertions only) in any constant number of dimensions. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear time (optimal) algorithm for computing the expansion of a shape represented by a region quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the operation of dilation by a ball. Received January 19, 1999; revised November 4, 1999.     

Efficient matching of nonrectangular shapes

Most known two-dimensional matching algorithms have a rectangular text (image) and rectangular pattern (template) as their input. These matching algorithms perform a row by row analysis followed by some column processing. These techniques are only efficient if all the rows are of equal length, hence the necessity for rectangular patterns.We present a novel method for analysing patterns with rows of different lengths. This enables finding all occurrences of a nonrectangular figure of heightm in ann×n text in time . We make use of thesmaller matching problem.The smaller matching problem is that of finding all appearances of a numerical one dimensional pattern in a numerical one-dimensional text, where every element of the pattern is no greater than the corresponding text element.Partially supported by NSF grant CCR-88-03641 and a University of Maryland full year research award.Supported by a University of Maryland Graduate Fellowship, an ACM Samuel M. Alexander Fellowship and NSF grant CCR-88-03641.     

Multi-product multi-chance-constraint stochastic inventory control problem with dynamic demand and partial back-ordering: A harmony search algorithm

In this paper, a multiproduct inventory control problem is considered in which the periods between two replenishments of the products are assumed independent random variables, and increasing and decreasing functions are assumed to model the dynamic demands of each product. Furthermore, the quantities of the orders are assumed integer-type, space and budget are constraints, the service-level is a chance-constraint, and that the partial back-ordering policy is taken into account for the shortages. The costs of the problem are holding, purchasing, and shortage. We show the model of this problem is an integer nonlinear programming type and to solve it, a harmony search approach is used. At the end, three numerical examples of different sizes are given to demonstrate the applicability of the proposed methodology in real world inventory control problems, to validate the results obtained, and to compare its performances with the ones of both a genetic and a particle swarm optimization algorithms.     

Optimum loading of machines in a flexible manufacturing system using a mixed-integer linear mathematical programming model and genetic algorithm

Machine loading problem in a flexible manufacturing system (FMS) encompasses various types of flexibility aspects pertaining to part selection and operation assignments. The evolution of flexible manufacturing systems offers great potential for increasing flexibility by ensuring both cost-effectiveness and customized manufacturing at the same time. This paper proposes a linear mathematical programming model with both continuous and zero-one variables for job selection and operation allocation problems in an FMS to maximize profitability and utilization of system. The proposed model assigns operations to different machines considering capacity of machines, batch-sizes, processing time of operations, machine costs, tool requirements, and capacity of tool magazine. A genetic algorithm (GA) is then proposed to solve the formulated problem. Performance of the proposed GA is evaluated based on some benchmark problems adopted from the literature. A statistical test is conducted which implies that the proposed algorithm is robust in finding near-optimal solutions. Comparison of the results with those published in the literature indicates supremacy of the solutions obtained by the proposed algorithm for attempted model.     

Optimal pricing, lot-sizing and marketing planning in a capacitated and imperfect production system

In the classical economic production quantity (EPQ) problem demand is considered to be known in advance. However, in the real-world, demand of a product is a function of factors such as product’s price, its quality, and marketing expenditures for promoting the product. Quality level of the product and specifications of the adopted manufacturing process also affect the unit product’s cost. Therefore, in this paper we consider a profit maximizing firm who wants to jointly determine the optimal lot-sizing, pricing, and marketing decisions along with manufacturing requirements in terms of flexibility and reliability of the process. Geometric programming (GP) technique is proposed to address the resulting nonlinear optimization problem. Using recent advances in optimization techniques we are able to optimally solve the developed, highly nonlinear, mathematical model. Finally, using numerical examples, we illustrate the solution approach and analyze the solution under different conditions.     

Maintaining awareness using policies; Enabling agents to identify relevance of information

The field of computer supported cooperative work aims at providing information technology models, methods, and tools that assist individuals to cooperate. The presented paper is based on three main observations from literature. First, one of the problems in utilizing information technology for cooperation is to identify the relevance of information, called awareness. Second, research in computer supported cooperative work proposes the use of agent technologies to aid individuals to maintain their awareness. Third, literature lacks the formalized methods on how software agents can identify awareness. This paper addresses the problem of awareness identification. The main contribution of this paper is to propose and evaluate a formalized structure, called Policy-based Awareness Management (PAM). PAM extends the logic of general awareness in order to identify relevance of information. PAM formalizes existing policies into Directory Enabled Networks-next generation structure and uses them as a source for awareness identification. The formalism is demonstrated by applying PAM to the space shuttle Columbia disaster occurred in 2003. The paper also argues that efficacy and cost-efficiency of the logic of general awareness will be increased by PAM. This is evaluated by simulation of hypothetical scenarios as well as a case study.