# Data Reduction in the String Space for Efficient kNN Classification Through Space Partitioning
## 3 Reduction Through Homogeneous Clusters in the String Space  
The Reduction through Homogeneous Clusters algorithm proposed by [PERSON] and [PERSON] [17] stands out as one of the most recent proposals for PG based on a space partitioning premise for feature data. This method basically works in two different phases:  
1. The partitioning phase in which the space is divided into a set of regions comprising one or more prototypes each one. These regions are obtained by means of applying a clustering process to the initial data until reaching a class homogeneity, i.e., the prototypes associated to a region share the same class. This process is typically carried out using a k-means process [1].
2. For each of those class-homogeneous clusters, a new single is derived as a combination of the prototypes associated to the cluster. Typically, this process is conducted by a feature-wise mean or median operation.  
As commented, one of the main contributions of this work is the adaptation of the RHC algorithm to the case of structural representations, and more precisely to string data, which is now presented. Note that several considerations must be taken into account due to the particularity of the data representation, since the original algorithm is only designed for processing statistical data.  
Let us denote initial set of instances \(\mathcal{T}=\left\{\left(x_{i},y_{i}\right)\right\}_{i=1}^{|\mathcal{T}|}\) where \(x_{i}\) represents the \(i\)-th prototype from a given structural space \(\mathcal{X}\) and \(y_{i}\) stands for its associated label belonging to the set of possible categories \(\mathcal{Y}\). Let us also denote \(\zeta\left(\cdot\right)\) as the function that retrieves the class associated to instance \(x_{i}\), i.e., \(\zeta\left(x_{i}\right)=y_{i}\in\mathcal{Y}\). Finally, consider \(d\left(\cdot\right)\) as a dissimilarity measure in space \(\mathcal{X}\). The string-based RHC algorithm retrieves a reduced version \(\mathcal{R}\) out of the initial set \(\mathcal{T}\) using Algorithm 1.  
```
1:functionRHC(\(\mathcal{T}\))\(\triangleright\) Initial set \(\mathcal{T}=t_{1}\dots t_{|\mathcal{T}|}\)
2:\(\mathcal{R}\), \(\mathcal{C}\leftarrow\emptyset\)
3:for each\(y\in\mathcal{Y}\)do
4:\(\mathcal{V}\leftarrow\left\{t_{i}\in\mathcal{T}\quad:\quad\zeta(t_{i})=y\right\}\)\(\triangleright\) Class-homogeneous grouping
5:\(\mathcal{C}\leftarrow\mathcal{C}\,\cup\) set-median \(\left(\mathcal{V}\right)\)
6:endfor
7:for each\(c\in\mathcal{C}\)do
8:\(\mathcal{S}\leftarrow\left\{t_{i}\in\mathcal{T}\quad:\quad c=\arg\min_{c^{ \prime}\in\mathcal{C}}\,d\left(t_{i},c^{\prime}\right)\right\}\)\(\triangleright\)\(\mathcal{S}\): Set of prototypes in cluster \(c\)
9:if\(\mid\left\{\xi\left(t_{i}\right)\quad:\quad t_{i}\in\mathcal{S}\right\}\mid>1\)then\(\triangleright\) Cluster homogeneity as set cardinality
10:\(\mathcal{R}\leftarrow\mathcal{R}\,\cup\) RHC \(\left(\mathcal{S}\right)\)\(\triangleright\) Non-homogeneous cluster
11:else
12:\(\mathcal{R}\leftarrow\mathcal{R}\,\cup\) set-median \(\left(\mathcal{S}\right)\)\(\triangleright\) Homogeneous cluster
13:endif
14:endfor
15:return\(\mathcal{R}\)\(\triangleright\) Reduced set \(\mathcal{R}=r_{1}\dots r_{|\mathcal{R}|}\)
16:endfunction
```  
**Algorithm 1** Reduction through Homogeneous Clusters.  
The main consideration in this design is the actual computation of the median string. As it has been introduced, the retrieval of the exact median value of a set of strings is known to be a NP-hard problem [18]. Thus, in this case we consider the set-median operation due to its lower complexity. This process is the one denoted as set-median \(\left(\cdot\right)\) in Algorithm 1 and is obtained following Equation (1).  
\[\text{set-median}\left(\mathcal{S}\right)=\arg\min_{s\in\mathcal{S}}\sum_{s^{ \prime}\in\mathcal{S}}d\left(s,s^{\prime}\right) \tag{1}\]  
where \(d\left(\cdot\right)\) denotes the dissimilarity measure previously defined and \(\mathcal{S}\) is the set of prototypes contained in a particular cluster.