# Spherical Tree-Structured SOM and Its Application to Hierarchical Clustering
## 2 Materials and Methods  
### Related Work  
First, we describe a SOM and other methods used for data visualization. A SOM is a type of artificial neural network proposed by [PERSON]. It maps high-dimensional data onto a low-dimensional map and expresses the similarity of the data using distance. On the map, similar data are placed close to each other, and dissimilar data are placed far from each other. This characteristic enables the SOM to be used for data visualization. By visualizing the data, humans can intuitively grasp the relationships among the data in a high-dimensional space. WeBSOM is an example of an application that is used as a tool for data visualization. WeBSOM makes it easy to search for documents that are similar to a query document by arranging many documents onto a two-dimensional map according to similarity [4]. We describe the SOM algorithm as follows: Figure 1 shows the structure of the SOM. It has nodes \(m_{i}(i=1,\ldots I)\) with reference vector \(m_{i}\). First, each reference vector is initialized with a random value. In the SOM, the node with the reference vector that is closest to the input vector \(x_{j}(j=1,\ldots J)\) that was selected from the input set is determined to be the winner node \(m_{c}\). After the winner node is determined, the reference vectors of the winner node and its neighborhood nodes are updated so that they are closer to the value of the input vector using the following formula:  
\[m_{i}(t+1)=m_{i}(t)+h_{ci}\left[x_{j}(t)-m_{i}(t)\right] \tag{1}\]  
\[h_{ci}(t)=\alpha(t)\exp\left(-\frac{d_{ci}2}{2\sigma^{2}(t)}\right), \tag{2}\]  
where \(h_{ci}\) is a neighborhood function determined by the positions of winner node \(m_{c}\) and node \(m_{i}\), \(d_{ci}\) is the distance between the nodes \(m_{c}\) and \(m_{i}\) on the map, \(\alpha(t)\) is the learning rate, and \(\sigma(t)\) is a function that determines the size of the update area; \(\alpha(t)\) and \(\sigma(t)\) are set to decrease as the number of updates increases. By repeatedly determining the winner node and updating the reference vectors, the SOM is trained. The algorithm described above is a common technique called online learning. By contrast, batch learning that does not depend on the order of input has also been proposed [5]. In batch learning, after the winner node of all inputs is determined, the map is updated using the following formula:  
\[m_{i}(t+1)=\frac{\sum_{j=1}^{l}h_{cji}\,x_{j}}{\sum_{j=1}^{l}h_{cji}} \tag{3}\]  
\[h_{cji}\left(t\right)=\exp\left(-\frac{d_{cji}\,^{2}}{2\sigma^{2}(t)}\right). \tag{4}\]  
In addition to the SOM, principal component analysis (PCA) and t-distributed stochastic neighbor embedding (t-SNE) are common dimensional reduction or compression methods [6; 7]. PCA searches for the axes with the large variances in the data and removes axes with small variances to reduce the dimensions. Note that PCA is based on the assumption that the magnitude of the variance represents the characteristics of the data. t-SNE regards the distance between data points as a probability and compresses the dimensions so that the distances between data points in the high- and low-dimensional spaces are the same. Here, we introduced PCA and t-SNE as typical methods. However, many other methods continue to be proposed [8; 9]. Similar to the SOM, PCA and t-SNE are mainly used for data visualization. The major difference between the SOM and other dimensional reduction or compression methods such as PCA and t-SNE is that the SOM uses nodes for learning. Therefore, using a SOM, we obtain not only the coordinates of the input data in the low-dimensional space but also the codebook vectors from the nodes. As mentioned in the Introduction, if the number of nodes in a SOM increases, the number of search nodes needed to determine the winner nodes increase, and the calculation time increases. Therefore, a tree-structured SOM (TS-SOM), which uses the tree search method in the SOM, was proposed [10].