Soft nearest prototype classification

We propose a new method for the construction of nearest prototype classifiers which is based on a Gaussian mixture ansatz and which can be interpreted as an annealed version of learning vector quantization (LVQ). The algorithm performs a gradient descent on a cost-function minimizing the classification error on the training set. We investigate the properties of the algorithm and assess its performance for several toy data sets and for an optical letter classification task. Results show 1) that annealing in the dispersion parameter of the Gaussian kernels improves classification accuracy; 2) that classification results are better than those obtained with standard learning vector quantization (LVQ 2.1, LVQ 3) for equal numbers of prototypes; and 3) that annealing of the width parameter improved the classification capability. Additionally, the principled approach provides an explanation of a number of features of the (heuristic) LVQ methods.     

Adaptive nearest neighbor pattern classification

A variant of nearest-neighbor (NN) pattern classification and supervised learning by learning vector quantization (LVQ) is described. The decision surface mapping method (DSM) is a fast supervised learning algorithm and is a member of the LVQ family of algorithms. A relatively small number of prototypes are selected from a training set of correctly classified samples. The training set is then used to adapt these prototypes to map the decision surface separating the classes. This algorithm is compared with NN pattern classification, learning vector quantization, and a two-layer perceptron trained by error backpropagation. When the class boundaries are sharply defined (i.e., no classification error in the training set), the DSM algorithm outperforms these methods with respect to error rates, learning rates, and the number of prototypes required to describe class boundaries.     

Self-generating prototypes for pattern classification

Prototype classifiers are a type of pattern classifiers, whereby a number of prototypes are designed for each class so as they act as representatives of the patterns of the class. Prototype classifiers are considered among the simplest and best performers in classification problems. However, they need careful positioning of prototypes to capture the distribution of each class region and/or to define the class boundaries. Standard methods, such as learning vector quantization (LVQ), are sensitive to the initial choice of the number and the locations of the prototypes and the learning rate. In this article, a new prototype classification method is proposed, namely self-generating prototypes (SGP). The main advantage of this method is that both the number of prototypes and their locations are learned from the training set without much human intervention. The proposed method is compared with other prototype classifiers such as LVQ, self-generating neural tree (SGNT) and K-nearest neighbor (K-NN) as well as Gaussian mixture model (GMM) classifiers. In our experiments, SGP achieved the best performance in many measures of performance, such as training speed, and test or classification speed. Concerning number of prototypes, and test classification accuracy, it was considerably better than the other methods, but about equal on average to the GMM classifiers. We also implemented the SGP method on the well-known STATLOG benchmark, and it beat all other 21 methods (prototype methods and non-prototype methods) in classification accuracy.     

On Near Optimal Lattice Quantization of Multi‐Dimensional Data Points

One of the most elementary application of a lattice is the quantization of real‐valued s‐dimensional vectors into finite bit precision to make them representable by a digital computer. Most often, the simple s‐dimensional regular grid is used for this task where each component of the vector is quantized individually. However, it is known that other lattices perform better regarding the average quantization error. A rank‐1 lattices is a special type of lattice, where the lattice points can be described by a single s‐dimensional generator vector. Further, the number of points inside the unit cube [0, 1)^s is arbitrary and can be directly enumerated by a single one‐dimensional integer value. By choosing a suitable generator vector the minimum distance between the lattice points can be maximized which, as we show, leads to a nearly optimal mean quantization error. We present methods for finding parameters for s‐dimensional maximized minimum distance rank‐1 lattices and further show their practical use in computer graphics applications.     

Collective recall via the brain-state-in-a-box network

A number of approaches to pattern recognition employ variants of nearest neighbor recall. This procedure uses a number of prototypes of known class and identifies an unknown pattern vector according to the prototype it is nearest to. A recall criterion of this type that depends on the relation of the unknown to a single prototype is a non-smooth function and leads to a decision boundary that is a jagged, piecewise linear hypersurface. Collective recall, a pattern recognition method based on a smooth nearness measure of the unknown to all the prototypes, is developed. The prototypes are represented as cells in a brain-state-in-a-box (BSB) network. Cells that represent the same pattern class are linked by positive weights and cells representing different pattern classes are linked by negative weights. Computer simulations of collective recall used in conjunction with learning vector quantization (LVQ) show significant improvement in performance relative to nearest neighbor recall for pattern classes defined by nonspherically symmetric Gaussians.     

Crowd sculpting: A space‐time sculpting method for populating virtual environments

We introduce “Crowd Sculpting”: a method to interactively design populated environments by using intuitive deformation gestures to drive both the spatial coverage and the temporal sequencing of a crowd motion. Our approach assembles large environments from sets of spatial elements which contain inter‐connectible, periodic crowd animations. Such a “Crowd Patches” approach allows us to avoid expensive and difficult‐to‐control simulations. It also overcomes the limitations of motion editing, that would result into animations delimited in space and time. Our novel methods allows the user to control the crowd patches layout in ways inspired by elastic shape sculpting: the user creates and tunes the desired populated environment through stretching, bending, cutting and merging gestures, applied either in space or time. Our examples demonstrate that our method allows the space‐time editing of very large populations and results into endless animation, while offering real‐time, intuitive control and maintaining animation quality.     

Enhancing prototype reduction schemes with LVQ3-type algorithms

Various prototype reduction schemes have been reported in the literature. Foremost among these are the prototypes for nearest neighbor (PNN), the vector quantization (VQ), and the support vector machines (SVM) methods. In this paper, we shall show that these schemes can be enhanced by the introduction of a post-processing phase that is related, but not identical to, the LVQ3 process. Although the post-processing with LVQ3 has been reported for the SOM and the basic VQ methods, in this paper, we shall show that an analogous philosophy can be used in conjunction with the SVM and PNN rules. Our essential modification to LVQ3 first entails a partitioning of the respective training sets into two sets called the Placement set and the Optimizing set, which are instrumental in determining the LVQ3 parameters. Such a partitioning is novel to the literature. Our experimental results demonstrate that the proposed enhancement yields the best reported prototype condensation scheme to-date for both artificial data sets, and for samples involving real-life data sets.     

User demographics prediction based on mobile data

Demographics prediction is an important component of user profile modeling. The accurate prediction of users’ demographics can help promote many applications, ranging from web search, personalization to behavior targeting. In this paper, we focus on how to predict users’ demographics, including “gender”, “job type”, “marital status”, “age” and “number of family members”, based on mobile data, such as users’ usage logs, physical activities and environmental contexts. The core idea is to build a supervised learning framework, where each user is represented as a feature vector and users’ demographics are considered as prediction targets. The most important component is to construct features from raw data and then supervised learning models can be applied. We propose a feature construction framework, CFC (contextual feature construction), where each feature is defined as the conditional probability of one user activity under the given contexts. Consequently, besides employing standard supervised learning models, we propose a regularized multi-task learning framework to model different kinds of demographics predictions collectively. We also propose a cost-sensitive classification framework for regression tasks, in order to benefit from the existing dimension reduction methods. Finally, due to the limited training instances, we employ ensemble to avoid overfitting. The experimental results show that the framework achieves classification accuracies on “gender”, “job” and “marital status” as high as 96%, 83% and 86%, respectively, and achieves Root Mean Square Error (RMSE) on “age” and “number of family members” as low as 0.69 and 0.66 respectively, under the leave-one-out evaluation.     

NP-completeness of the problem of prototype selection in the nearest neighbor method

The problem of selecting of prototypes is to select a subset in the learning sample for which the set of minimum cardinality would provide the optimum of a given learning quality functional. In this article the problem of classification is considered in two classes, the method of classification by nearest neighbor, and three functional characteristics: the frequency of errors on the entire sample, a cross validation with one separated object, and a complete cross validation with k separated objects. It is shown that the problem of selection of prototypes in all three cases is NP-complete, which justifies the use of well-known heuristic methods for the prototype search.     

User‐Controllable Color Transfer

This paper presents an image editing framework where users use reference images to indicate desired color edits. In our approach, users specify pairs of strokes to indicate corresponding regions in both the original and the reference image that should have the same color “style”. Within each stroke pair, a nonlinear constrained parametric transfer model is used to transfer the reference colors to the original. We estimate the model parameters by matching color distributions, under constraints that ensure no visual artifacts are present in the transfer result. To perform transfer on the whole image, we employ optimization methods to propagate the model parameters defined at each stroke location to spatially‐close regions of similar appearance. This stroke‐based formulation requires minimal user effort while retaining the high degree of user control necessary to allow artistic interpretations. We demonstrate our approach by performing color transfer on a number of image pairs varying in content and style, and show that our algorithm outperforms state‐of‐the‐art color transfer methods on both user‐controllability and visual qualities of the transfer results.     

基于量化误差与分形理论的高计算效率无监督聚类研究*

已有的矢量聚类算法需学习较多的复杂数据方可获得较好的聚类效果,而对于多维的大数据性能较弱,对此,提出一种基于量化误差与分形理论的高计算效率无监督聚类算法。首先,为数据集建立量化误差的参数化模型,基于数据集的空间结构获得数据集的率失真曲线;然后,通过对率失真曲线的估算,获得数据空间的有效维度;最终,利用分形理论,通过搜索数据集的量化模型参数获得目标数据集的最优类簇数量。实验结果表明,本文的量化误差参数化模型可较好地估算数据集的有效维度,同时,本算法对数值型数据集的最优类簇估算与计算效率优于已有的矢量聚类算法。     

Fast Search Methods for Spectral Quantization

In this paper, we examine the computational requirements for the split-vector class of vector quantizers when applied to low-rate speech spectrum quantization. The split-vector quantization techniques are able to reduce the complexity and storage requirements of the 24-bit per frame spectral quantizer to manageable proportions. However, further dramatic reductions in computational complexity are possible, as will be demonstrated. As the fast-search algorithms reported in the literature are somewhat data dependent, it has been necessary to carefully evaluate several methods specifically for the speech coding problem. A total of six methods have been evaluated for their effectiveness in this task, and we show that a so-called “geometric” fast-search method results in a reduction in the average search time of an order of magnitude.     

Medical image compression using topology-preserving neural networks

A novel method based on topology-preserving neural networks is used to implement vector quantization for medical image compression. The described method is an innovative image compression procedure, which differentiates itself from known systems in several ways. It can be applied to larger image blocks and represents better probability distribution estimation methods. A transformation-based operation is applied as part of the encoder on the block-decomposed image. The quantization process is performed by a “neural-gas” network which applied to vector quantization converges quickly to low distortion errors and reaches a distortion error lower than that resulting from Kohonen's feature map or the LBG algorithm. To study the efficiency of our algorithm, we blended mathematical phantom features into clinically proved cancer free mammograms. The influence of the neural compression method on the phantom features and the mammo-graphic image is not visually perceptible up to a high compression rate.     

Evaluation of earcons for portable digital electronic products considering perceptual user characteristics

Earcons, nonverbal sound feedback, have been used for electronic products to give appropriate feedback information for the selected user functions. This study evaluated earcon usability of a portable digital electronic product based on cognition time, error rate, and subjective feelings using 20 male and female subjects. For subjective evaluation, the study assessed various earcons by subjective impression of sounds using 7‐point rating scales. For earcon usability performance, major user functions were used for the product with currently available earcons and for the product with the new earcons (suggested by this study), which considered perceptual characteristics, such as loudness and melody. Statistical results from the study indicated that the new earcons significantly reduced user error rates and therefore generally improved user performance on major functions, such as “PLAY,” “OFF,” “STOP,” “FF” (fast forward), and “REW” (rewind). Subjective data results also showed that users were more satisfied with the new, melody‐based sound feedback. Practical guidelines for sound feedback design of a small digital product are suggested. © 2011 Wiley Periodicals, Inc.     

Development of a multiprobe electrical resistivity tomography prototype system and robust underground clustering

This study reports a 24‐probe electrical resistivity tomography (ERT) prototype system and its empirical evaluation in a case study setting. The system was designed using the Wenner soil resistivity measurement method. The performance and outputs of the approach and the developed prototype system were assessed and approved by the General Directorate of Mineral Research and Exploration of Turkey. This study is also supported by the Republic of Turkey Ministry of Science, Industry and Technology through the project “Distinguishing of Metallic Targets (code number is 1064.STZ.2011‐2).” The state of the art of this study is multiprobe ERT, which has a touchscreen for ease of use and improved measurement accuracy for minimizing RMS (root mean square) error using a 16‐bit ADC. Similar to other ERT systems, the prototype system that we have developed allows the user to change the current and probe interval via the touchscreen user interface. In addition to this system, a new fuzzy clustering algorithm named robust colored image fuzzy C‐mean was developed in this study. The robust colored image fuzzy C‐mean performs underground clustering in RGB colors, which provides improved clustering results compared to those of the conventional fuzzy C‐mean clustering algorithm.     

Component‐wise Controllers for Structure‐Preserving Shape Manipulation

Recent shape editing techniques, especially for man‐made models, have gradually shifted focus from maintaining local, low‐level geometric features to preserving structural, high‐level characteristics like symmetry and parallelism. Such new editing goals typically require a pre‐processing shape analysis step to enable subsequent shape editing. Observing that most editing of shapes involves manipulating their constituent components, we introduce component‐wise controllers that are adapted to the component characteristics inferred from shape analysis. The controllers capture the natural degrees of freedom of individual components and thus provide an intuitive user interface for editing. A typical model usually results in a moderate number of controllers, allowing easy establishment of semantic relations among them by automatic shape analysis supplemented with user interaction. We propose a component‐wise propagation algorithm to automatically preserve the established inter‐relations while maintaining the defining characteristics of individual controllers and respecting the user‐specified modeling constraints. We extend these ideas to a hierarchical setup, allowing the user to adjust the tool complexity with respect to the desired modeling complexity. We demonstrate the effectiveness of our technique on a wide range of man‐made models with structural features, often containing multiple connected pieces.     

Sharing,finding and reusing end-user code for reformatting and validating data

To help users with automatically reformatting and validating spreadsheets and other datasets, prior work introduced a user-extensible data model called “topes” and a supporting visual programming language. However, no support has existed to date for users to exchange and reuse topes. This functional gap results in wasteful duplication of work as users implement topes that other people have already created.In this paper, a design for a new repository system is presented that supports sharing and finding of topes for reuse. This repository tightly integrates traditional keyword-based search with two additional search methods whose usefulness in repositories of end-user code has gone unexplored to date. The first method is “search-by-match”, where a user specifies examples of data, and the repository retrieves topes that can reformat and validate that data. The second method is collaborative filtering, which has played a vital role in repositories of non-code artifacts.The repository’s search functionality was empirically tested on a prototype repository implementation by simulating queries generated from real user spreadsheets. This experiment reveals that search-by-match and collaborative filtering greatly improve the accuracy of search over the traditional keyword-based approach, to a recall as high as 95%. These results show that search-by-match and collaborative filtering are useful approaches for helping users to publish, find, and reuse visual programs similar to topes.     

The influence of prototype fidelity and aesthetics of design in usability tests: effects on user behaviour, subjective evaluation and emotion

An empirical study examined the impact of prototype fidelity on user behaviour, subjective user evaluation and emotion. The independent factors of prototype fidelity (paper prototype, computer prototype, fully operational appliance) and aesthetics of design (high vs. moderate) were varied in a between-subjects design. The 60 participants of the experiment were asked to complete two typical tasks of mobile phone usage: sending a text message and suppressing a phone number. Both performance data and a number of subjective measures were recorded. The results suggested that task completion time may be overestimated when a computer prototype is being used. Furthermore, users appeared to compensate for deficiencies in aesthetic design by overrating the aesthetic qualities of reduced fidelity prototypes. Finally, user emotions were more positively affected by the operation of the more attractive mobile phone than by the less appealing one.