On the suitability of Prototype Selection methods for kNN classification with distributed data

In the current Information Age, data production and processing demands are ever increasing. This has motivated the appearance of large-scale distributed information. This phenomenon also applies to Pattern Recognition so that classic and common algorithms, such as the k-Nearest Neighbour, are unable to be used. To improve the efficiency of this classifier, Prototype Selection (PS) strategies can be used. Nevertheless, current PS algorithms were not designed to deal with distributed data, and their performance is therefore unknown under these conditions. This work is devoted to carrying out an experimental study on a simulated framework in which PS strategies can be compared under classical conditions as well as those expected in distributed scenarios. Our results report a general behaviour that is degraded as conditions approach to more realistic scenarios. However, our experiments also show that some methods are able to achieve a fairly similar performance to that of the non-distributed scenario. Thus, although there is a clear need for developing specific PS methodologies and algorithms for tackling these situations, those that reported a higher robustness against such conditions may be good candidates from which to start.

Surface k-NN query processing

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

Optimization of PCB component placements for the collect-and-place machines

This paper presents two hybrid genetic algorithms (HGAs) to optimize the component placement operation for the collect-and-place machines in printed circuit board (PCB) assembly. The component placement problem is to optimize (i) the assignment of components to a movable revolver head or assembly tour, (ii) the sequence of component placements on a stationary PCB in each tour, and (iii) the arrangement of component types to stationary feeders simultaneously. The objective of the problem is to minimize the total traveling time spent by the revolver head for assembling all components on the PCB. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method, the nearest neighbor heuristic, and the neighborhood frequency heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different population sizes. It is proved that the performance of HGA2 is superior to HGA1 in terms of the total assembly time.

Machine learning classification of surgical pathology reports and chunk recognition for information extraction noise reduction

Background and aims: Machine learning techniques for the text mining of cancer-related clinical documents have not been sufficiently explored. Here some techniques are presented for the pre-processing of free-text breast cancer pathology reports, with the aim of facilitating the extraction of information relevant to cancer staging.

Materials and methods: The first technique was implemented using the freely available software RapidMiner to classify the reports according to their general layout: ‘semi-structured’ and ‘unstructured’. The second technique was developed using the open source language engineering framework GATE and aimed at the prediction of chunks of the report text containing information pertaining to the cancer morphology, the tumour size, its hormone receptor status and the number of positive nodes. The classifiers were trained and tested respectively on sets of 635 and 163 manually classified or annotated reports, from the Northern Ireland Cancer Registry.

Results: The best result of 99.4% accuracy – which included only one semi-structured report predicted as unstructured – was produced by the layout classifier with the k nearest algorithm, using the binary term occurrence word vector type with stopword filter and pruning. For chunk recognition, the best results were found using the PAUM algorithm with the same parameters for all cases, except for the prediction of chunks containing cancer morphology. For semi-structured reports the performance ranged from 0.97 to 0.94 and from 0.92 to 0.83 in precision and recall, while for unstructured reports performance ranged from 0.91 to 0.64 and from 0.68 to 0.41 in precision and recall. Poor results were found when the classifier was trained on semi-structured reports but tested on unstructured.

Conclusions: These results show that it is possible and beneficial to predict the layout of reports and that the accuracy of prediction of which segments of a report may contain certain information is sensitive to the report layout and the type of information sought.

Procesos hopping a través del modelo difusional en materiales nanocristalinos usados para aplicaciones fotovoltaicas

Se presentan los modelos de hopping de rango variable (variable range hopping; VRH), vecinos cercanos (nearest neighbor hopping; NNH) y barreras de potencial presentes en las fronteras de grano; como mecanismos de transporte eléctrico predominantes en los materiales semiconductores para aplicaciones fotovoltaicas. Las medidas de conductividad a oscuras en función de temperatura fueron realizadas para región de bajas temperaturas entre 120 y 400 K con Si y compuestos Cu3BiS2 y Cu2ZnSnSe4. Siguiendo la teoría de percolación, se obtuvieron parámetros hopping y la densidad de estados cerca del nivel de Fermi, N(EF), para todas las muestras. A partir de los planteamientos dados por Mott para VRH, se presentó el modelo difusional, que permitió establecer la relación entre la conductividad y la densidad de estados de defecto o estados localizados en el gap del material. El análisis comparativo entre modelos, evidenció, que es posible obtener mejora hasta de un orden de magnitud en valores para cada uno de los parámetros hopping que caracterizan el material.

Desenvolvimento de um algoritmo para identificação e correção de spikes em espectroscopia Raman de imagem

Raman imaging spectroscopy is a highly useful analytical tool that provides spatial and spectral information on a sample. However, CCD detectors used in dispersive instruments present the drawback of being sensitive to cosmic rays, giving rise to spikes in Raman spectra. Spikes influence variance structures and must be removed prior to the use of multivariate techniques. A new algorithm for correction of spikes in Raman imaging was developed using an approach based on comparison of nearest neighbor pixels. The algorithm showed characteristics including simplicity, rapidity, selectivity and high quality in spike removal from hyperspectral images.

Missing levels in acoustic resonators

It is shown that the deviations of the experimental statistics of six chaotic acoustic resonators from Wigner-Dyson random matrix theory predictions are explained by a recent model of random missing levels. In these resonatorsa made of aluminum plates a the larger deviations occur in the spectral rigidity (SRs) while the nearest-neighbor distributions (NNDs) are still close to the Wigner surmise. Good fits to the experimental NNDs and SRs are obtained by adjusting only one parameter, which is the fraction of remaining levels of the complete spectra. For two Sinai stadiums, one Sinai stadium without planar symmetry, two triangles, and a sixth of the three-leaf clover shapes, was found that 7%, 4%, 7%, and 2%, respectively, of eigenfrequencies were not detected.

Amorphous HfO(2) and Hf(1-x)Si(x)O via a melt-and-quench scheme using ab initio molecular dynamics

We have performed ab initio molecular dynamics simulations to generate an atomic structure model of amorphous hafnium oxide (a-HfO(2)) via a melt-and-quench scheme. This structure is analyzed via bond-angle and partial pair distribution functions. These results give a Hf-O average nearest-neighbor distance of 2.2 angstrom, which should be compared to the bulk value, which ranges from 1.96 to 2.54 angstrom. We have also investigated the neutral O vacancy and a substitutional Si impurity for various sites, as well as the amorphous phase of Hf(1-x)Si(x)O(2) for x=0.25, 0375, and 0.5.

Multiclass Hammersley-Aldous-Diaconis process and multiclass-customer queues

In the Hammersley-Aldous-Diaconis process, infinitely many particles sit in R and at most one particle is allowed at each position. A particle at x, whose nearest neighbor to the right is at y, jumps at rate y - x to a position uniformly distributed in the interval (x, y). The basic coupling between trajectories with different initial configuration induces a process with different classes of particles. We show that the invariant measures for the two-class process can be obtained as follows. First, a stationary M/M/1 queue is constructed as a function of two homogeneous Poisson processes, the arrivals with rate, and the (attempted) services with rate rho > lambda Then put first class particles at the instants of departures (effective services) and second class particles at the instants of unused services. The procedure is generalized for the n-class case by using n - 1 queues in tandem with n - 1 priority types of customers. A multi-line process is introduced; it consists of a coupling (different from Liggett's basic coupling), having as invariant measure the product of Poisson processes. The definition of the multi-line process involves the dual points of the space-time Poisson process used in the graphical construction of the reversed process. The coupled process is a transformation of the multi-line process and its invariant measure is the transformation described above of the product measure.

A chemometric study on the analgesic activity of cannabinoid compounds using SDA, KNN and SIMCA methods

The supervised pattern recognition methods K-Nearest Neighbors (KNN), stepwise discriminant analysis (SDA), and soft independent modelling of class analogy (SIMCA) were employed in this work with the aim to investigate the relationship between the molecular structure of 27 cannabinoid compounds and their analgesic activity. Previous analyses using two unsupervised pattern recognition methods (PCA-principal component analysis and HCA-hierarchical cluster analysis) were performed and five descriptors were selected as the most relevants for the analgesic activity of the compounds studied: R (3) (charge density on substituent at position C(3)), Q (1) (charge on atom C(1)), A (surface area), log P (logarithm of the partition coefficient) and MR (molecular refractivity). The supervised pattern recognition methods (SDA, KNN, and SIMCA) were employed in order to construct a reliable model that can be able to predict the analgesic activity of new cannabinoid compounds and to validate our previous study. The results obtained using the SDA, KNN, and SIMCA methods agree perfectly with our previous model. Comparing the SDA, KNN, and SIMCA results with the PCA and HCA ones we could notice that all multivariate statistical methods classified the cannabinoid compounds studied in three groups exactly in the same way: active, moderately active, and inactive.

Entanglement in a simple quantum phase transition

What entanglement is present in naturally occurring physical systems at thermal equilibrium? Most such systems are intractable and it is desirable to study simple but realistic systems that can be solved. An example of such a system is the one-dimensional infinite-lattice anisotropic XY model. This model is exactly solvable using the Jordan-Wigner transform, and it is possible to calculate the two-site reduced density matrix for all pairs of sites. Using the two-site density matrix, the entanglement of formation between any two sites is calculated for all parameter values and temperatures. We also study the entanglement in the transverse Ising model, a special case of the XY model, which exhibits a quantum phase transition. It is found that the next-nearest-neighbor entanglement (though not the nearest-neighbor entanglement) is a maximum at the critical point. Furthermore, we show that the critical point in the transverse Ising model corresponds to a transition in the behavior of the entanglement between a single site and the remainder of the lattice.

Phase diagram of the one-dimensional Holstein model of spinless fermions

The one-dimensional Holstein model of spinless fermions interacting with dispersionless phonons is studied using a new variant of the density matrix renormalization group. By examining various low-energy excitations of finite chains, the metal-insulator phase boundary is determined precisely and agrees with the predictions of strong coupling theory in the antiadiabatic regime and is consistent with renormalization group arguments in the adiabatic regime. The Luttinger liquid parameters, determined by finite-size scaling, are consistent with a Kosterlitz-Thouless transition.

Phase diagram of a Heisenberg spin-Peierls model with quantum phonons

Using a new version of the density-matrix renormalization group we determine the phase diagram of a model of an antiferromagnetic Heisenberg spin chain where the spins interact with quantum phonons. A quantum phase transition from a gapless spin-fluid state to a gapped dimerized phase occurs at a nonzero value of the spin-phonon coupling. The transition is in the same universality class as that of a frustrated spin chain, to which the model maps in the diabatic limit. We argue that realistic modeling of known spin-Peierls materials should include the effects of quantum phonons.

Accelerating seismic energy release and evolution of event time and size statistics: Results from two heterogeneous cellular automaton models

The evolution of event time and size statistics in two heterogeneous cellular automaton models of earthquake behavior are studied and compared to the evolution of these quantities during observed periods of accelerating seismic energy release Drier to large earthquakes. The two automata have different nearest neighbor laws, one of which produces self-organized critical (SOC) behavior (PSD model) and the other which produces quasi-periodic large events (crack model). In the PSD model periods of accelerating energy release before large events are rare. In the crack model, many large events are preceded by periods of accelerating energy release. When compared to randomized event catalogs, accelerating energy release before large events occurs more often than random in the crack model but less often than random in the PSD model; it is easier to tell the crack and PSD model results apart from each other than to tell either model apart from a random catalog. The evolution of event sizes during the accelerating energy release sequences in all models is compared to that of observed sequences. The accelerating energy release sequences in the crack model consist of an increase in the rate of events of all sizes, consistent with observations from a small number of natural cases, however inconsistent with a larger number of cases in which there is an increase in the rate of only moderate-sized events. On average, no increase in the rate of events of any size is seen before large events in the PSD model.

Charge ordering and antiferromagnetic exchange in layered molecular crystals of the theta type

We consider the electronic properties of layered molecular crystals of the type theta -D(2)A where A is an anion and D is a donor molecule such as bis-(ethylenedithia-tetrathiafulvalene) (BEDT-TTF), which is arranged in the theta -type pattern within the layers. We argue that the simplest strongly correlated electron model that can describe the rich phase diagram of these materials is the extended Hubbard model on the square lattice at one-quarter filling. In the limit where the Coulomb repulsion on a single site is large, the nearest-neighbor Coulomb repulsion V plays a crucial role. When V is much larger than the intermolecular hopping integral t the ground state is an insulator with charge ordering. In this phase antiferromagnetism arises due to a novel fourth-order superexchange process around a plaquette on the square lattice. We argue that the charge ordered phase is destroyed below a critical nonzero value V, of the order of t. Slave-boson theory is used to explicitly demonstrate this for the SU(N) generalization of the model, in the large-N limit. We also discuss the relevance of the model to the all-organic family beta-(BEDT-TTF)(2)SF5YSO3 where Y=CH2CF2, CH2, CHF.