Peritoneal dialysis (PD) removes waste products from blood when the kidney is malfunctioned. Since there is no clear criterion for PD recommendation for patients with kidney disease, existing machine learning models (ML), which rely on credible decision criterion, are ineffective in making PD eligibility decisions, especially when the correlated traits or indicators (patterns) inherent in the PD data are diverse and subtle. Furthermore, the lack of interpretable transparency in traditional ML also weakens the credibility of the decision they produce. Hence, an in-depth knowledge of the patients' characteristics is needed to render a clearer picture of the decision-making process and model to detect the rare PD eligibility cases. In this paper, we extend our previous work (Attribute-Value-Association Discovery and Disentanglement (ADD)), to an extended ADD for PD data analysis (PD-ADD) to overcome these problems. We show that PD-ADD is able to discover association patterns of patient profiles and symptoms to reveal PD characteristics and detect eligible rare cases. Experimental results show that PDADD is much superior to existing unsupervised clustering (with accuracy of 89.87% vs 73.37% of K-Means). It also enables straightforward interpretation of the underlying relations of patient characteristics in an unsupervised setting.

Functional region identification is of fundamental importance for protein sequences analysis for a protein family. Such knowledge not only provides a better scientific understanding but also assists drug discovery. Domain annotation is one approach but it needs to leverage existing databases. For de novo discovery, motif discovery locates and aligns locally similar sub-sequences and represents them as a position-weight matrix (PWM). However, PWM is a fixed-length model whereas protein functional region size varies. Furthermore, to obtain a PWM, a width range parameter needs to be identified through exhaustive search. Hence, it is computational intensive for large dataset. This paper presents a new method known as Pattern-Directed Aligned Pattern Clustering (PD-APCn) to discover and align residues in conserved protein functional regions. It adopts Aligned Pattern Cluster (APC) as the representation model which allows variable pattern length. It uses patterns with strong support to direct the incremental expansion of the APCs, allowing substitution and frame-shift mutations, until a robust termination condition is reached. The concept of breakpoint gap is introduced to identify uncovered conserved patterns with substitution and frame-shift mutations, where these are often rare mutants. To evaluate the performance of PD-APCn, we conducted experiments on synthetic datasets with different size and noise level. Comparing with the popular motif discovery algorithm MEME, PD-APCn has demonstrated competitive performance throughout the experiments, obtaining a higher recall and F measure with up to 400× significant computational speed up comparing to MEME.

Proteins from the same family have similar functions. Hence, it is important to discover from a protein family conserved sequence patterns with variations to unveil the functionality of a functional domain. Aligned Pattern Clusters (APCs) are knowledge-rich representations comparing with probabilistic models. If significant aligned residue associations (ARAs) were discovered in APCs, they could reveal subtle functional or subgroup characteristics. However, when ARAs corresponding to different subgroups/classes were entangled due to certain subtle factors, to disentangle them to reveal succinct ARA groups is a big challenge. This paper presents a novel method known as Aligned Residual Association Discovery and Disentanglement (ARADD), to meet such challenge. ARADD first constructs an ARA Frequency Matrix (ARAFM) and converts it into a Statistical Residual (SR) Vector Space (SRV) to suppress noise. SR measures the deviation of the observed frequency of an event against that when the occurrence is random. By applying Principal Component Decomposition (PCD) on the SRV, we obtain PCs ranked by their variance. The ARAs of an AR with others can be represented by an AR-vector whose coordinates account for its associations with others. When the projection of an AR vector on a PC Space is reprojected to the SRV (abbreviated by RSRVs), its coordinates reflect the SRs of that AR associating with other ARs. Experiments showed that the ARADD can a) disentangle entangled ARAs in APCs, b) reveal subtle AR clusters relating to classes or ARAs within or between subgroups - significant to proteomic research, drug discovery and personalized medicine.

Understanding binding cores is of fundamental importance in deciphering Protein-DNA (TF-TFBS) binding and gene regulation. Limited by expensive experiments, it is promising to discover them with variations directly from sequence data. Although existing computational methods have produced satisfactory results, they are one-to-one mappings with no site-specific information on residue/nucleotide variations, where these variations in binding cores may impact binding specificity. This study presents a new representation for modeling binding cores by incorporating variations and an algorithm to discover them from only sequence data. Our algorithm takes protein and DNA sequences from TRANSFAC (a Protein-DNA Binding Database) as input; discovers from both sets of sequences conserved regions in Aligned Pattern Clusters (APCs); associates them as Protein-DNA Co-Occurring APCs; ranks the Protein-DNA Co-Occurring APCs according to their co-occurrence, and among the top ones, finds three-dimensional structures to support each binding core candidate. If successful, candidates are verified as binding cores. Otherwise, homology modeling is applied to their close matches in PDB to attain new chemically feasible binding cores. Our algorithm obtains binding cores with higher precision and much faster runtime ( ≥ 1,600x) than that of its contemporaries, discovering candidates that do not co-occur as one-to-one associated patterns in the raw data. AVAILABILITY: http://www.pami.uwaterloo.ca/~ealee/files/tcbbPnDna2015/Release.zip.

A Content-Based Image Retrieval (CBIR) system which identifies similar medical images based on a query image can assist clinicians for more accurate diagnosis. The recent CBIR research trend favors the construction and use of binary codes to represent images. Deep architectures could learn the non-linear relationship among image pixels adaptively, allowing the automatic learning of high-level features from raw pixels. However, most of them require class labels, which are expensive to obtain, particularly for medical images. The methods which do not need class labels utilize a deep autoencoder for binary hashing, but the code construction involves a specific training algorithm and an ad-hoc regularization technique. In this study, we explored using a deep de-noising autoencoder (DDA), with a new unsupervised training scheme using only backpropagation and dropout, to hash images into binary codes. We conducted experiments on more than 14,000 x-ray images. By using class labels only for evaluating the retrieval results, we constructed a 16-bit DDA and a 512-bit DDA independently. Comparing to other unsupervised methods, we succeeded to obtain the lowest total error by using the 512-bit codes for retrieval via exhaustive search, and speed up 9.27 times with the use of the 16-bit codes while keeping a comparable total error. We found that our new training scheme could reduce the total retrieval error significantly by 21.9%. To further boost the image retrieval performance, we developed Radon Autoencoder Barcode (RABC) which are learned from the Radon projections of images using a de-noising autoencoder. Experimental results demonstrated its superior performance in retrieval when it was combined with DDA binary codes.

MOTIVATION: Evolutionarily conserved amino acids within proteins characterize functional or structural regions. Conversely, less conserved amino acids within these regions are generally areas of evolutionary divergence. A priori knowledge of biological function and species can help interpret the amino acid differences between sequences. However, this information is often erroneous or unavailable, hampering discovery with supervised algorithms. Also, most of the current unsupervised methods depend on full sequence similarity, which become inaccurate when proteins diverge (e.g. inversions, deletions, insertions). Due to these and other shortcomings, we developed a novel unsupervised algorithm which discovers highly conserved regions and uses two types of information measures: (i) data measures computed from input sequences; and (ii) class measures computed using a priori class groupings in order to reveal subgroups (i.e. classes) or functional characteristics. RESULTS: Using known and putative sequences of two proteins belonging to a relatively uncharacterized protein family we were able to group evolutionarily related sequences and identify conserved regions, which are strong homologous association patterns called Aligned Pattern Clusters, within individual proteins and across the members of this family. An initial synthetic demonstration and in silico results reveal that (i) the data measures are unbiased and (ii) our class measures can accurately rank the quality of the evolutionarily relevant groupings. Furthermore, combining our data and class measures allowed us to interpret the results by inferring regions of biological importance within the binding domain of these proteins. Compared to popular supervised methods, our algorithm has a superior runtime and comparable accuracy. AVAILABILITY AND IMPLEMENTATION: The dataset and results are available at www.pami.uwaterloo.ca/∼ealee/files/classification2015 CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Understanding Protein-protein interaction (PPI) is of fundamental importance in deciphering cellular processes. Predicting PPIs is thus critical in making new discoveries in the biological domains. Traditionally, new PPIs are identified through biochemical experiments but such methods are labor-intensive, expensive, time-consuming and technically ineffective due to high false positive rates. Computational docking is an alternative but requires the three-dimensional structures of the target proteins which are not always accessible. Sequence-based prediction is the most readily applicable and cost-effective method. It exploits known PPI Databases to construct classifiers for predicting unknown PPIs based only on sequence data. However, existing methods, adopting features that fix the pattern length and use exact patterns, are biologically unrealistic. Also, those based on SVM and String Kernel are hardly biologically interpretable since they do not compute the features. Recently, we have developed a new method for predicting PPI known as WeMine-P2P based on our WeMine Aligned Pattern Clustering algorithm which discovers and identifies the localized and co-occurring conserved patterns and regions allowing variable length and pattern variations. As our first attempt, under 40 independent experiments, we showed that (1) WeMine-P2P outperforms the well-known algorithm, PIPE2 which also utilizes co-occurring amino acid sequence segments but does not allow variable lengths and pattern variations; (2) Unlike SVM-based methods, WeMine-P2P renders interpretable biological features; (3) WeMine-P2P achieves satisfactory PPI prediction performance, comparable to the SVM-based methods particularly in unseen protein sequences, with a potential reduction of feature dimension of 1280x. WeMine-P2P is extendable to other biosequence interactions such as predicting Protein-DNA interactions.

Understanding binding cores is of fundamental importance in deciphering Protein-DNA (TF-TFBS) binding and gene regulation. Variations (or mutations) in binding cores are ubiquitous and have different levels of effects on the binding specificity. To alleviate expensive experiments, we have developed a new method to discover directly from sequence data binding cores and study the effect due to variations. Although existing computational methods have produced satisfactory TF-TFBS binding cores, they are only one-to-one mappings with no site-specific information on residue/nucleotide variations; and also are largely overlapped. In this study, we propose a new representation for modeling TF-TFBS binding with variants known as TF-TFBS Co-Supportive Aligned Pattern Clusters (APCs), which are more compact, with more details for site-specific variants, and biologically more intuitive for analysis. To achieve this task, we have also developed an algorithm to discover TF-TFBS Co-Supportive APCs to capture binding cores at a higher precision with much faster runtime (≥1600X) comparing to other methods. The variants in TF-TFBS Co-Supportive APCs are also statistically analyzed and demonstrated that they can assist homology modeling to synthesize new biological knowledge.

BACKGROUND: The large influx of biological sequences poses the importance of identifying and correlating conserved regions in homologous sequences to acquire valuable biological knowledge. These conserved regions contain statistically significant residue associations as sequence patterns. Thus, patterns from two conserved regions co-occurring frequently on the same sequences are inferred to have joint functionality. A method for finding conserved regions in protein families with frequent co-occurrence patterns is proposed. The biological significance of the discovered clusters of conserved regions with co-occurrences patterns can be validated by their three-dimensional closeness of amino acids and the biological functionality found in those regions as supported by published work. METHODS: Using existing algorithms, we discovered statistically significant amino acid associations as sequence patterns. We then aligned and clustered them into Aligned Pattern Clusters (APCs) corresponding to conserved regions with amino acid conservation and variation. When one APC frequently co-occurred with another APC, the two APCs have high co-occurrence. We then clustered APCs with high co-occurrence into what we refer to as Co-occurrence APC Clusters (Co-occurrence Clusters). RESULTS: Our results show that for Co-occurrence Clusters, the three-dimensional distance between their amino acids is closer than average amino acid distances. For the Co-occurrence Clusters of the ubiquitin and the cytochrome c families, we observed biological significance among the residing amino acids of the APCs within the same cluster. In ubiquitin, the residues are responsible for ubiquitination as well as conventional and unconventional ubiquitin-bindings. In cytochrome c, amino acids in the first co-occurrence cluster contribute to binding of other proteins in the electron transport chain, and amino acids in the second co-occurrence cluster contribute to the stability of the axial heme ligand. CONCLUSIONS: Thus, our co-occurrence clustering algorithm can efficiently find and rank conserved regions that contain patterns that frequently co-occurring on the same proteins. Co-occurring patterns are biologically significant due to their three-dimensional closeness and other evidences reported in literature. These results play an important role in drug discovery as biologists can quickly identify the target for drugs to conduct detailed preclinical studies.

Discovering sequence patterns with variations unveils significant functions of a protein family. Existing combinatorial methods of discovering patterns with variations are computationally expensive, and probabilistic methods require more elaborate probabilistic representation of the amino acid associations. To overcome these shortcomings, this paper presents a new computationally efficient method for representing patterns with variations in a compact representation called Aligned Pattern Cluster (AP Cluster). To tackle the runtime, our method discovers a shortened list of non-redundant statistically significant sequence associations based on our previous work. To address the representation of protein functional regions, our pattern alignment and clustering step, presented in this paper captures the conservations and variations of the aligned patterns. We further refine our solution to allow more coverage of sequences via extending the AP Clusters containing only statistically significant patterns to Weak and Conserved AP Clusters. When applied to the cytochrome c, the ubiquitin, and the triosephosphate isomerase protein families, our algorithm identifies the binding segments as well as the binding residues. When compared to other methods, ours discovers all binding sites in the AP Clusters with superior entropy and coverage. The identification of patterns with variations help biologists to avoid time-consuming simulations and experimentations. (Software available upon request).

Multivariate time series are common in many application domains, particularly in industrial processes with a large number of sensors installed for process monitoring and control. Often, such data encapsulate complex relations among individual series. This paper presents a new type of patterns in multivariate time series, referred to as temporal associations, to capture a wide range of local relations along and across individual series. A scalable algorithm is developed to discover frequent associations by incorporating (1) redundancy pruning of patterns in single time series and (2) two conditions to avoid over-counting the occurrences of associations, thus greatly reducing the space and runtime complexity of the discovery process. A statistical significance measure is also introduced for ranking and post-pruning discovered associations. To evaluate the proposed method, synthetic data sets and a real world data set taken from the time series mining repository as well as a large data set obtained from a delayed coking plant are used. The experiments demonstrated that the discovered associations capture the local relations in multiple time series and that the proposed method is scalable to large data sets.

Advances in bioinformatics have provided researchers with a large influx of novel sequences, thus making the analysis of the sequences for inherent biological knowledge crucial. By using pattern discovery and pattern synthesis on protein family sequences, conserved protein segments can be represented by Aligned Pattern Clusters (APC), which is more knowledge-rich in statistical association comparing to probabilistic models. Such representation enabled us to exploit their co-occurrence on the same protein sequence to identify functional regions. In this paper, we developed an efficient algorithm to identify the frequently co-occurring patterns using only homologous protein sequences as input. We applied our algorithm to triosephosphate isomerase and ubiquitin for a detailed study. We found that the discovered co-occurring patterns are close in spatial distance in most cases, by comparing to corresponding 3D structures. We also found that the co-occurrence of patterns are biologically significant. Residues which play important and co-operative roles in the glycolytic pathway of triosephosphate isomerase and residues which are responsible for ubiquitination and ubiquitin-binding of ubiquitin are all covered in our co-occurring APCs. These results demonstrate the power of our algorithm to reveal the concurrent distant functional and structural relation of proteins sequences based on co-occurrence clusters of APCs.

Discovering protein patterns for amino acids and their biochemical properties is important for revealing the underlying biophysical models. From this, pattern clustering was introduced in order to relate the discovered protein patterns to taxonomic classes in a localized region of a protein. This paper proposes an algorithm to synthesize and re-group pattern clusters, maximizing their separability in order to reveal class characteristics of the localized region of the protein based on our previous work. To evaluate the pattern clustering and regrouping pattern clusters results, we introduce three evaluation measures: F-measure, class entropy measure, and attribute entropy measure. To validate our proposed algorithm, experiments are run on synthetic data, protein family for amino acid attributes, and chemical property attributes. The experimental results show that: a) the result for regrouping pattern clusters is more accurate in class separation than only using pattern clustering; b) The clusters after regrouping are more distinctly separable with each other than only using pattern clustering; c) two types of pattern clusters are found, with one pertaining to distinct classes and the other associating with two or more related classes; and d) class characteristics are clearly revealed in the data subspace containing the patterns in the pattern clusters. The datasets with chemical properties show that unsupervised techniques can reveal common chemical attributes in the inherent classes as more of the common properties shared by different amino acids are taken into account

A basic task in protein analysis is to discover a set of sequence patterns that reflect the function of a protein family. This set of sequence patterns contains non-exact significant residue associations. Currently, the existing combinatorial methods are computationally expensive and probabilistic methods require richer representation of the amino acid associations. To undertake this task, we create a synthesized pattern representation called an Aligned Pattern (AP) Cluster that identifies the residue associations in the binding segment and the site variations in the aligned residues. In this paper, our algorithm identifies the binding segments for two protein families: the Cytochrome Complex and the Ubiquitin protein families. For each of the experiments, the AP Clusters obtained correspond to protein binding segments including a few beyond those identified by the other protein databases, PROSITE and pFam. Furthermore, the columns of aligned sites that exist only as a single value in the AP Clusters also corresponds to the binding residues. Additional information retained by the AP Clusters can reveal the amino acid residues of interest, thus averting time-consuming simulations and experimentation.

Discovering patterns from sequence data has significant impact in many aspects of science and society, especially in genomics and proteomics. Here we consider multiple strings as input sequence data and substrings as patterns. In the real world, usually a large set of patterns could be discovered yet many of them are redundant, thus degrading the output quality. This paper improves the output quality by removing two types of redundant patterns. First, the notion of delta tolerance closed itemset is employed to remove redundant patterns that are not delta closed. Second, the concept of statistically induced patterns is proposed to capture redundant patterns which seem to be statistically significant yet their significance is induced by their strong significant subpatterns. It is computationally intense to mine these nonredundant patterns (delta closed patterns and noninduced patterns). To efficiently discover these patterns in very large sequence data, two efficient algorithms have been developed through innovative use of suffix tree. Three sets of experiments were conducted to evaluate their performance. They render excellent results when applying to genomics. The experiments confirm that the proposed algorithms are efficient and that they produce a relatively small set of patterns which reveal interesting information in the sequences.

BACKGROUND: Discovering patterns from gene expression levels is regarded as a classification problem when tissue classes of the samples are given and solved as a discrete-data problem by discretizing the expression levels of each gene into intervals maximizing the interdependence between that gene and the class labels. However, when class information is unavailable, discovering gene expression patterns becomes difficult. METHODS: For a gene pool with large number of genes, we first cluster the genes into smaller groups. In each group, we use the representative gene, one with highest interdependence with others in the group, to drive the discretization of the gene expression levels of other genes. Treating intervals as discrete events, association patterns of events can be discovered. If the gene groups obtained are crisp gene clusters, significant patterns overlapping different gene clusters cannot be found. This paper presents a new method of "fuzzifying" the crisp gene clusters to overcome such problem. RESULTS: To evaluate the effectiveness of our approach, we first apply the above described procedure on a synthetic data set and then a gene expression data set with known class labels. The class labels are not being used in both analyses but used later as the ground truth in a classificatory problem for assessing the algorithm's effectiveness in fuzzy gene clustering and discretization. The results show the efficacy of the proposed method. The existence of correlation among continuous valued gene expression levels suggests that certain genes in the gene groups have high interdependence with other genes in the group. Fuzzification of a crisp gene cluster allows the cluster to take in genes from other clusters so that overlapping relationship among gene clusters could be uncovered. Hence, previously unknown hidden patterns resided in overlapping gene clusters are discovered. From the experimental results, the high order patterns discovered reveal multiple gene interaction patterns in cancerous tissues not found in normal tissues. It was also found that for the colon cancer experiment, 70% of the top patterns and most of the discriminative patterns between cancerous and normal tissues are among those spanning across different crisp gene clusters. CONCLUSIONS: We show that the proposed method for analyzing the error-prone microarray is effective even without the presence of tissue class information. A unified framework is presented, allowing fast and accurate pattern discovery for gene expression data. For a large gene set, to discover a comprehensive set of patterns, gene clustering, gene expression discretization and gene cluster fuzzification are absolutely necessary.

Discovering patterns from gene expression levels is regarded as a classification problem when tissue classes of the samples are given and solved as a discrete-data problem by discretizing the expression levels of each gene into intervals maximizing the interdependence between that gene and the class labels. However, when class information is unavailable, discovering gene expression patterns becomes difficult. This paper attempts to tackle this important problem. For a gene pool with large number of genes, we first cluster the genes into smaller groups. In each group, we use the representative gene, one with highest interdependence with others in the group, to drive the discretization of the gene expression levels of other genes. Treating intervals as discrete events, association patterns can be discovered. If the gene groups obtained are crisp clusters, significant patterns overlapping different clusters cannot be found. This paper presents a new method of “fuzzifying” the crisp attribute clusters for that purpose. To evaluate the effectiveness of our approach, we first apply the above described procedure on a synthetic dataset and then a gene expression dataset with known class labels. The class labels are not being used in both analyses but used later as the ground truth in a classificatory problem for assessing the algorithm's effectiveness in fuzzy gene clustering and discretization. The results show the efficacy of the proposed method.

In business and industry today, large databases with mixed data types (continuous and categorical) are very common. There are great needs to discover patterns from them for knowledge interpretation and understanding. In the past, for classification, this problem is solved as a discrete data problem by first discretizing the continuous data based on the class-attribute interdependence relationship. However, so far no proper solution exists when class information is unavailable. Hence, important pattern post-processing tasks such as pattern clustering and summarization cannot be applied to mixed-mode data. This paper presents a new method for solving the problem. It is based on two essential concepts. (1) Though class information is absent, yet for a correlated dataset, the attribute with the strongest interdependence with others in the group can be used to drive the discretization of the continuous data. (2) For a large database, correlated attribute groups must first be obtained by attribute clustering before (1) can be applied. Based on (1) and (2), pattern discovery methods are developed for mixed-mode data. Extensive experiments using synthetic and real world data were conducted to validate the usefulness and effectiveness of the proposed method.

Classification of data with imbalanced class distribution has encountered a significant drawback of the performance attainable by most standard classifier learning algorithms which assume a relatively balanced class distribution and equal misclassification costs. This paper provides a review of the classification of imbalanced data regarding: the application domains; the nature of the problem; the learning difficulties with standard classifier learning algorithms; the learning objectives and evaluation measures; the reported research solutions; and the class imbalance problem in the presence of multiple classes.

In data mining and knowledge discovery, pattern discovery extracts previously unknown regularities in the data and is a useful tool for categorical data analysis. However, the number of patterns discovered is often overwhelming. It is difficult and time-consuming to 1) interpret the discovered patterns and 2) use them to further analyze the data set. To overcome these problems, this paper proposes a new method that clusters patterns and their associated data simultaneously. When patterns are clustered, the data containing the patterns are also clustered; and the relation between patterns and data is made explicit. Such an explicit relation allows the user on the one hand to further analyze each pattern cluster via its associated data cluster, and on the other hand to interpret why a data cluster is formed via its corresponding pattern cluster. Since the effectiveness of clustering mainly depends on the distance measure, several distance measures between patterns and their associated data are proposed. Their relationships to the existing common ones are discussed. Once pattern clusters and their associated data clusters are obtained, each of them can be further analyzed individually. To evaluate the effectiveness of the proposed approach, experimental results on synthetic and real data are reported.

Genome comparison is very useful for deriving evolutionary and functional relationships between genomes. Previous works on genome comparison focus mainly on comparing the entire genome at the nucleotide level. As interesting patterns exist also at the gene and segment level, we propose an algorithm called Multi- Level Genome Comparison Algorithm (MGC) that can allow genome comparison to be performed at multi-level while sequential and regional consistency of gene segments can be determined. Different genomes may have common sub-sequences that differ with each other due to processes such as mutations, lateral transfers, gene rearrangements that cannot be easily identified. The result is that not all the genes can form a certain one-to-one matching gene pair. One-to-many or many-to-many ambiguity relationships may exist . MGC takes this ambiguity into consideration and represents genomes with a new graph representation known as Multi-Level Attributed Graph Mining Algorithm (MAGMA). We tested MGC with the intra- and inter-species of Chlamydia genomes. The results show that the proposed algorithm is able to discover the similarities and dissimilarities among different genomes, while in addition, to confirm the specific role of the gene in the genomes and provide variations among species and similarity within species. KEY WORDS Genome comparison, multi-level, consistency, segment, graph

This is a correction to a typographical error in (11) in [1] which present the calculation of the sum of the multiple significant interdependence redundancy measure. Equation (11) in [1] should be: $$k=\arg\max\nolimits_{k\in\{2,\ldots,p\}}\sum_{r=1}^k \sum_{A_i\in\{C_r-\eta_r\}}R(A_i:\eta_r).$$(11)We remark that the experimental results reported in [1] are based on (11) above not (11) in [1].

This correspondence presents a two-stage classification learning algorithm. The first stage approximates the class-conditional distribution of a discrete space using a separate mixture model, and the second stage investigates the class posterior probabilities by training a network. The first stage explores the generative information that is inherent in each class by using the Chow-Liu (CL) method, which approximates high-dimensional probability with a tree structure, namely, a dependence tree, whereas the second stage concentrates on discriminative learning to distinguish between classes. The resulting learning algorithm integrates the advantages of both generative learning and discriminative learning. Because it uses CL dependence-tree estimation, we call our algorithm CL-Net. Empirical tests indicate that the proposed learning algorithm makes significant improvements when compared with the related classifiers that are constructed by either generative learning or discriminative learning.

Classification is an important topic in data mining research. To better handle continuous data, fuzzy sets are used to represent interval events in the domains of continuous attributes, allowing continuous data lying on the interval boundaries to partially belong to multiple intervals. Since the membership functions of fuzzy sets can profoundly affect the performance of the models or rules discovered, the determination of membership functions or fuzzy partitioning is crucial. In this paper, we present a new method to determine the membership functions of fuzzy sets directly from data to maximize the class-attribute interdependence and, hence, improve the classification results. In other words, it forms a fuzzy partition of the input space automatically, using an information-theoretic measure to evaluate the interdependence between the class membership and an attribute as the objective function for fuzzy partitioning. To find the optimum of the measure, it employs fractional programming. To evaluate the effectiveness of the proposed method, several real-world data sets are used in our experiments. The experimental results show that this method outperforms other well-known discretization and fuzzy partitioning approaches.

Associative classification is a new classification approach integrating association mining and classification. It becomes a significant tool for knowledge discovery and data mining. However, high-order association mining is time consuming when the number of attributes becomes large. The recent development of the AdaBoost algorithm indicates that boosting simple rules could often achieve better classification results than the use of complex rules. In view of this, we apply the AdaBoost algorithm to an associative classification system for both learning time reduction and accuracy improvement. In addition to exploring many advantages of the boosted associative classification system, this paper also proposes a new weighting strategy for voting multiple classifiers.

This paper presents an attribute clustering method which is able to group genes based on their interdependence so as to mine meaningful patterns from the gene expression data. It can be used for gene grouping, selection, and classification. The partitioning of a relational table into attribute subgroups allows a small number of attributes within or across the groups to be selected for analysis. By clustering attributes, the search dimension of a data mining algorithm is reduced. The reduction of search dimension is especially important to data mining in gene expression data because such data typically consist of a huge number of genes (attributes) and a small number of gene expression profiles (tuples). Most data mining algorithms are typically developed and optimized to scale to the number of tuples instead of the number of attributes. The situation becomes even worse when the number of attributes overwhelms the number of tuples, in which case, the likelihood of reporting patterns that are actually irrelevant due to chances becomes rather high. It is for the aforementioned reasons that gene grouping and selection are important preprocessing steps for many data mining algorithms to be effective when applied to gene expression data. This paper defines the problem of attribute clustering and introduces a methodology to solving it. Our proposed method groups interdependent attributes into clusters by optimizing a criterion function derived from an information measure that reflects the interdependence between attributes. By applying our algorithm to gene expression data, meaningful clusters of genes are discovered. The grouping of genes based on attribute interdependence within group helps to capture different aspects of gene association patterns in each group. Significant genes selected from each group then contain useful information for gene expression classification and identification. To evaluate the performance of the proposed approach, we applied it to two well-known gene expression data sets and compared our results with those obtained by other methods. Our experiments show that the proposed method is able to find the meaningful clusters of genes. By selecting a subset of genes which have high multiple-interdependence with others within clusters, significant classification information can be obtained. Thus, a small pool of selected genes can be used to build classifiers with very high classification rate. From the pool, gene expressions of different categories can be identified.

This paper presents a new robust scene-recognition algorithm using points and lines in three uncalibrated color images under natural or artificial lighting without knowing the poses of the camera. Local optimization is employed by the algorithm in finding point matches to guarantee accuracy in the case when object surface is extremely uneven of having abrupt changes, thus causing a wide range of point movements between consecutive images. The algorithm is iterated to obtain maximum features until no improvement can be achieved. Experiments using a large number of images show excellent performance by this new algorithm.

Association and classification are two important tasks in data mining and knowledge discovery. Intensive studies have been carried out in both areas. But, how to apply discovered event associations to classification is still seldom found in current publications. Trying to bridge this gap, this paper extends our previous paper on significant event association discovery to classification. We propose to use weight of evidence to evaluate the evidence of a significant event association in support of, or against, a certain class membership. Traditional weight of evidence in information theory is extended here to measure the event associations of different orders with respect to a certain class. After the discovery of significant event associations inherent in a data set, it is easy and efficient to apply the weight of evidence measure for classifying an observation according to any attribute. With this approach, we achieve flexible prediction.

Decision support nowadays is more and more targeted to large scale complicated systems and domains. The success of a decision support system relies mainly on its capability of processing large amounts of data and efficiently extracting useful knowledge from the data, especially knowledge which is previously unknown to the decision makers. With a large scale system, traditional knowledge acquisition models become inefficient and/or more biased, due to the subjectivity of the experts or the pre-assumptions of certain ideas or algorithmic procedures. Today, with the rapid development of computer technologies, the capability of collecting data has been greatly advanced. Data becomes the most valuable resource for an organization. We present a fundamental framework toward intelligent decision support by analyzing a large amount of mixed-mode data (data with a mixture of continuous and categorical values) in order to bridge the subjectivity and objectivity of a decision support process. By considering significant associations of artifacts (events) inherent in the data as patterns, we define patterns as statistically significant associations among feature values represented by joint events or hypercells in the feature space. We then present an algorithm which automatically discovers statistically significant hypercells (patterns) based on: 1) a residual analysis, which tests the significance of the deviation when the occurrence of a hypercell differs from its expectation, and 2) an optimization formulation to enable recursive discovery. By discovering patterns from data sets based on such an objective measure, the nature of the problem domain will be revealed. The patterns can then be applied to solve specific problems as being interpreted or inferred with.

Structured light systems (SLS) have been used in 3D model building for a long time. However, the comprehensive performance of such systems, in terms of data acquisition speed and depth density, is still far from being perfect. In this paper, we introduce a new pattern design for SLS in order to get a dense depth map while in principle maintaining the acquisition speed, high reliability and accuracy. Our system uses a hierarchical integration of features and textures in the projection pattern. This hierarchy is then used to guide the matching process. The effectiveness of the method has been demonstrated by extensive experiments.

A new robust scene-reconstruction algorithm using points and lines in three uncalibrated color images is introduced. The algorithm is robust because it discards outliers at the same time as it estimates the geometric constraints. The algorithm consists of three components: a point-tracking algorithm for color images; a line-matching algorithm for color images and a robust algorithm for computing the trifocal tensor (also called the trilinear tensor). These three components are carried out iteratively within the scene-reconstruction algorithm until no significant improvement can be achieved. Cameras are assumed uncalibrated and camera poses are assumed unknown.

We develop a new technique for 3D object modeling by integrating the 2D vision methodology with a laser based high precision measurement technology. After calibrating the spatial relationship between the CCD camera and the range laser, the system captures an image of the inspected object, extracts 2D image features such as edges, curves and corners, and provides intelligent guidance for the range laser sensor to obtain 3D measurements on these features. The available range data are analysed and synthesized to construct a CAD model of the object.

The objective of the paper is to establish a mathematical framework for the variational approach for collision free trajectory planning of a robot manipulator, examine it from an engineering perspective and demonstrate the importance of the dynamic characteristics. The framework is based on the energetic concept of an instantaneous energy balance of a dynamic system. Within the framework, different energy forms are defined for obstacle, environmental constraints and task requirements according to their functional characteristics. By applying Hamilton's principle, the general differential control equations of the system are derived. The simulated results demonstrate the elegance and robustness of the current variational approach.

In this paper, a novel method of pattern discovery is proposed. It is based on the theoretical formulation of a contingency table of events. Using residual analysis and recursive partitioning, statistically significant events are identified in a data set. These events constitute the important information contained in the data set and are easily interpretable as simple rules, contour plots, or parallel axes plots. In addition, an informative probabilistic description of the data is automatically furnished by the discovery process. Following a theoretical formulation, experiments with real and simulated data will demonstrate the ability to discover subtle patterns amid noise, the invariance to changes of scale, cluster detection, and discovery of multidimensional patterns. It is shown that the pattern discovery method offers the advantages of easy interpretation, rapid training, and tolerance to noncentralized noise.

A challenge in 3D computer vision is to automatically acquire 3D models of objects through a CCD camera and to use the acquired models to recognize objects and estimate their poses. The PAMI System works on images acquired from a single CCD camera. It first detects salient features from an image and then groups them according to their types as well as their spatial, geometrical and topological relations. The feature grouping types include: a) four corner points and triplets of lines forming corners; b) curve segments fitted into ellipses. The use of matching hypotheses generated based on feature groupings is usually more robust and effective than the combinatorial matching of point features.

This paper presents the automated model synthesis component of an integrated passive 3D vision system. The synthesized models can be used by the object recognition and pose determination components. The model synthesis obtains the 3D object model from images acquired by a CCD camera posed at various known positions. This paper presents developments and discusses automatic model synthesis. The tasks include robust 2D feature detection; 2D feature post-processing for eliminating noise and recovering missing features; 2D feature grouping of structurally related 2D features; stereo triangulation with a new form of epipolar line constraint; projective inversion of ellipses; synthesis for circular shape in 3D space from its projective views based on the ellipse pose hypothesis; and incremental model synthesis of model from multiple views based on the vertex triangulation. To demonstrate full automation, we use a single CCD camera mounted on the last link of a robot arm. The integrated robot system is able to move the CCD camera around the object and capture images at various vantage points and furnish the camera pose corresponding to each image acquired. The intelligent system then synthesizes the extracted features from each image to obtain a 3D model of the object. Such an approach, though more difficult than the direct use of range data through range sensors, is of great importance for space and industrial automation where cost and flexibility are of concern.

This article introduces a representation known as Bayesian attributed hypergraphs (BAHGs) that are based on the integration of Bayesian networks and attributed hypergraphs. BAHGs are an augmentation to attributed hypergraphs that allow for the management of uncertainty, using Bayesian theory, and can reason about formations from the sensory data using simple graph operators. They allow for the creation of multiple instantiations of Bayesian networks while maintaining single instantiation of nodes that represent the same event. This unification of uncertainty management and attributed hypergraphs removes the need of maintaining and synchronizing between a representation for managing uncertainty and another to manage declarative knowledge. A formalism for the construction of a BAHG for image understanding is presented based on the decomposition by parts methodology and the use of geometric constraints among feature sets. An example is presented that performs perceptual grouping among fragmented 3-D surfaces in an attempt to group the surfaces into corners and continuous surfaces.

The currently used techniques for multiple sequence alignment are characterized by great computational complexity, which prevents the techniques from wider use. The research reported in the paper is aimed at developing a new technique for efficient multiple sequence alignment. The new technique consists of a genetic algorithm and a sequence synthesis method. The genetic algorithm identifies matches and the sequence synthesis method handles mismatches. Genetic algorithms are stochastic approaches for efficient and robust search. By converting biomolecular sequence alignment into a problem of searching for near-optimal points in a "pre-alignment space", a genetic algorithm can be used to find good alignments very efficiently. Experiments on real data sets have shown that the average computing time of this technique may be two or three orders lower than an technique based on pairwise dynamic programming, while the alignment qualities are very similar.

The visual appearance of an object in space is an image configuration projected from a subset of connected faces of the object. It is believed that face perception and face integration play a key role in object recognition in human vision. This paper presents a novel approach for calculating viewpoint consistency for three-dimensional (3D) object recognition, which utilizes the perceptual models of face grouping and face integration. In the approach, faces are used as perceptual entities in accordance with the visual perception of shape constancy and face-pose consistency. To accommodate the perceptual knowledge of face visibility of objects, a synthetic view space (SVS) is developed. SVS is an abstractive perceptual space which partitions and synthesizes the conventional metric view sphere into a synthetic view box in which only a very limited set of synthetic views (s-views) need to be considered in estimating face-pose consistency. The s-views are structurally organized in a network, the view-connectivity net (VCN), which describes all the possible connections and constraints of the s-views in SVS. VCN provides a meaningful mechanism in pruning the search space of SVS during estimating face-pose consistency. The method has been successfully used for recognizing a class of industrial parts.

MOTIVATION: Multiple molecular sequence alignment is among the most important and most challenging tasks in computational biology. The currently used alignment techniques are characterized by great computational complexity, which prevents their wider use. This research is aimed at developing a new technique for efficient multiple sequence alignment. APPROACH: The new method is based on genetic algorithms. Genetic algorithms are stochastic approaches for efficient and robust searching. By converting biomolecular sequence alignment into a problem of searching for optimal or near-optimal points in an 'alignment space', a genetic algorithm can be used to find good alignments very efficiently. RESULTS: Experiments on real data sets have shown that the average computing time of this technique may be two or three orders lower than that of a technique based on pairwise dynamic programming, while the alignment qualities are very similar. AVAILABILITY: A C program on UNIX has been written to implement the technique. It is available on request from the authors.

To uncover qualitative and quantitative patterns in a data set is a challenging task for research in the area of machine learning and data analysis. Due to the complexity of real-world data, high-order (polythetic) patterns or event associations, in addition to first-order class-dependent relationships, have to be acquired. Once the patterns of different orders are found, they should be represented in a form appropriate for further analysis and interpretation. The authors propose a novel method to discover qualitative and quantitative patterns (or event associations) inherent in a data set. It uses the adjusted residual analysis in statistics to test the significance of the occurrence of a pattern candidate against its expectation. To avoid exhaustive search of all possible combinations of primary events, techniques of eliminating the impossible pattern candidates are developed. The detected patterns of different orders are then represented in an attributed hypergraph which is lucid for pattern interpretation and analysis. Test results on artificial and real-world data are discussed toward the end of the paper.

Multiple biomolecular sequence alignment is among the most important and challenging tasks in computational biology. It is characterized by great complexity in processing time. In this paper, a multiple-sequence alignment system is reported which combines the techniques of genetic algorithms and pairwise dynamic programming. Genetic algorithms are stochastic approaches for efficient and robust search. By converting biomolecular sequence alignment into a problem of searching for an optimal or a near-optimal point in a solution space, a genetic algorithm is used to find match blocks very efficiently. A pairwise dynamic programming is then applied to the subsequences between the match blocks. Combining the strengths of the two methods, the system achieves high efficiency and high alignment quality. In this paper, the system is described in detail. The system's performance is analyzed and the experimental results are presented.

The recovery of 2D information from intensity images, and that of 3D information from range images are the major issues in 3D objects recognition from sensory data. The analysis and interpretation of remote sensing aerial images have important applications. This paper presents an efficient method for the analysis and modeling of such scenes based on range sensory data. Unlike methods using 2D intensity images, we exploit the rich 3D data. We extract symbolic information from the 3D triangular mesh models. These are used to recognize buildings using symbolic reasoning and generic object models.

Rapidly changing requirements in manufacturing and robotics require efficient automated planning systems. In this paper, we present a method to acquire and exploit domain-knowledge. We use two examples of knowledge-extensive contexts; outdoor terrain robot navigation and mission planning. We represent the acquired sensory 3D data by triangular terrain meshes. Application independent features are automatically extracted from these and converted into symbolic entities suitable for reasoning. Their topological relations are then organized into attributed graphs. Higher-order, application dependent relations are captured by hyper-edges in attributed hypergraphs. The symbolic relations inducing hyperedges are used as the basis of symbolic reasoning operations. The resulting compact hypergraph representation of the raw data facilitates complex navigation and mission planning tasks. Domain-knowledge is thus captured in a flexible form and used to reduce the search for feasible paths.

The recovery of 2D information from intensity images, and that of 3D information from range images are the major issues in 3D objects recognition from sensory data. The analysis and interpretation of remote sensing aerial images have important applications. This paper presents an efficient method for the analysis and modeling of such scenes based on range sensory data. Unlike methods using 2D intensity images, we exploit the rich 3D data. We extract symbolic information from the 3D triangular mesh models. These are used to recognize buildings using symbolic reasoning and generic object models.

This article presents a vision based online system for the robust trajectory planning of robot manipulators. It uses a 3D vision system to determine the relative position of the objects to be engaged and the obstacle to avoid, and a novel obstacle avoidance procedure for manipulator motion planning. From intensity images acquired by a CCD camera mounted on the robot arm, the salient features are first accurately and robustly detected and then grouped. Through the correspondences between the feature groupings and the model features, the 3D poses of the objects and the obstacles are determined and confirmed by back-projection. Once these poses are determined, an online procedure, based on redundancy resolution, is used to achieve obstacle avoidance. The approach utilizes a null space vector to set properly the robot configuration, and a potential field method to guide the end-effector. By pseudoinverse perturbation it also prevents singular configurations and local minima. The feasibility and effectiveness of the system is demonstrated by an experiment with online engagement and transportation of objects posed inside an aluminium frame.

Inductive learning systems can be effectively used to acquire classification knowledge from examples. Many existing symbolic learning algorithms can be applied in domains with continuous attributes when integrated with a discretization algorithm to transform the continuous attributes into ordered discrete ones. In this paper, a new information theoretic discretization method optimized for supervised learning is proposed and described. This approach seeks to maximize the mutual dependence as measured by the interdependence redundancy between the discrete intervals and the class labels, and can automatically determine the most preferred number of intervals for an inductive learning application. The method has been tested in a number of inductive learning examples to show that the class-dependent discretizer can significantly improve the classification performance of many existing learning algorithms in domains containing numeric attributes.>

In this article a fast and simple method for the motion planning of telerobotic manipulators is presented. It is based on solving numerically a linear system of equations that includes a simple null space vector for obstacle avoidance, and an efficient procedure for the appropriate damping of the pseudoinverse matrix. This approach enables the pursuance simultaneously, of both collision avoidance and singularities prevention on-line in a sensor based environment. These properties also make it suitable for entirely autonomous operations.>

Suppose we are given a sequence of events that are generated probabilistically in the sense that the attributes of one event are dependent, to a certain extent, on those observed before it. This paper presents an inductive method that is capable of detecting the inherent patterns in such a sequence and to make predictions about the attributes of future events. Unlike previous AI-based prediction methods, the proposed method is particularly effective in discovering knowledge in ordered event sequences even if noisy data are being dealt with. The method can be divided into three phases: (i) detection of underlying patterns in an ordered event sequence; (ii) construction of sequence-generation rules based on the detected patterns; and (iii) use of these rules to predict the attributes of future events. The method has been implemented in a program called OBSERVER-II, which has been tested with both simulated and real-life data. Experimental results indicate that it Is capable of discovering underlying patterns and explaining the behaviour of certain sequence-generation processes that are not obvious or easily understood. The performance of OBSERVER-II has been compared with that of existing AI-based prediction systems, and it is found to be able to successfully solve prediction problems programs such as SPARC have failed on.>

An inductive knowledge acquisition method based on the probabilistic inference technique is presented. The proposed system can be applied to generate decision rules automatically for certain medical expert systems. Given a patient database containing historical diagnosis and prognosis information, the method is capable of detecting the inherent probabilistic patterns in the data. Classification knowledge can be synthesized in the form of explicit production rules with associated probabilistic weight of evidence based on the patterns detected. With these rules, new patient cases can be quickly and accurately classified. Using real-world medical data, it is shown that the proposed method performs better in terms of classification accuracy and computational efficiency than some of the major existing methods.>

The authors present a kinematic measure of global performance for the design evaluation and optimization of robot (redundant) manipulators. The proposed criterion has been applied to optimize each of several different designs of a HERA arm as a redundant manipulator. The results obtained have shown the ability of the proposed approach to establish quantitative kinematic distinctions among a set of designs.>

In this article a fast approach for the ob- stacle avoidance of robot manipulators is presented. The approach is based on formulating an inverse kinematics problem under an inexact context. This procedure per- mits to deal with the avoidance of obstacles with an ap propriate and easy to compute null space vector; whereas the avoidance of singularities is attained by the proper pseudoinverse perturbation. Here the computation of the inverse kinematics problem is accomplished by solving nu- merically a linear system, which includes the vector for obstacle avoidance and a scheme for the proper pseudoin- verse perturbation. These properties make the proposed approach suitable for robots operating in a sensor based environment. The developed algorithm is tested on the simulation of a planar redundant manipulator. From the results obtained it is observed that the proposed approach compares favorably with the other approaches that have recently proposed.

In this article the inverse kinematics problem for robot manipulators is considered under an inexact context; and a fast procedure for its solution and pseudoinverse robustness is presented. The approach is based on solving the linear system based on the symmetric matrix JJT+pl (where, J and I are the Jacobian and the identity matrix respectively, and p is a damping factor) by a Gaussian elimination process that takes into account the matrix symmetry, and automatically evaluating some simple parameters. These parameters are used in either one of two original schemes, which are theoretically justifiable, that are also proposed for the appropiate evaluation of the damping factor. In the first scheme an upper bound for the condition number of the matrix JJT+pl, in terms of some of the calculated parameters is used. Alternatively, in the second scheme the sufficiency condition for the rank preservation of the Jacobian developed in [5] is considered. First, an upper bound for the pseudoinverse matrix p, in terms of some of the evaluated parameters is found. Then, it is easily shown that the sufficiency condition for rank preservation can be established in terms of this bound and on the 00 norm of the Jacobian rate of change matrix. Furthermore, and as important, here it is also shown how to properly implement these schemes, in particular the one based on an upper bound for the pseudoinverse, in conjuction with a recently developed approach [4] for the singularities prevention of redundant manipulators. The developed algorithms are tested on the simulation of a planar redundant manipulator. From the results obtained it is observed that the proposed approach (in terms of efficiency, robustness and ability to prevent large joint speeds) compares favorably with the approaches using a Gaussian elimination procedure and with pseudoinverse robustness based on a manipulability measure. 2. The inverse Linematics problem.

A fast procedure for the computation of manipulator inverse kinematics and pseudoinverse robustness is presented. The approach is based on solving a linear algebraic system and evaluating the norm of the Jacobian matrix. This value is properly used in an original scheme that is also proposed for the appropriate robustness of the pseudoinverse matrix. The developed algorithm is tested on the simulation of a planar redundant manipulator and of an industrial robot arm. From the results obtained it is observed that the proposed approach compares favorably with the approaches using a Gaussian elimination procedure and with pseudoinverse robustness based on a manipulability measure.>

A string or sequence is a linear array of symbols that come from an alphabet. Due to unknown substitutions, insertions, and deletions of symbols, a sequence cannot be treated like a vector or a tuple of a fixed number of variables. The synthesis of an ensemble of sequences is a sequence of random elements that specify the probabilities of occurrence of the different symbols at the corresponding sites of the sequences. The synthesis is determined by a hierarchical sequence synthesis procedure (HSSP), which returns not only the taxonomic hierarchy of the whole ensemble of sequences but also the alignment and the synthesis of a group (a subset of the ensemble) of the sequences at each level of the hierarchy. The HSSP does not require the ensemble of sequences to be presented in the form of a tabulated array of data, the hierarchical information of the data, or the assumption of a stochastic process. The authors present the concept of sequence synthesis and the applicability of the HSSP as a supervised classification procedure as well as an unsupervised classification procedure.>

A general approach to analyzing multivariate time-dependent system processes with discrete-valued (both nominal and ordinal) and/or continuous-valued outcomes is presented. The approach is based on an event-covering method which selects (or covers) a subspace from the outcome space of an n-tuple of variables for estimation purposes. From the covered subspace, statistically interdependent events are selected as statistical knowledge for forecasting unknown events. The event-covering method presented is based on the use of restricted variables with only a subset of the outcomes considered. An extension to the event-covering method based on the selection of joint outcomes is discussed. The testing of this method using climatic data and simulated data which model situations in real life is described. The experiments show that the method is able to detect statistically relevant information, describe it in a meaningful and comprehensible way, and use this information for a reliable estimation (or forecast) of the missing values that will occur at some future time.>

A dexterity measure is presented which can be used for the design evaluation of robot (redundant) manipulators. The proposed criterion is applied (in an absolute fashion) to the evaluation of the kinematic dexterity of five different designs of a HERA redundant manipulator to be used in space operations. The selection of these designs is based on augmenting the original HERA six-degree-of-freedom design with an extra joint and considering only the resultant manipulators to be capable of avoiding all possible kinds of internal singularity. The results are in agreement with the conclusions from previous subjective studies conducted for the design analysis of an industrial arm as a redundant manipulator.>

A singularity-prevention approach is presented for redundant robot manipulators. The approach is based on establishing a local sufficiency condition that guarantees the rank preservation of the Jacobian matrix. This condition has been used directly as the constraint in the optimization problem which is formulated to obtain the optimal path of the robot manipulator. From the formulation a closed-form solution is derived and tested in the simulation of a planar redundant manipulator. The results obtained show that the approach compares favorably with methods formulated at the resolved-motion level.>

Many existing inductive learning systems have been developed under the assumption that the learning tasks are performed in a noise‐free environment. To cope with most real‐world problems, it is important that a learning system be equipped with the capability to handle uncertainty. In this paper, we first identify the various sources of uncertainty that may be encountered in a noisy problem domain. Next, we present a method for the efficient acquisition of classification rules from training instances which may contain inconsistent, incorrect, or missing information. This algorithm consists of three phases: (i) the detection of inherent patterns in a set of noisy training data; (ii) the construction of classification rules based on these patterns; and (iii) the use of these rules to predict the class membership of an object. The method has been implemented in a system known as APACS (automatic pattern analysis and classification system). This system has been tested using both real‐life and simulated data, and its performance is found to be superior to many existing systems in terms of efficiency and classification accuracy. Being able to handle uncertainty in the learning process, the proposed algorithm can be employed for applications in real‐world problem domains involving noisy data.

This paper presents a description of the application of an attributed graph based approach to the synthesis of a geometric world model for use in navigation by a mobile robot. Our aim is to develop the theoretical aspects of graph synthesis for mobile robot world knowledge acquisition, and to demonstrate the validity of the approach with a simulation before implementation on the rover. A boundary representation of free space consisting of directed line segments organized into a directed attributed graph is used. The synthesis problem can be considered as having two parts: matching of a local model with a global model and the construction of a new global model. Structural and geometric local and global constraints are used to limit and direct the search for valid graph mappings. The constraints are the source of rules for matching primitives and graphs and are used in the process of constructing a new world model graph. An algorithm for graph synthesis is implemented in a software simulation for testing and experimentation.

This paper proposes a search-effective strategy for multi-class texture classification. The textures are classified according to the nearest neighbor rule based on our recently developed texture metric. We will show that it is possible to significantly reduce the amount of computation from an exhaustive search scheme. For this purpose, a distance-preserving vector space representation of the texture database is constructed. The representation facilitates the selection of a subset of class prototypes which constitute the reduced search space. In addition, the prototypes are organized into a hierarchy to further economize the search for the nearest class. This methodology is demonstrated by experiments on 720 texture samples belonging to eight classes. On average, a reduction of close to 70% is achieved.

This paper outlines a new approach to the synthesis of information from data. Information is defined as a detected organization of data after a process of discretization (or partitioning) and event covering. The discretization is based on a hierarchical maximum entropy scheme which iteratively minimizes the loss of information according to Shannon. The event-covering process is based on an evaluation of the deviation of the observed frequencies of an event from the expectation due to prior knowledge (defined by the null hypothesis and/or domain knowledge). The hierarchical maximum entropy discretization scheme provides a rigorous and efficient way in solving the non-uniform scaling problem in multivariate data analysis. Because our method refines the boundaries dynamically depending on the detection of information, it directs the analysis on the outcome subspace with high information content. In addition, it naturally produces a hierarchical view of information so that data can be analyzed/synthesized with respect to an outcome context. The method has been tested using simulated and real life data with very good result.

An algorithm for finding the optimal monomorphism between two attributed graphs is proposed. The problem is formulated as a tree search problem. To guide the search the branch-and-bound heuristic approach is adopted, using an efficient consistent lower bounded estimate for the evaluation function of the cost associated with the optimal solution path in the search tree. The algorithm is a generalization of an algorithm for graph optimal isomorphism. The algorithm's potential for engineering application is demonstrated by a simple structural pattern recognition problem and a plant allocation and distribution problem.>

A singularities avoidance approach suitable for the optimal path planning of redundant robot manipulators is presented. The approach is based on establishing proper bounds for the rate of change of the Jacobian matrix of the transformation between the joint speeds and the end effector Cartesian speed. These bounds become an additional constraint for an optimization problem that is formulated to obtain the optimal path of the robot manipulator. Here, the optimization problem is formulated globally as a state-constrained continuous optimal control problem which can consider joint (speeds) constraints and/or manipulator dynamics, and be solved by an efficient iterative numerical technique. This approach is particularly exemplified for the optimal path generation of a simulated planar redundant manipulator, and its results are compared with the results yielded by a local approach. The results obtained (although not adequate for present real-time implementation) confirm the superiority of the global approach.>

A computer vision system is presented for shape synthesis and recognition of three-dimensional objects using an attributed hypergraph representation. The vision system is capable of: (1) constructing an attributed hypergraph representation (AHR) based on the information extracted from an image with range data; (2) synthesizing several AHRs obtained from various views of an object to form a complete AHR of the object; and (3) recognizing any view of an object of finding the graph monomorphism between the AHR of that view and the complete AHR of a prototype object. This system is implemented on a Grinnell imaging system driven by a VAX 11/750 running VMS.>

A description is given of a gray-level threshold selection method for image segmentation that is based on the maximum entropy principle. The optimal threshold value is determined by maximizing the a posteriori entropy subject to certain inequality constraints which are derived by means of spectral measures characterizing uniformity and the shape of the regions in the image. For this purpose, the authors use both the gray-level distribution and the spatial information of an image. The effectiveness of the method is demonstrated by its performance on some real-world images. An extension of this method to chromatic images is provided.>

A method is proposed for probabilistic interference through empirical observations involving categorical data. This method can detect statistically independent patterns inherent in a set of observed events. The evidence provided by the patterns for or against some hypotheses generated during the inference process are then quantitatively estimated and combined to find the most plausible hypotheses. The proposed method has been implemented for the Probabilistic Inference System (PIS). Because it can detect patterns in observed or inferred events which may not be directly observable, the PIS can be used to aid decision-making in the presence of uncertainty. It has been tested with simulated as well as real-life data, and the results are very satisfactory.>

A vision system based on the attributed hypergraph representation (AHR) and monomorphism is presented. The graph representation consists of the structural descriptions of the objects in a scene and their interrelations. It renders all structural information explicit and symbolic. A hypergraph monomorphism algorithm is then used to compare the AHR of objects in the scene with a set of complete AHRs of prototypes. It enables objects which may be partially occluded by each other to be distinguished.>

A singularities-avoidance approach suitable for the optimal local path generation of redundant robot manipulators is presented. It is based on establishing proper bounds for the rate of change of the Jacobian matrix representing the transformation between the joints speeds and the end-effector Cartesian speed. These bounds become an additional constraint for an optimization problem which is formulated locally to obtain the optimal path of the considered robot manipulator. The problem is considered as a minimization of energy with given robot kinematics (and dynamics) and subject to the robot requirements and singularities-avoidance constraint. From this formulation, a closed-form solution is derived which allows online interaction with sensors.>

In this paper, a singularities avoidance method suitable for the trajectory planning of redundant and nonredundant robot manipulators is presented. This method is based on establishing proper bounds for the rate of change of the Jacobian matrix of the transformation between the joints speed and end effector Cartesian speed These bounds are computationally inexpensive and easy to deal with by their conversion into additional constraints for any optimization problem which may be formulated to obtain the local or global optimal control of the robot manipulator. Here, this approach is exemplified for the trajectory planning problem of a particular type of redundant and nonredundant robot manipulators studied under an optimal control problem formulation. For each case, this problem is treated as a minimum energy problem with given kinematics and dynamics and subject to the robot requirements, tasks, and the additional singularities avoidance constraints; resulting in a state constrained continuous optimal control which is solved numerically.

In this paper, we present a method capable of identifying and locating objects with known three-dimensional models in a single perspective image. The identity and location of an object are obtained through a procedure which we refer to as a knowledge-directed search. The search encodes declarative and procedural knowledge in a rule network designed to ensure that only pertinent information is processed. The search is organized as a collection of search activations. Each search activation has a context memory for recording previously inferred or assumed information. As a result, multiple search activations may be used to test various hypotheses of object identity and location.

This paper presents a method of structuring the free space of a roving robot's environment into a set of overlapping convex regions ideally suited to path planning and navigation tasks. The structure of the free space environment is maintained as a hypergraph with each convex region represented by a hyperedge identifying the boundary walls of the region. A new methodology reveals the structure of free space and constructs the hypergraph representation through a directed search for a set of fundamental circits in an abstract graphical representation of the environment geometry.

The difficulties in analyzing and clustering (synthesizing) multivariate data of the mixed type (discrete and continuous) are largely due to: 1) nonuniform scaling in different coordinates, 2) the lack of order in nominal data, and 3) the lack of a suitable similarity measure. This paper presents a new approach which bypasses these difficulties and can acquire statistical knowledge from incomplete mixed-mode data. The proposed method adopts an event-covering approach which covers a subset of statistically relevant outcomes in the outcome space of variable-pairs. And once the covered event patterns are acquired, subsequent analysis tasks such as probabilistic inference, cluster analysis, and detection of event patterns for each cluster based on the incomplete probability scheme can be performed. There are four phases in our method: 1) the discretization of the continuous components based on a maximum entropy criterion so that the data can be treated as n-tuples of discrete-valued features; 2) the estimation of the missing values using our newly developed inference procedure; 3) the initial formation of clusters by analyzing the nearest-neighbor distance on subsets of selected samples; and 4) the reclassification of the n-tuples into more reliable clusters based on the detected interdependence relationships. For performance evaluation, experiments have been conducted using both simulated and real life data.

The maximum entropy method has been successfully applied to a number of scientific and engineering disciplines. A special case of its particular usefulness is the discretization of two-dimensional distribution subject to the maximization of Shannon's entropy. Such a discretization scheme provides a means for deriving a Iow-order approximation of probability distribution for mixed-mode (continuous and discrete) multivariate data. The presence of special cases is shown where the maximum-entropy discretization of two-dimensional probability distribution is not unique.

A new algorithm is presented for detecting graph monomorphisms for a pair of graphs. This algorithm entails a tree search based on the projections of the product graph called the net of the two graphs. It uses the minimum number of neighbors of the projected graphs to detect infeasible subtrees. The algorithm, in comparison with that of Deo and coworkers, is more efficient in its storage space utilization and average execution time. It does not suffer from the ambiguity which arises in Deo et al.'s work when cyclic graphs are matched. Applications to attributed graph monomorphisms are included.

An event-covering method [1] for synthesizing knowledge gathered from empirical observations is presented. Based on the detection of statistically significant events, knowledge is synthesized through the use of a special clustering algorithm. This algorithm, employing a probabilistic information measure and a subsidiary distance, is capable of clustering ordered and unordered discrete-valued data that are subject to noise perturbation. It consists of two phases: cluster initiation and cluster refinement. During cluster initiation, an analysis of the nearest-neighbor distance distribution is performed to select a criterion for merging samples into clusters. During cluster refinement, the samples are regrouped using the event-covering method, which selects subsets of statistically relevant events. For performance evaluation, we tested the algorithm using both simulated data and a set of radiological data collected from normal subjects and spina bifida patients.

The notion of a random graph is formally defined. It deals with both the probabilistic and the structural aspects of relational data. By interpreting an ensemble of attributed graphs as the outcomes of a random graph, we can use its lower order distribution to characterize the ensemble. To reflect the variability of a random graph, Shannon's entropy measure is used. To synthesize an ensemble of attributed graphs into the distribution of a random graph (or a set of distributions), we propose a distance measure between random graphs based on the minimum change of entropy before and after their merging. When the ensemble contains more than one class of pattern graphs, the synthesis process yields distributions corresponding to various classes. This process corresponds to unsupervised learning in pattern classification. Using the maximum likelihood rule and the probability computed for the pattern graph, based on its matching with the random graph distributions of different classes, we can classify the pattern graph to a class.

A formal definition of random graphs is introduced which is applicable to graphical pattern recognition problems. The definition is used to formulate rigorously the structural-contextual dichotomy of random graphs. The probability of outcome graphs is expressed as the product of two terms, one due to the statistical variability of structure among the outcome graphs and the other due to their contextual variability. Expressions are obtained to estimate the various probability, typicality, and entropy measures. The members in an ensemble of signed digraphs are interpreted as outcome graphs of a random graph. The synthesized random graph is used to quantify the structural, contextual, and overall typicality of the outcome graphs with respect to the random graph.

The characterization of graph morphisms in terms of the subgraphs of the Cartesian graph product is extended and used to develop algorithms for an optimal graph monomorphism problem. The objective functional considered is defined as the sum of the weights associated with vertex and arc mappings. A reduction algorithm is proposed to obtain sharp lower bounds on the value of the solution. The lower bounds are used in a branch-and-bound algorithm for the optimal graph monomorphism problem.

Multivariate data sets with dependency between observations are described using a feature space representation. The resulting ordered set of points in feature space is termed the pattern trajectory. A set of descriptors of the pattern trajectory has been developed. Time-dependent clusters and transition segments form the basic structural description from which both lower level properties, e.g., cluster position, cluster dispersion, transition rate, and higher level properties, e.g., rebound, periodicity, finite state model, may be derived. Two algorithms have been developed for time-dependent cluster analysis. The time-weighted minimum spanning tree (TWMST) algorithm utilizes a composite space-time distance measure and creates clusters by cutting the longest tree branches. The time-dependent Isodata (TD-ISODATA) algorithm utilizes a global clustering to initiate the segmentation into timedependent cluster cores and transition segments. Examples of the applica tion of these algorithms to nonstationary neuronal spike train data and to simulated animal migration data are described. The pattern trajectory approach appears to offer advantages in the analysis of complex nonstationary data sets where conventional time series techniques are insufficient. Time-dependent clustering provides a means to identify a composite source model.

This paper presents a method of cluster analysis based on a pseudo F-statistic (PFS) criterion function. It is designed to subdivide an ensemble into an optimal set of groups, where the number of groups is not specified and no ad hoc parameters are employed. Univariate and multivariate F-statistic and pseudo F-statistic consistency is displayed. Algorithms for feasible application of PFS are given. Results from simulations are utilized to demonstrate the capabilities of the PFS clustering method and to provide a comparative guide for other users.

This paper presents a new clustering algorithm for analyzing unordered discrete-valued data. This algorithm consists of a cluster initiation phase and a sample regrouping phase. The first phase is based on a data-directed valley detection process utilizing the optimal second-order product approximation of high-order discrete probability distribution, together with a distance measure for discrete-valued data. As for the second phase, it involves the iterative application of the Bayes' decision rule based on subgroup discrete distributions. Since probability is used as its major decision criterion, the proposed method minimizes the disadvantages of yielding solutions sensitive to the arbitrary distance measure adopted. The performance of the proposed algorithm is evaluated by applying it to four different sets of simulated data and a set of clinical data. For performance comparison, the decision-directed algorithm [11] is also applied to the same set of data. These evaluation experiments fully demonstrate the validity and the operational feasibility of the proposed algorithm and its superiority as compared to the decision-directed algorithm.

This article presents a decision-directed approach for classifying discrete data. In the clustering algorithm, probable clusters are initiated through the use of a sorting scheme based on the estimated probability distribution of the data and an arbitrary distance measure. The subsequent iterative reclassification procedures are directed by the estimated distribution of each class. The distribution estimation adopted is modified from the dependence tree procedure. The algorithm performance is then evaluated through the use of simulated and clinical data. Finally, the algorithm is applied to disease categorization and to signs and symptoms extraction for each disease class.

A picture processing scheme which quantifies pictorial information through the use of a resolution-dependent feature extraction process is introduced. The proposed quantification method (based on an information theoretical approach) can be used for edge detection, texture analysis, and classification, as well as feature extraction. These applications are possible because the information measures obtained are capable of uncovering some basic characteristics of images. Vector quantities and synthesized plots of various information measures derived from images are included here to demonstrate the usefulness of the method in image analysis.

A method of data analysis which aims at the detection of the significant periodicities as well as of the irregular high frequency oscillations (perturbations) in biological time series (TS) is proposed. The significant frequency modes are detected by application of a statistical significance criterion on the periodogram derived from the given TS; they are used to construct the significant periodic series. The latter is then subtracted from the original TS in order to obtain the detrended TS defined as the perturbation series which is considered as the outcome of a stochastic process. Under the assumption of Gaussian characteristics for the stochastic process, evidence of which is available, a probabilistic basis for both univariate and bivariate analysis is provided. A ``surprisal'' measure defined as the reciprocal of the probability for an outcome of a stochastic process (or a pair of correlated porcesses) is introduced to account for both the average as well as the localized perturbation of the TS (or the correlation between the pair of TS). A dependence tree configuration that maximizes the overall mutual information or dependence among branches is proposed as an optimal representation of a multivariate system. Lag-correlation analysis and cospectrum tests are adopted for validation and modification of the configuration generated. Simulated systems are employed to test the extent of linear approximation of various nonlinear functions as well as the sensitivity of the proposed method when the simulated system is subject to disturbances of varied type and degree.

In this paper, issues concerning feature patterns in terms of both feature composition and feature interdependence are discussed, and the concepts of typicality and diversity of an ensemble are formulated. The features of the specimens investigated are organized in a two-dimensional array, called an observation matrix, with each row vector representing the ordered set of features of a specimen. An algorithm (based upon the proposed measures and statistical screening) is implemented for extracting feature patterns. In the algorithm, schemes for feature patterns and specimen reweighting are proposed to optimize the utilization of available information in the array, and to minimize possible bias caused by the uneven sampling of the ensemble. Two sets of real world data in the environmental and molecular biology areas are used to exemplify the physical meaning of the proposed measures as well as to demonstrate the operational feasibility and significance of this methodology in analyzing homologous ensemble which is subject to variable degrees of diversity.

A theoretical planning model that consists of a composite set of modal networks for serving the population in an urban area or region is presented. By varying and controling various parameters in the model, an equilibrium of modal choices can be obtained by seeking the condition that no user can alter his path without experiencing an increase in cost. The equivalence between equilibrium conditions and a nonlinear programming problem will be established, following a fundamental theorem. Thus, under small perturbations in the composite network, either through changes in the frequency of certain trips or changes in the structure of the network, it is possible to linearize about the observed equilibrium to determine the effects of perturbations.

The regional planning of health care facilities is treated as a process of searching, integrating, screening, matching, evaluating, and selecting the type of facilities most suitable for the physical and socioeconomic environment in which the facilities are to be constructed. A rational procedure which matches various possible combinations of environmental features and performance characteristics of potential facility types is presented, and the process of determining the location and the extent of services of a facility in the region by means of sophisticated computer programming techniques is discussed in detail.

A simulation model is presented which investigates the requirements of patient care in planning new hospitals on the basis of statistical data of health care needs in a community and different administrative policies for providing services. The minimum requirements for future service demands for planning patient care in a hospital on the basis of health statistics in a community are generated by synthetic random observations according to certain probability distributions. The model permits the investigation of the influence of admission control on the manifest service demands as well as the effects of the latter on the utilization of patient care facilities over a period of time. The consequences of possible alternatives for meeting the demands may be determined through experimentation with various time-dependent demand patterns and various policy decisions in planning and management.