# A Clustering Method for Data in Cylindrical Coordinates

Authors: Kazuhisa Fujita
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We propose a new clustering method for data in cylindrical coordinates based on thek-means. The goal of the k-means family is to maximize an optimization function, which requires a similarity. Thus, we need a new similarity to obtain the new clustering method for data in cylindrical coordinates. In this study, we first derive a new similarity for the new clustering method by assuming a particular probabilistic model. A data point in cylindrical coordinates has radius, azimuth, and height. We assume that the azimuth is sampled from a von Mises distribution and the radius and the height are independently generated from isotropic Gaussian distributions. We derive the new similarity from the log likelihood of the assumed probability distribution. Our experiments demonstrate that the proposed method using the new similarity can appropriately partition synthetic data defined in cylindrical coordinates. Furthermore, we apply the proposed method to color image quantization and show that the methods successfully quantize a color image with respect to the hue element.


---

## Body

## 1. Introduction

Clustering is an important technique in many areas such as data analysis, data visualization, image processing, and pattern recognition. The most popular and useful clustering method is thek-means. The k-means uses the Euclidean distance as coefficient and partitions data to k clusters. The Euclidean distance is a reasonable measurement for data sampled from an isotropic Gaussian distribution. We cannot always obtain a good clustering result using the k-means because not all data distributions are isotropic Gaussian distributions.The present study focuses on data in cylindrical coordinates. Data in cylindrical coordinates have a periodic element, so clustering methods using the Euclidean distance will lead to an improper analysis of the data. Furthermore, a clustering method using the Euclidean distance may not be able to extract meaningful centroids. For example, if a distribution in cylindrical coordinates is remarkably curved crescent-shape, the centroid of the distribution calculated by thek-means may not be on the data distribution. However, there are no clustering methods optimized for data in cylindrical coordinates.The cylindrical data are found in many fields such as image processing, meteorology, and biology. Movements of plants and animals and wind direction with another environmental measure are typical examples of cylindrical data [1]. The most popular example of data in cylindrical coordinates is color defined in the HSV color model. The HSV color has three attributes that are hue (direction), saturation (radius), and value that means brightness (height). The HSV color model can represent hue information and has a more natural correspondence to human vision than the RGB color model [2]. The clustering method for cylindrical coordinates is useful for many fields, especially image processing.The purpose of this study is to develop a new clustering method for data in cylindrical coordinates based on thek-means. We first derive a new similarity for clustering data in cylindrical coordinates assuming that the data are sampled from a probabilistic model that is the product of a von Mises distribution and Gaussian distributions. We propose a new clustering method with this new similarity for data in cylindrical coordinates. Using numerical experiments, we demonstrate that the proposed method can partition synthetic data. Furthermore, we evaluate the performance of the proposed method for real world data. Finally, we apply the proposed method to color image quantization and demonstrate that it can quantize a color image according to the hue.


## 2. Related Works

The most commonly used clustering method is thek-means [3], which is one of the top 10 most common algorithms used in data mining [4]. We have applied the k-means to various fields because it is fast, simple, and easy to understand. It uses the Euclidean distance as a clustering criterion and assumes that the data is sampled from a mixture of isotropic Gaussian distributions. Thus, we can apply the k-means to data sampled from a mixture of isotropic Gaussian distributions, but the k-means is not appropriate for data generated from other distributions. Data in cylindrical coordinates have periodic characteristics, so the k-means will be inappropriate as a clustering method for the data.We can cluster periodic data distributed on ann-dimensional sphere surface using the spherical k-means (sk-means). Dhillon and Modha [5] and Banerjee et al. [6, 7] have developed the sk-means for clustering high dimensional text data. It is a k-means based method that uses cosine similarity as the criterion for clustering. The sk-means assumes that the data are sampled from a mixture of von Mises-Fisher distributions with the same concentrate parameters and the same mixture weights. However, we cannot apply the sk-means to data that have direction, radius, and height. To appropriately partition these data, we need a different nonlinear separation method.There are many methods for achieving nonlinear separation. One method is the kernelk-means [8], which partitions the data points in a higher-dimensional feature space after they are mapped to the feature space using a nonlinear function. The spectral clustering [9] is another popular modern nonlinear clustering method, which uses the eigenvectors of a similarity (kernel) matrix to partition data points. The support vector clustering [10] is inspired by the support vector machine [11]. These nonlinear clustering methods based on the kernel method can provide reasonable clustering results for non-Gaussian data. However, these methods can hardly provide significant statistics because they perform the clustering in a feature space. This is a problem when we also want to determine some features of data, such as color image quantization. Furthermore, we must experimentally select the optimal kernel functions and its parameters.Clustering methods are frequently used for color image quantization. Color image quantization reduces the number of colors in an image and plays an important role in applications such as image segmentation [12], image compression [13], and color feature extraction [14]. A color quantization technique consists of two stages: the palette design stage and the pixel mapping stage. These stages can be, respectively, regarded as calculating the centroids and assigning a data point to a cluster. Many researchers have developed color quantization methods including median cut [15], the k-means [16], the fuzzy c-means [17, 18], the self-organizing maps [19–21], and the particle swarm optimization [22]. However, generally, color quantization is performed in the RGB color space although HSV color space is rarely adopted.


## 3. Methodology

### 3.1. Assumed Probabilistic Distribution

A data point in cylindrical coordinates,x, is represented by x=(r,u,z) with u=1 and r≥0, where r,u,z are called the radius, azimuth, and height, respectively. In this study, we represent the azimuth as a unit vector u=(ux,uy) to simply calculate the cosine similarity. Here, each element of x is assumed to be independent and identically distributed. Let a data point in cylindrical coordinates, x=(r,u,z), be generated by a probability density function (pdf) of the form(1)px∣θ=vMu∣μu,κNr∣μr,σr2Nz∣μz,σz2,where θ={μu,μr,μz,κ,σr2,σz2} and vM· and N(·) are pdfs of a von Mises distribution and an isotropic Gaussian distribution, respectively. A pdf of a von Mises distribution vM(·) has the form(2)vMu∣μu,κ=12πI0κexp⁡κμuTu,where μu is the mean of the azimuth with μu=1, κ is the concentrate parameter, and I0(·) is the modified Bessel function of the first kind (order 0). A pdf of an isotropic Gaussian distribution N(·) has the form(3)Ny∣μ,σ2=12πσexp⁡-y-μ22σ2,where μ is the mean and σ2 is the variance. μr and μz are the means of the radius and height, respectively. σr2 and σz2 are the variances of radius and height, respectively. Thus, the density px∣θ can be written as(4)px∣θ=14π2σrσzI0κexp⁡κμuTu-r-μr22σr2-z-μz22σz2.We can estimate the parameters of densitypx∣θ using maximum likelihood estimation. Let data set X={x1,…,xN} be generated from density pX∣θ. The log likelihood function of pX∣θ is (5)ln⁡pX∣θ=∑i=1Nln⁡pxi∣θ=∑i=1N-ln⁡4π2σrσzI0κ+κμuTui-ri-μr22σr2-zi-μz22σz2.Maximizing this equation subject to μuTμu=1, we find the maximum likelihood estimates μ^u, μ^r,   μ^z, A(κ^), σ^r, and σ^z obtained from(6)μ^u=∑i=1Nui∑i=1Nui,Aκ^=R¯,μ^r=1N∑i=1Nri,σ^r2=1N∑i=1Nri-μ^r2,μ^z=1N∑i=1Nzi,σ^z2=1N∑i=1Nzi-μ^z2,where A(κ^) is(7)Aκ^=I0′κ^I0κ^=∑i=1NuiN=R¯.It is difficult to estimate the concentrate parameterκ, because an analytic solution cannot be obtained using the maximum likelihood estimate and we can only calculate the ratio of the Bessel functions. We approximate κ using the numerical method proposed by Sra [23], because it produces the most accurate estimates for κ (compared to other methods).We estimateκ using the recursive function(8)κn=κn-1-Apκn-1-R¯1-Apκn-12-p-1/κn-1Apκn-1,where n is the iteration number. The recursive calculations terminate when κn-κn-1<εκ. In this study, εκ=0.001. We calculate κ0 using the method proposed by Banerjee et al. [6]. κ0 is(9)κ0=R¯2-R¯21-R¯2.


### 3.2. Cylindricalk-Means

Thek-means family uses a particular similarity to decide whether a data point belongs to a cluster. The Euclidean distance (dissimilarity) is most frequently used by the k-means family, and, moreover, is derived using the log likelihood of an isotropic Gaussian distribution. Therefore, the k-means using the Euclidean distance will be able to appropriately partition data sampled from isotropic Gaussian distributions but not other distributions. We must develop a new similarity for data in cylindrical coordinates because the k-means family clusters by maximizing the sum of similarities between a centroid of a cluster and data points that belong to the cluster. In this study, we obtain the optimal similarity for partitioning data in cylindrical coordinates from an assumed pdf.First, to develop ak-means based method for data in cylindrical coordinates (cylindrical k-means; cyk-means), we obtain a new similarity measure for data in cylindrical coordinates by assuming a probability distribution. Assume that a data point x in a cluster that has a centroid m=(μr,μu,μz) is sampled from the probability distribution px∣θ denoted by (4) where θ=(m,κ,σr,σz). The natural logarithm of px∣θ is(10)ln⁡px∣θ=κμuTu-r-μr22σr2-z-μz22σz2+ln⁡C,where C is a normalizing constant given by(11)C=14π2σrσzI0κ.Here, we ignore the normalizing constant ln⁡C to obtain (12)Sx,m=κμuTu-r-μr22σr2-z-μz22σz2.In this study, this equation is used as a similarity for the cyk-means. S(x,m) denotes the similarity between the data point x and the centroid m. The terms in (12) consist of the cosine similarity and the Euclidean similarities, and the new similarity is a sum of these similarities weighed. The weights indicate the concentrations of distributions. This similarity can also be considered as a simplified log likelihood.The cyk-means partitions data points in cylindrical coordinates intoK clusters using the procedure same as the k-means. Let X={x1,…,xN} be a set of data points in cylindrical coordinates. Let mj=(μrj,μuj,μzj) be the centroid of the jth cluster. Using the similarity S(xi,mj), the objective function J is (13)J=∑i=1N∑j=1KγijSxi,mj=∑i=1N∑j=1KγijκμujTui-ri-μrj22σrj2-zi-μzj22σzj2,where γij is a binary indicator value. If the ith data point belongs to the jth cluster, γij=1. Otherwise, γij=0. The aim of the cyk-means is to maximize the objective function J. The process to maximize the objective function is the same as that of the k-means and is described as follows. (1)
FixK and initialize mj.(2)
Assign each data point to the cluster that has the most similar centroid.(3)
Estimate parameters of clusters.(4)
Return to Step(2) if the cluster assignment of data points changes or the difference in the values of the optimal function from the current and last iteration is more than a threshold εJ. Otherwise, terminate the procedure.In this study, we use εJ=0.001×Jn where Jn is the objective function of the nth iteration. Algorithm 1 shows the details of the algorithm of the cyk-means. From (6), the elements of the centroid vector, mj=(μrj,μuj,μzj), of the jth cluster are(14)μrj=1Nj∑i=1Nγijri,μuj=∑i=1Nγiju∑i=1Nγiju,μrj=1Nj∑i=1Nγijzi,where Nj is the number of data points in the jth cluster (which has the form Nj=∑i=1N‍γij). The other values used to calculate the objective function are (15)R¯j=∑i=1NγijuiNj,σrj2=1Nj∑i=1Nγijri-μrj2,σzj2=1Nj∑i=1Nγijzi-μzj2.κj is approximated by Sra’s method using the ratio of the Bessel function R¯j.Algorithm 1:cyk-means.
Input: Set X of data points in cylindrical coordinates
Output: A clustering of X
(1) Initializeθj,j=1,…,K
(2)repeat
(3) Set γij=0,i=1,…,N,j=1,…,K
(4)Assign data points to clusters
(5)for  i=0 to Ndo
(6)j⟵arg⁡maxj′⁡κj′μuj′Tui-ri-μrj′22σrj′2-zi-μzj′22σzj′2
(7)γij=1
(8)end for
(9)Estimate parameters
(10)for  j=1 to K  do
(11)Nj=∑i=1Nγij
(12)μrj=1Nj∑i=1Nγijri
(13)μuj=∑i=1Nγijui∑i=1Nγijui
(14)μzj=1Nj∑i=1Nγijzi
(15)σrj2=1Nj∑i=1Nγijri-μrj2
(16)σzj2=1Nj∑i=1Nγijzi-μzj2
(17)R-j=∑i=1NγijuiNj
(18)κj=R-j2-R-j21-R-j2
(19)repeat
(20)κj⟵κj-Apκj-R-j1-Apκj2-p-1/κjApκj
(21)until convergence
(22)end for
(23)until convergenceThe cyk-means method has many parameters. Thek-means method for data in three-dimensional Cartesian coordinates has only 3K parameters, which are multiples of the number of centroid vectors and dimensions. However, the cyk-means has 7K parameters, which are multiples of the number of clusters and the number of parameters of a cluster. The parameters of the jth cluster are μrj, μuj (two dimensions), μrj, σrj, κj, and σzj. Because the cyk-means has more degrees of freedom, the dead unit problem (i.e., empty clusters) will frequently occur if the initial k is not optimal.


### 3.3. Fixed cyk-Means

Model based clustering methods have various problems such as the dead units and initial value problems. One reason for this is that the log likelihood equation can have many local optima [9]. If a model has more parameters, these problems tend to be more frequent. In the fixed cyk-means, the concentrate parameter κ and the variances σ2s are fixed for particular values. As a consequence, the fixed cyk-means has 4K parameters. Fixing the parameters decreases the complexity of the model and makes these problems less. Algorithm 2 indicates the fixed cyk-means algorithm.Algorithm 2:Fixed cyk-means.
Input: Set X of data points in cylindrical coordinates
Output: A clustering of X
(1) Initializeθj,j=1,…,K
(2)repeat
(3) Set γij=0,i=1,…,N,j=1,…,K
(4)Assign data points to clusters
(5)for  i=0 to N  do
(6)j⟵arg⁡maxj′⁡κj′μuj′Tui-ri-μrj′22σrj′2-zi-μzj′22σzj′2
(7)γij=1
(8)end for
(9)Estimate parameters
(10)for  j=1 to K  do
(11)Nj=∑i=1Nγij
(12)μrj=1Nj∑i=1Nγijri
(13)μuj=∑i=1Nγijui∑i=1Nγijui
(14)μrj=1Nj∑i=1Nγijzi
(15)end for
(16)until convergence


### 3.4. Computational Complexity

Assigning data points to clusters has a complexity ofO(KN) per iteration. We must estimate six parameters. We obtain three μs, two σs, and κ in O(6KN+Ktκmax) time per iteration, where tκmax is the convergence time of κ. Therefore, the total computational complexity per iteration is O(7KN+Ktκmax). The complexity of the fixed cyk-means is O(5KN) per iteration, so the cyk-means is approximately 1.5 times as complex as the fixed cyk-means.


## 3.1. Assumed Probabilistic Distribution

A data point in cylindrical coordinates,x, is represented by x=(r,u,z) with u=1 and r≥0, where r,u,z are called the radius, azimuth, and height, respectively. In this study, we represent the azimuth as a unit vector u=(ux,uy) to simply calculate the cosine similarity. Here, each element of x is assumed to be independent and identically distributed. Let a data point in cylindrical coordinates, x=(r,u,z), be generated by a probability density function (pdf) of the form(1)px∣θ=vMu∣μu,κNr∣μr,σr2Nz∣μz,σz2,where θ={μu,μr,μz,κ,σr2,σz2} and vM· and N(·) are pdfs of a von Mises distribution and an isotropic Gaussian distribution, respectively. A pdf of a von Mises distribution vM(·) has the form(2)vMu∣μu,κ=12πI0κexp⁡κμuTu,where μu is the mean of the azimuth with μu=1, κ is the concentrate parameter, and I0(·) is the modified Bessel function of the first kind (order 0). A pdf of an isotropic Gaussian distribution N(·) has the form(3)Ny∣μ,σ2=12πσexp⁡-y-μ22σ2,where μ is the mean and σ2 is the variance. μr and μz are the means of the radius and height, respectively. σr2 and σz2 are the variances of radius and height, respectively. Thus, the density px∣θ can be written as(4)px∣θ=14π2σrσzI0κexp⁡κμuTu-r-μr22σr2-z-μz22σz2.We can estimate the parameters of densitypx∣θ using maximum likelihood estimation. Let data set X={x1,…,xN} be generated from density pX∣θ. The log likelihood function of pX∣θ is (5)ln⁡pX∣θ=∑i=1Nln⁡pxi∣θ=∑i=1N-ln⁡4π2σrσzI0κ+κμuTui-ri-μr22σr2-zi-μz22σz2.Maximizing this equation subject to μuTμu=1, we find the maximum likelihood estimates μ^u, μ^r,   μ^z, A(κ^), σ^r, and σ^z obtained from(6)μ^u=∑i=1Nui∑i=1Nui,Aκ^=R¯,μ^r=1N∑i=1Nri,σ^r2=1N∑i=1Nri-μ^r2,μ^z=1N∑i=1Nzi,σ^z2=1N∑i=1Nzi-μ^z2,where A(κ^) is(7)Aκ^=I0′κ^I0κ^=∑i=1NuiN=R¯.It is difficult to estimate the concentrate parameterκ, because an analytic solution cannot be obtained using the maximum likelihood estimate and we can only calculate the ratio of the Bessel functions. We approximate κ using the numerical method proposed by Sra [23], because it produces the most accurate estimates for κ (compared to other methods).We estimateκ using the recursive function(8)κn=κn-1-Apκn-1-R¯1-Apκn-12-p-1/κn-1Apκn-1,where n is the iteration number. The recursive calculations terminate when κn-κn-1<εκ. In this study, εκ=0.001. We calculate κ0 using the method proposed by Banerjee et al. [6]. κ0 is(9)κ0=R¯2-R¯21-R¯2.


## 3.2. Cylindricalk-Means

Thek-means family uses a particular similarity to decide whether a data point belongs to a cluster. The Euclidean distance (dissimilarity) is most frequently used by the k-means family, and, moreover, is derived using the log likelihood of an isotropic Gaussian distribution. Therefore, the k-means using the Euclidean distance will be able to appropriately partition data sampled from isotropic Gaussian distributions but not other distributions. We must develop a new similarity for data in cylindrical coordinates because the k-means family clusters by maximizing the sum of similarities between a centroid of a cluster and data points that belong to the cluster. In this study, we obtain the optimal similarity for partitioning data in cylindrical coordinates from an assumed pdf.First, to develop ak-means based method for data in cylindrical coordinates (cylindrical k-means; cyk-means), we obtain a new similarity measure for data in cylindrical coordinates by assuming a probability distribution. Assume that a data point x in a cluster that has a centroid m=(μr,μu,μz) is sampled from the probability distribution px∣θ denoted by (4) where θ=(m,κ,σr,σz). The natural logarithm of px∣θ is(10)ln⁡px∣θ=κμuTu-r-μr22σr2-z-μz22σz2+ln⁡C,where C is a normalizing constant given by(11)C=14π2σrσzI0κ.Here, we ignore the normalizing constant ln⁡C to obtain (12)Sx,m=κμuTu-r-μr22σr2-z-μz22σz2.In this study, this equation is used as a similarity for the cyk-means. S(x,m) denotes the similarity between the data point x and the centroid m. The terms in (12) consist of the cosine similarity and the Euclidean similarities, and the new similarity is a sum of these similarities weighed. The weights indicate the concentrations of distributions. This similarity can also be considered as a simplified log likelihood.The cyk-means partitions data points in cylindrical coordinates intoK clusters using the procedure same as the k-means. Let X={x1,…,xN} be a set of data points in cylindrical coordinates. Let mj=(μrj,μuj,μzj) be the centroid of the jth cluster. Using the similarity S(xi,mj), the objective function J is (13)J=∑i=1N∑j=1KγijSxi,mj=∑i=1N∑j=1KγijκμujTui-ri-μrj22σrj2-zi-μzj22σzj2,where γij is a binary indicator value. If the ith data point belongs to the jth cluster, γij=1. Otherwise, γij=0. The aim of the cyk-means is to maximize the objective function J. The process to maximize the objective function is the same as that of the k-means and is described as follows. (1)
FixK and initialize mj.(2)
Assign each data point to the cluster that has the most similar centroid.(3)
Estimate parameters of clusters.(4)
Return to Step(2) if the cluster assignment of data points changes or the difference in the values of the optimal function from the current and last iteration is more than a threshold εJ. Otherwise, terminate the procedure.In this study, we use εJ=0.001×Jn where Jn is the objective function of the nth iteration. Algorithm 1 shows the details of the algorithm of the cyk-means. From (6), the elements of the centroid vector, mj=(μrj,μuj,μzj), of the jth cluster are(14)μrj=1Nj∑i=1Nγijri,μuj=∑i=1Nγiju∑i=1Nγiju,μrj=1Nj∑i=1Nγijzi,where Nj is the number of data points in the jth cluster (which has the form Nj=∑i=1N‍γij). The other values used to calculate the objective function are (15)R¯j=∑i=1NγijuiNj,σrj2=1Nj∑i=1Nγijri-μrj2,σzj2=1Nj∑i=1Nγijzi-μzj2.κj is approximated by Sra’s method using the ratio of the Bessel function R¯j.Algorithm 1:cyk-means.
Input: Set X of data points in cylindrical coordinates
Output: A clustering of X
(1) Initializeθj,j=1,…,K
(2)repeat
(3) Set γij=0,i=1,…,N,j=1,…,K
(4)Assign data points to clusters
(5)for  i=0 to Ndo
(6)j⟵arg⁡maxj′⁡κj′μuj′Tui-ri-μrj′22σrj′2-zi-μzj′22σzj′2
(7)γij=1
(8)end for
(9)Estimate parameters
(10)for  j=1 to K  do
(11)Nj=∑i=1Nγij
(12)μrj=1Nj∑i=1Nγijri
(13)μuj=∑i=1Nγijui∑i=1Nγijui
(14)μzj=1Nj∑i=1Nγijzi
(15)σrj2=1Nj∑i=1Nγijri-μrj2
(16)σzj2=1Nj∑i=1Nγijzi-μzj2
(17)R-j=∑i=1NγijuiNj
(18)κj=R-j2-R-j21-R-j2
(19)repeat
(20)κj⟵κj-Apκj-R-j1-Apκj2-p-1/κjApκj
(21)until convergence
(22)end for
(23)until convergenceThe cyk-means method has many parameters. Thek-means method for data in three-dimensional Cartesian coordinates has only 3K parameters, which are multiples of the number of centroid vectors and dimensions. However, the cyk-means has 7K parameters, which are multiples of the number of clusters and the number of parameters of a cluster. The parameters of the jth cluster are μrj, μuj (two dimensions), μrj, σrj, κj, and σzj. Because the cyk-means has more degrees of freedom, the dead unit problem (i.e., empty clusters) will frequently occur if the initial k is not optimal.


## 3.3. Fixed cyk-Means

Model based clustering methods have various problems such as the dead units and initial value problems. One reason for this is that the log likelihood equation can have many local optima [9]. If a model has more parameters, these problems tend to be more frequent. In the fixed cyk-means, the concentrate parameter κ and the variances σ2s are fixed for particular values. As a consequence, the fixed cyk-means has 4K parameters. Fixing the parameters decreases the complexity of the model and makes these problems less. Algorithm 2 indicates the fixed cyk-means algorithm.Algorithm 2:Fixed cyk-means.
Input: Set X of data points in cylindrical coordinates
Output: A clustering of X
(1) Initializeθj,j=1,…,K
(2)repeat
(3) Set γij=0,i=1,…,N,j=1,…,K
(4)Assign data points to clusters
(5)for  i=0 to N  do
(6)j⟵arg⁡maxj′⁡κj′μuj′Tui-ri-μrj′22σrj′2-zi-μzj′22σzj′2
(7)γij=1
(8)end for
(9)Estimate parameters
(10)for  j=1 to K  do
(11)Nj=∑i=1Nγij
(12)μrj=1Nj∑i=1Nγijri
(13)μuj=∑i=1Nγijui∑i=1Nγijui
(14)μrj=1Nj∑i=1Nγijzi
(15)end for
(16)until convergence


## 3.4. Computational Complexity

Assigning data points to clusters has a complexity ofO(KN) per iteration. We must estimate six parameters. We obtain three μs, two σs, and κ in O(6KN+Ktκmax) time per iteration, where tκmax is the convergence time of κ. Therefore, the total computational complexity per iteration is O(7KN+Ktκmax). The complexity of the fixed cyk-means is O(5KN) per iteration, so the cyk-means is approximately 1.5 times as complex as the fixed cyk-means.


## 4. Experimental Results

In our experiments, we use Python and its libraries (NumPy, SciPy, and scikit-learn) to implement the proposed method.


### 4.1. Synthetic Data

In this subsection, we demonstrate that the cyk-means and the fixed cyk-means can partition synthetic data that is defined using cylindrical coordinates. The dataset used in this experience has three clusters, as shown in Figure1(a). The data points in each cluster are generated from the probability distribution denoted by (4), with the parameters shown in Table 1. Figures 1(b), 1(c), and 1(d) show the clustering results of the cyk-means, the fixed cyk-means with κ=25, σr=0.1, and σz=0.1, and the k-means, respectively. We can see that the cyk-means and the fixed cyk-means properly partition the dataset into each cluster. On the other hand, the k-means regards two upper right clusters as one cluster and unsuccessfully partitions the dataset. Table 2 shows the parameters estimated by the cyk-means, the fixed cyk-means, and the k-means. The cyk-means can only estimate the concentrate parameters and the variances. The values of the concentrate parameters and the variances estimated by the cyk-means are approximate to the true values. The cyk-means most appropriately estimates the number of data points in each cluster. The fixed cyk-means most approximately estimates the all means and the cyk-means also approximately calculates the all means. These results show that the cyk-means and the fixed cyk-means sufficiently approximately estimate the all means.Table 1
Parameters of dataset.
j
N
j
μ
θ
j
κ
j
μ
r
j
σ
r
j
μ
z
j
σ
z
j
1
200
0
8
1
0.2
0.5
0.1
2
300
-
2
4
1.5
0.15
-
0.5
0.2
3
400
2
12
0.5
0.1
1
0.2
j is a cluster number. μθj is the azimuth of the centroid of the jth cluster. μθj=arctan⁡uyj/uxj.Table 2
Parameters estimated by the cyk-means, the fixed cyk-means, and thek-means.
Method
j
N
j
μ
θ
j
κ
j
μ
r
j
σ
r
j
μ
z
j
σ
z
j
cyk-means
1
200
-
1.960
×
1
0
-
3
7.523
0.9746
0.1942
0.5065
0.09417
2
300
-
1.997
3.979
1.495
0.1492
-
0.5070
0.1866
3
400
1.986
12.69
0.4966
0.1004
1.005
0.1997
Fixed cyk-means
1
200.2
-
5
.
124
×
1
0
-
5
—
1.001
—
0.4995
—
2
299.9
-
2
.
000
—
1.501
—
-
0.5056
—
3
400
1.996
—
0.4998
—
0.9995
—
k-means
1
184.85
-
0.6627
—
1.091
—
0.1871
—
2
253.65
-
1.974
—
1.358
—
-
0.4974
—
3
461.5
1.704
—
0.4406
—
0.9477
—
The results are the mean of twenty runs on randomly generated initial values.j is a cluster number. μθj is the azimuth of the centroid of the jth cluster. μθj=arctan⁡(uyj/uxj). The best estimations are bold.Figure 1
(a) Scatter plot of the synthetic dataset including three clusters. (b), (c), (d) Clustering results of the cyk-means, the fixed cyk-means, and thek-means. The three clusters are shown with circles, triangles, and crosses.
(a)
(b)
(c)
(d)In the next experiment, we examine the effectiveness of the proposed methods (the cyk-means and the fixed cyk-means withκ=15, σr=0.1, and σz=0.1) compared to the k-means and the kernel k-means with a radial basis function. The parameter of the radial basis function is γ=0.1. The synthetic data have K clusters and are defined in cylindrical coordinates. The number of data points in each cluster is 200. The mean azimuth of the jth cluster arctan⁡(uy/ux) is a random number in [0,2π}. The concentrate parameter κj is a random number in [5,30}. The mean radius of the jth cluster μrj is a random number in [1,4}. The mean height of the jth cluster μzj is a random number in [-1.5,1.5}. The standard deviations of σrj and σzj are random numbers in [0.05,0.2}.Figure2 shows the relationship between the number of clusters and adjusted rand index (ARI). ARI evaluates the performance of clustering algorithms [24]. When ARI = 1, all data points belong to true clusters. The figure shows that the cyk-means has the largest ARI for almost all cases. The fixed cyk-means performs better than the kernel k-means and the k-means. The k-means performs the worst. In conclusion, the cyk-means most accurately partitions synthetic data defined in cylindrical coordinates, and the fixed cyk-means also performs well.Figure 2
Relationship between the number of clustersK and adjusted rand index (ARI). The vertical and the horizontal lines indicate ARI and the number of clusters K, respectively. The results are the mean of 200 runs on randomly generated synthetic data for each K.


### 4.2. Real World Data

We show the performances of the proposed methods for the iris dataset (http://mlearn.ics.uci.edu/databases/iris/) and the segmentation benchmark dataset (http://www.ntu.edu.sg/home/asjfcai/Benchmark_Website/benchmark_index.html) [25]. The iris dataset has 150 data points of three classes of irises. The data point consists of the four attributes, sepal length in cm, sepal width in cm, petal length in cm, and petal width in cm. The segmentation benchmark dataset consists of 100 images from the Berkeley segmentation database [26] and ground-truths generated by manual labeling.Table3 depicts the ARI scores of the cyk-means, the fixed cyk-means, the k-means, and the kernel k-means for the iris dataset. The parameters of the fixed cyk-means are κ=15, σr=0.1, and σz=0.1. γ of the radial basis function of the kernel k-means is 0.01. In this experiment, we use only three attributes of the iris dataset because the proposed methods are specialized for 3-dimensional data. Furthermore, we transform this dataset that has three attributes into zero mean dataset. In all cases, the performance of the cyk-means is lower than the other methods. Conversely, in almost all cases, the performance of the fixed cyk-means is the best. However, the difference in the performance between the fixed cyk-means, the k-means, and the kernel k-means is not large.Table 3
Comparison of performances of the four methods using the iris dataset.
Attributes
cyk-means
Fixed cyk-means
k-means
Kernelk-means
Sepal length, sepal width, petal length
0.5543
0.6961
0.6569
0.6614
Sepal width, petal length, petal width
0.5627
0.7900
0.7462
0.7590
Petal length, petal width, sepal length
0.4179
0.7114
0.7302
0.7359
Petal width, sepal length, sepal width
0.5171
0.6121
0.6104
0.6099
ARI are the mean of 200 runs with random initial values. The best estimations are bold. “Attributes” indicates three attributes used in clustering.Table4 shows the ARI scores of the cyk-means, the fixed cyk-means, and the k-mean for seven images in the segmentation benchmark dataset. The parameters of the fixed cyk-means are κ=15, σr=0.1, and σz=0.1. To evaluate the performances of the cyk-means and the fixed cyk-means, we convert images from RGB color to HSV color. When we cluster the dataset by the k-means, we use images represented by RGB color and HSV color. In this experiment, we compare a clustering result with a ground truth using the ARI score. We set the number of clusters K to the number of segments in a ground truth. In all cases, the fixed cyk-means stably shows good performance. The cyk-means indicates much better or worse performances than the other methods. In other words, the cyk-means shows unstable performance. This instability will be caused by the cyk-means more easily trapping a local minimum because of more parameters.Table 4
Comparison of performances of the four methods using the segmentation benchmark dataset.
Number
cyk-means
Fixed cyk-means
k-means (HSV)
k-means (RGB)
12003 (K=4)
0.6397
0.3744
0.3695
0.2277
69020 (K=2)
0.1611
0.5247
0.07680
0.1406
80099 (K=2)
0.9205
0.7960
0.6544
0.04890
103029 (K=3)
0.4697
0.5934
0.1794
0.09143
106047 (K=2)
0.3210
0.2988
0.04155
0.02332
310007 (K=7)
0.1548
0.3338
0.3075
0.3396
353013 (K=4)
0.6125
0.5993
0.5020
0.4683
ARI are the mean of 200 runs with random initial values. The best estimations are bold. “Number” indicates the number of the image. “k-means (HSV)” and “k-means (RGB)” indicate that we cluster HSV and RGB color images by the k-means, respectively.


### 4.3. Application to Color Image Quantization

We apply the cyk-means and the fixed cyk-means to color image quantization and compare the results to those using thek-means. We convert images quantized by the proposed methods from RGB color space to HSV color space before quantization, whereas an image processed by the k-means is represented using RGB. Figure 3 contains the four test images from the Berkeley segmentation database [26] and their quantization results. The original color images have sizes of 481×321 or 321×481 and are used as the test images to quantize into three colors. These quantization results are generated by the cyk-means, the fixed cyk-means with κ=25, σr=0.1, and σz=0.1, and the k-means. The color of a pixel in the quantized image represents the value of the centroid of the cluster that contains the pixel.Figure 3
Quantization results. The first column contains the original images. The second, third, and fourth columns contain the quantization results generated by the cyk-means, the fixed cyk-means, and thek-means, respectively. All original images are clustered with K=3.For image 118035 in Figure3, the colors of the background, the wall, and the roof are obviously different from each other. The cyk-means and the fixed cyk-means successfully segment this image, whereas the k-means extracts the shade from the wall and can not merge the wall to one color. Furthermore, the quantization results using the cyk-means and the fixed cyk-means are very similar.Image 26098 consists of red and green peppers on a display table. The cyk-means merges the red peppers and the planks of the display table and divides the dark area into two colors. The fixed cyk-means successfully extracts the red peppers. Thek-means assigns red to the planks and part of the green peppers.Image 299091 consists of some sky with cloud, an ocher pyramid, and ocher ground. The cyk-means groups the ocher pyramid and white cloud into the same color, whereas the fixed cyk-means correctly segments the pyramid and the sky. Thek-means is unsuccessful; it divides the pyramid into three regions (an ocher region, a highlight region, and a shade region).The cyk-means did not perform well for image 295087. It segments the image into two colors even though we set the number of clusters to three. Thus, the cyk-means makes a dead unit. This is because the concentrate parameter and variances, respectively, become small and large if a distribution of data points is regarded to visually consist of a few clusters. Thus, a few clusters include all data points and dead units (empty clusters) appear, even if we fix the number of clusters to a large number. In contrast, the fixed cyk-means (which has fixed concentrate and variance values) appropriately partitions the ground and the blue and the deep blue regions of the sky. Thek-means extracts shaded regions from the ground; that is, it can not group the ground into one region.Furthermore, the initial parameters,κ and σs, of the fixed cyk-means can control the quantization results. Figure 4 shows the quantization results generated by the fixed cyk-means using the different parameters. The original image in Figure 4 consists of two objects: the red fish and the arms of an anemone. The fixed cyk-means with κ=25, σr=0.1, and σz=0.1 can not extract the red fish shown in the middle image of Figure 4. However, the fixed cyk-means with κ=50, σr=0.5, and σz=0.5 extracts the red fish in the left image of Figure 4. This is because a large κ and/or large variances relatively increase the cosine similarity term of (12), and consequently clustering is more focused on the hue element.Figure 4
Quantization results of the fixed cyk-means with different parameters. The left image is the original. The middle and the right images are quantized withK=3.In conclusion, the fixed cyk-means is a more suitable method for color image quantization than the cyk-means. The fixed cyk-means quantizes color images with respect to the hue. The quantization results of the fixed cyk-means differ from that generated byk-means. That is because the Euclidean metric cannot consider the hue.


## 4.1. Synthetic Data

In this subsection, we demonstrate that the cyk-means and the fixed cyk-means can partition synthetic data that is defined using cylindrical coordinates. The dataset used in this experience has three clusters, as shown in Figure1(a). The data points in each cluster are generated from the probability distribution denoted by (4), with the parameters shown in Table 1. Figures 1(b), 1(c), and 1(d) show the clustering results of the cyk-means, the fixed cyk-means with κ=25, σr=0.1, and σz=0.1, and the k-means, respectively. We can see that the cyk-means and the fixed cyk-means properly partition the dataset into each cluster. On the other hand, the k-means regards two upper right clusters as one cluster and unsuccessfully partitions the dataset. Table 2 shows the parameters estimated by the cyk-means, the fixed cyk-means, and the k-means. The cyk-means can only estimate the concentrate parameters and the variances. The values of the concentrate parameters and the variances estimated by the cyk-means are approximate to the true values. The cyk-means most appropriately estimates the number of data points in each cluster. The fixed cyk-means most approximately estimates the all means and the cyk-means also approximately calculates the all means. These results show that the cyk-means and the fixed cyk-means sufficiently approximately estimate the all means.Table 1
Parameters of dataset.
j
N
j
μ
θ
j
κ
j
μ
r
j
σ
r
j
μ
z
j
σ
z
j
1
200
0
8
1
0.2
0.5
0.1
2
300
-
2
4
1.5
0.15
-
0.5
0.2
3
400
2
12
0.5
0.1
1
0.2
j is a cluster number. μθj is the azimuth of the centroid of the jth cluster. μθj=arctan⁡uyj/uxj.Table 2
Parameters estimated by the cyk-means, the fixed cyk-means, and thek-means.
Method
j
N
j
μ
θ
j
κ
j
μ
r
j
σ
r
j
μ
z
j
σ
z
j
cyk-means
1
200
-
1.960
×
1
0
-
3
7.523
0.9746
0.1942
0.5065
0.09417
2
300
-
1.997
3.979
1.495
0.1492
-
0.5070
0.1866
3
400
1.986
12.69
0.4966
0.1004
1.005
0.1997
Fixed cyk-means
1
200.2
-
5
.
124
×
1
0
-
5
—
1.001
—
0.4995
—
2
299.9
-
2
.
000
—
1.501
—
-
0.5056
—
3
400
1.996
—
0.4998
—
0.9995
—
k-means
1
184.85
-
0.6627
—
1.091
—
0.1871
—
2
253.65
-
1.974
—
1.358
—
-
0.4974
—
3
461.5
1.704
—
0.4406
—
0.9477
—
The results are the mean of twenty runs on randomly generated initial values.j is a cluster number. μθj is the azimuth of the centroid of the jth cluster. μθj=arctan⁡(uyj/uxj). The best estimations are bold.Figure 1
(a) Scatter plot of the synthetic dataset including three clusters. (b), (c), (d) Clustering results of the cyk-means, the fixed cyk-means, and thek-means. The three clusters are shown with circles, triangles, and crosses.
(a)
(b)
(c)
(d)In the next experiment, we examine the effectiveness of the proposed methods (the cyk-means and the fixed cyk-means withκ=15, σr=0.1, and σz=0.1) compared to the k-means and the kernel k-means with a radial basis function. The parameter of the radial basis function is γ=0.1. The synthetic data have K clusters and are defined in cylindrical coordinates. The number of data points in each cluster is 200. The mean azimuth of the jth cluster arctan⁡(uy/ux) is a random number in [0,2π}. The concentrate parameter κj is a random number in [5,30}. The mean radius of the jth cluster μrj is a random number in [1,4}. The mean height of the jth cluster μzj is a random number in [-1.5,1.5}. The standard deviations of σrj and σzj are random numbers in [0.05,0.2}.Figure2 shows the relationship between the number of clusters and adjusted rand index (ARI). ARI evaluates the performance of clustering algorithms [24]. When ARI = 1, all data points belong to true clusters. The figure shows that the cyk-means has the largest ARI for almost all cases. The fixed cyk-means performs better than the kernel k-means and the k-means. The k-means performs the worst. In conclusion, the cyk-means most accurately partitions synthetic data defined in cylindrical coordinates, and the fixed cyk-means also performs well.Figure 2
Relationship between the number of clustersK and adjusted rand index (ARI). The vertical and the horizontal lines indicate ARI and the number of clusters K, respectively. The results are the mean of 200 runs on randomly generated synthetic data for each K.


## 4.2. Real World Data

We show the performances of the proposed methods for the iris dataset (http://mlearn.ics.uci.edu/databases/iris/) and the segmentation benchmark dataset (http://www.ntu.edu.sg/home/asjfcai/Benchmark_Website/benchmark_index.html) [25]. The iris dataset has 150 data points of three classes of irises. The data point consists of the four attributes, sepal length in cm, sepal width in cm, petal length in cm, and petal width in cm. The segmentation benchmark dataset consists of 100 images from the Berkeley segmentation database [26] and ground-truths generated by manual labeling.Table3 depicts the ARI scores of the cyk-means, the fixed cyk-means, the k-means, and the kernel k-means for the iris dataset. The parameters of the fixed cyk-means are κ=15, σr=0.1, and σz=0.1. γ of the radial basis function of the kernel k-means is 0.01. In this experiment, we use only three attributes of the iris dataset because the proposed methods are specialized for 3-dimensional data. Furthermore, we transform this dataset that has three attributes into zero mean dataset. In all cases, the performance of the cyk-means is lower than the other methods. Conversely, in almost all cases, the performance of the fixed cyk-means is the best. However, the difference in the performance between the fixed cyk-means, the k-means, and the kernel k-means is not large.Table 3
Comparison of performances of the four methods using the iris dataset.
Attributes
cyk-means
Fixed cyk-means
k-means
Kernelk-means
Sepal length, sepal width, petal length
0.5543
0.6961
0.6569
0.6614
Sepal width, petal length, petal width
0.5627
0.7900
0.7462
0.7590
Petal length, petal width, sepal length
0.4179
0.7114
0.7302
0.7359
Petal width, sepal length, sepal width
0.5171
0.6121
0.6104
0.6099
ARI are the mean of 200 runs with random initial values. The best estimations are bold. “Attributes” indicates three attributes used in clustering.Table4 shows the ARI scores of the cyk-means, the fixed cyk-means, and the k-mean for seven images in the segmentation benchmark dataset. The parameters of the fixed cyk-means are κ=15, σr=0.1, and σz=0.1. To evaluate the performances of the cyk-means and the fixed cyk-means, we convert images from RGB color to HSV color. When we cluster the dataset by the k-means, we use images represented by RGB color and HSV color. In this experiment, we compare a clustering result with a ground truth using the ARI score. We set the number of clusters K to the number of segments in a ground truth. In all cases, the fixed cyk-means stably shows good performance. The cyk-means indicates much better or worse performances than the other methods. In other words, the cyk-means shows unstable performance. This instability will be caused by the cyk-means more easily trapping a local minimum because of more parameters.Table 4
Comparison of performances of the four methods using the segmentation benchmark dataset.
Number
cyk-means
Fixed cyk-means
k-means (HSV)
k-means (RGB)
12003 (K=4)
0.6397
0.3744
0.3695
0.2277
69020 (K=2)
0.1611
0.5247
0.07680
0.1406
80099 (K=2)
0.9205
0.7960
0.6544
0.04890
103029 (K=3)
0.4697
0.5934
0.1794
0.09143
106047 (K=2)
0.3210
0.2988
0.04155
0.02332
310007 (K=7)
0.1548
0.3338
0.3075
0.3396
353013 (K=4)
0.6125
0.5993
0.5020
0.4683
ARI are the mean of 200 runs with random initial values. The best estimations are bold. “Number” indicates the number of the image. “k-means (HSV)” and “k-means (RGB)” indicate that we cluster HSV and RGB color images by the k-means, respectively.


## 4.3. Application to Color Image Quantization

We apply the cyk-means and the fixed cyk-means to color image quantization and compare the results to those using thek-means. We convert images quantized by the proposed methods from RGB color space to HSV color space before quantization, whereas an image processed by the k-means is represented using RGB. Figure 3 contains the four test images from the Berkeley segmentation database [26] and their quantization results. The original color images have sizes of 481×321 or 321×481 and are used as the test images to quantize into three colors. These quantization results are generated by the cyk-means, the fixed cyk-means with κ=25, σr=0.1, and σz=0.1, and the k-means. The color of a pixel in the quantized image represents the value of the centroid of the cluster that contains the pixel.Figure 3
Quantization results. The first column contains the original images. The second, third, and fourth columns contain the quantization results generated by the cyk-means, the fixed cyk-means, and thek-means, respectively. All original images are clustered with K=3.For image 118035 in Figure3, the colors of the background, the wall, and the roof are obviously different from each other. The cyk-means and the fixed cyk-means successfully segment this image, whereas the k-means extracts the shade from the wall and can not merge the wall to one color. Furthermore, the quantization results using the cyk-means and the fixed cyk-means are very similar.Image 26098 consists of red and green peppers on a display table. The cyk-means merges the red peppers and the planks of the display table and divides the dark area into two colors. The fixed cyk-means successfully extracts the red peppers. Thek-means assigns red to the planks and part of the green peppers.Image 299091 consists of some sky with cloud, an ocher pyramid, and ocher ground. The cyk-means groups the ocher pyramid and white cloud into the same color, whereas the fixed cyk-means correctly segments the pyramid and the sky. Thek-means is unsuccessful; it divides the pyramid into three regions (an ocher region, a highlight region, and a shade region).The cyk-means did not perform well for image 295087. It segments the image into two colors even though we set the number of clusters to three. Thus, the cyk-means makes a dead unit. This is because the concentrate parameter and variances, respectively, become small and large if a distribution of data points is regarded to visually consist of a few clusters. Thus, a few clusters include all data points and dead units (empty clusters) appear, even if we fix the number of clusters to a large number. In contrast, the fixed cyk-means (which has fixed concentrate and variance values) appropriately partitions the ground and the blue and the deep blue regions of the sky. Thek-means extracts shaded regions from the ground; that is, it can not group the ground into one region.Furthermore, the initial parameters,κ and σs, of the fixed cyk-means can control the quantization results. Figure 4 shows the quantization results generated by the fixed cyk-means using the different parameters. The original image in Figure 4 consists of two objects: the red fish and the arms of an anemone. The fixed cyk-means with κ=25, σr=0.1, and σz=0.1 can not extract the red fish shown in the middle image of Figure 4. However, the fixed cyk-means with κ=50, σr=0.5, and σz=0.5 extracts the red fish in the left image of Figure 4. This is because a large κ and/or large variances relatively increase the cosine similarity term of (12), and consequently clustering is more focused on the hue element.Figure 4
Quantization results of the fixed cyk-means with different parameters. The left image is the original. The middle and the right images are quantized withK=3.In conclusion, the fixed cyk-means is a more suitable method for color image quantization than the cyk-means. The fixed cyk-means quantizes color images with respect to the hue. The quantization results of the fixed cyk-means differ from that generated byk-means. That is because the Euclidean metric cannot consider the hue.


## 5. Conclusion and Discussion

In this study, we develop the cyk-means and the fixed cyk-means methods, which are new clustering methods for data in cylindrical coordinates. We derive a new similarity for the cyk-means from a probability distribution that is the product of a von Mises distribution and two Gaussian distributions (see (4)), because the Euclidean distance cannot properly represent dissimilarities between data points on periodic axes. Our experiments demonstrate that the cyk-means and the fixed cyk-means can properly partition synthetic data in cylindrical coordinates. Furthermore, the experimental results using real world data show that the fixed cyk-means has equal or better performance than the k-means and the kernel k-means. In the final experiment, the proposed methods are applied to color image quantization and successfully quantize a color image with respect to the hue element.The experiments that partitioned synthetic data demonstrate the effectiveness of the cyk-means. In the first experimental results, the cyk-means produces good estimates of the parameters and clustering data. The results of the second experiment show that the cyk-means performs the best when clustering synthetic data. However, in the experiment using real world data we find that the cyk-means did not provide good clustering results. Furthermore, the results of the color image quantization suggest that the flexibility of the cyk-means often produces dead units or a small cluster containing few data points. Thus, the cyk-means may not be appropriate for actual applications.The fixed cyk-means will be an effective method for actual applications. The fixed cyk-means is stable and performs well when we apply it to clusterings of synthetic data, real world data, and color image quantization. Furthermore, the fixed cyk-means hardly makes dead units because the number of its parameters is smaller than the cyk-means. The fixed cyk-means requires less computational time than the cyk-means with similar results.In future work, we will improve the performance of the proposed methods. The proposed methods are exposed to the ill-initialization problem and/or the dead unit problem caused by an incorrect initialization, similar tok-means. The k-means++ method proposed by Athur and Vassilvitskii [27] solves the ill-initialization problem of k-means and improves the clustering performance by obtaining an initial set of cluster centers that is close to the optimal solution. The conscience mechanism improves the performance of competitive learning and clustering algorithms [28–30]. It inserts a bias into the competition process so that each unit can win the competition with equal probability. Xu et al. [31] proposed an algorithm based on competitive learning called rival penalized competitive learning [2, 32], which determines the appropriate number of clusters and solves the dead unit problem. The strategy of rival penalized competitive learning is to adapt the weights of the winning unit to the input and to unlearn the weights of the 2nd winner. By incorporating the approaches in these algorithms into the proposed methods, we will improve the performance and reduce the effect of the intrinsic problems.



---

*Source: 3696850-2017-09-27.xml*