Phase 1: Grouping of symmetric clusters.

Spectral clustering is extended to find clusters consisting of two symmetric clusters at a time. Consider the distance measure

$$d(\textbf{x}[i],\textbf{x}[j]) = \min \left( \left\vert \textbf{... ...ert^2, \left\vert \textbf{x}^{+}[i] - \textbf{x}^{-}[j] \right\vert^2 \right),$$ (7)

where $\textbf{x}^{-}[j] = [-\textbf{x}[j]^T, t[j]^T ]^T$ is the point symmetric to $\textbf{x}^{+}[j]$ . As can be seen, this measure is small in two cases: Firstly for points that are very close to each other, and secondly for points that are very close to opposite of each other. If the the modified Gaussian kernel (4) is used with this distance measure for spectral clustering, neighboring points as well as opposite points will be grouped together, leading to $2^{N_t-1}$ clusters. This first phase avoids the incorrect clustering that might occur when some of the threads have a low number of data points, by combining the information of symmetric threads.