Centroid algorithm

As stated in Chap. 2, in a PET scanner, block detectors are cut into small detectors and coupled with four PM tubes, which are arranged in arrays of rings. Each detector is connected in coincidence to as many as N/2 detectors, where N is the number of small detectors in the ring. So which two detectors detected a coincidence event within the time window must be determined. Pulses produced in PM tubes are used to determine the locations of the two detectors (Fig. 3.2). As in scintillation cameras, the position of each detector is estimated by a weighted centroid algorithm. This algorithm estimates... 

An alternative way of measuring the dissimilarity of one compound to a set of compounds is to sum the pairwise dissimilarities between the compound and all compounds in the set. The most dissimilar compound to a set is then the compound which has the maximum sum of pairwise dissimilarities. Holliday et al. [51] have implemented an efficient version of DBCS that uses the cosine coefficient as the (dis)similarity coefficient. Their algorithm is called the Centroid algorithm and operates in O(nN) and can thus be applied to very large datasets. However, as Snarey et al. [52] have pointed out, there is a tendency for the algorithm to focus on outliers. 

The development of resonant ion ejection scanning, commonly called axial modulation, increased the mass resolution to unit resolution over the entire mass range. The ITS-40 was introduced in 1989 with axial modulation scanning and a high temperature vacuum chamber. The increased power of microprocessors available at that time allowed more sophisticated mass centroiding algorithms to be applied. 

Cao, J., Voth, G.A. The formulation of quantum statistical mechanics based on the Feynman path centroid density. I. Equilibrium properties. J. Chem. Phys. 100 (1994) 5093-5105 II Dynamical properties. J. Chem. Phys. 100 (1994) 5106-5117 III. Phase space formalism and nalysis of centroid molecular dynamics. J. Chem. Phys. 101 (1994) 6157-6167 IV. Algorithms for centroid molecular dynamics. J. Chem. Phys. 101 (1994) 6168-6183 V. Quantum instantaneous normal mode theory of liquids. J. Chem. Phys. 101 (1994) 6184 6192. 

The same idea can be developed in the case of a non-Euclidean metric such as the city-block metric or L,-norm (Section 31.6.1). Here we find that the trajectories, traced out by the variable coefficient kj are curvilinear, rather than linear. Markers between equidistant values on the original scales of the columns of X are usually not equidistant on the corresponding curvilinear trajectories of the nonlinear biplot (Fig. 31.17b). Although the curvilinear trajectories intersect at the origin of space, the latter does not necessarily coincide with the centroid of the row-points of X. We briefly describe here the basic steps of the algorithm and we refer to the original work of Gower [53,54] for a formal proof. 

The most widely known algorithm for partitioning is the k means algorithm (Hartigan 1975). It uses pairwise distances between the objects, and requires the input of the desired number k of clusters. Internally, the k-means algorithm uses the so-called centroids (means) representing the center of each cluster. For example, a centroid c, of a cluster j = 1,..., k can be defined as the arithmetic mean vector of all objects of the corresponding cluster, i.e.,... 

The objective function (Equation 6.7) also makes clear that not all pairwise distances are needed by the algorithm, but only the distances of the objects to all cluster centroids. For minimizing this objective function, several algorithms have been proposed. The most widely used algorithm for fc-means works as follows ... 

The algorithm usually always converges however, it does not necessarily find the global minimum of the objective function (Equation 6.7). The outcome of the /t-means algorithm also depends on the initialization of the cluster centroids in step 1. As a possible solution, the algorithm can be run several times to reduce this drawback. 

Instead of using the Euclidean distance, also other distance measures can be considered. Moreover, another power than 2 could be used for the membership coefficients, which will change the characteristics of the procedure (degree of fuzzification). Similar to fc-means, the number of clusters k has to be provided as an input, and the algorithm also uses cluster centroids Cj which are now computed by... 

So, the cluster centroids are weighted averages of all observations, with weights based on the membership coefficients of all observations to the corresponding cluster. When using only memberships of 0 and 1, this algorithm reduces to /.--means. 

In the Algorithms menu, SOM is chosen, and the number of clusters for display is selected by changing the numbers in SOM rows and SOM columns see Note 41). The advanced parameters are left at default value. The icon Run is clicked, which activates the processing of the data and the display in clusters. Standard deviations are displayed as red lines outside the centroids and displayed as blue lines connecting the dots, which each represent a sample see Fig. 16.2A). 

Cluster Algorithm. The Forgy variety of k-means cluster analysis ( ) is chosen because of its speed for large data sets. Forgy k-means cluster analysis is an iterative process. In the first iteration observations are assigned to the nearest centroid. This defines the initial clusters. The composition of the observations in each cluster are then averaged to find approximate centroids. Let xk be the centroid vector for cluster k. with components xkj. for... 

In order to characterize the interaction between different clusters, it is necessary to consider the mechanism of cluster identification during the process of the DA algorithm. As the temperature (Tk) is reduced after every iteration, the system undergoes a series of phase transitions (see (18) for details). In this annealing process, at high temperatures that are above a pre-computable critical value, all the lead compounds are located at the centroid of the entire descriptor space, thereby there is only one distinct location for the lead compounds. As the temperature is decreased, a critical temperature value is reached where a phase transition occurs, which results in a greater number of distinct locations for lead compounds and consequently finer clusters are formed. This provides us with a tool to control the number of clusters we want in our final selection. It is shown (18) for a square Euclidean distance d(xi,rj) = x, — rj that a cluster Rj splits at a critical temperature Tc when twice the maximum eigenvalue of the posterior covariance matrix, defined by Cx rj =... 

The algorithm starts with one lead compound at the centroid of the dataset. As the temperature is reduced, the cluster is split and separate regions are determined at each such split. 

---