# A Geo-Clustering Approach for the Detection of Areas-of-Interest and Their Underlying Semantics +
## 3 Proposed Methodology
### Geo-Clustering Algorithm
#### 3.1.1 Notation and Definitions  
Given an area, the first step is to divide it into sub-regions. To this goal, many approaches have been proposed in the literature, however it still remains an open challenge, since none could guarantee an optimal solution. When equality of tiles is necessary, overlapping regions may be used (e.g., as in our previous work [36]), or alternatively, simpler, square grid-based regions (e.g., as in [37]). Although overlapping regions have a few advantages, e.g., closely geo-tagged photos belong to the same geo-cluster, this would imply that overlapped tiles would share descriptions (tags). This is not a desired property in the context of this work. Thus, herein we adopt a simpler square grid-based approach, since we focus on the description and merging of sub-regions. We empirically set, each side of a tile to an fixed width, \(W_{R}\).  
Now, let \(R\) denote a given region containing a set of photos \(P\). Let also \(R_{i,j}\) denote a given tile, containing a set of photos \(P_{i,j}\), thus \(\bigcup_{R}P_{i,j}=P\). Moreover, let \(T_{i,j}\) denote a set of tags, containing all tags from photos in \(P_{i,j}\) and a subset \(D_{i,j}\) of \(T_{i,j}\), which constitutes the tag-based region description.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Definition** \\ \hline \(R\) & The whole area which is given as input to the proposed algorithm \\ \(P\) & The set of photos that have been geo-tagged within \(R\) \\ \(i,j\) & The \(i\)-th row and the \(j\)-th column of the square grid \\ \(R_{i,j}\) & A square tile upon the initial division of \(R\) \\ \(W_{R}\) & The size of each tile \(R_{i,j}\) \\ \(P_{i,j}\) & The set of photos that have been geo-tagged within \(P_{i,j}\) \\ \(T_{i,j}\) & The set of tags harvested from \(P_{i,j}\) \\ \(N_{i,j}\) & The set of neighboring tiles of tile \(R_{i,j}\) \\ \(R_{i,j}^{\text{obs}}\) & A neighbor of \(R_{i,j}\) pos \(\in\) \(\{\)up, down, left, right\(\}\) denotes its position. \\ \(D_{i,j}\) & Semantic representation of tile \(R_{i,j}\) \\ \(D_{i,j}^{L}\) & Semantic representation of tile \(R_{i,j}\), using the \(L\) most popular tags \\ \(J(A,B)\) & Jaccard distance between sets \(A\) and \(B\) \\ \(S\) & Similarity threshold for two sets to be merged \\ \(\text{tf}_{t,d}\) & The frequency of a specific word \(t\) within a document \(d\) \\ \(\text{id}t_{t}\) & The overall number of documents in a collection that contain word \(t\) \\ \(C_{p}\) & Set of geo-clusters resulted upon a run with \(p\) parameter set \\ \(C_{i,p}\) & The \(i\)-th geo-cluster of \(C_{p}\) \\ \(P_{i,p}\) & Set of photos within the \(i\)-th geo-cluster of \(C_{p}\) \\ \(T_{i,p}\) & Set of tags within the photos in \(i\)-th geo-cluster of \(C_{p}\) \\ \(T_{i,p}\) & Ranked set of tags within the photos in \(i\)-th geo-cluster of \(C_{p}\) \\ \(T_{P}\) & Set of tags within \(P\) \\ \(t_{i,p}\) & A tag within \(T_{i,p}\) \\ \(t_{P}\) & A tag within \(T_{P}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Symbols used throughout this paper and their description.  
In the aforementioned grid, \(i\) and \(j\) denote the corresponding line and column of the grid, where \(R_{i,j}\) is placed.  
Since we have adopted a square grid, the most intuitive approach to define the set of the initial neighboring tiles is to use 4-connectivity. This way, let \(N_{i,j}\in\{R_{i,j}^{\text{up}},R_{i,j}^{\text{right}},R_{i,j}^{\text{down}},R _{i,j}^{\text{left}}\}\). Obviously:  
* \(R_{i,j}^{\text{up}}=R_{i-1,j}\)
* \(R_{i,j}^{\text{right}}=R_{i,j+1}\)
* \(R_{i,j}^{\text{down}}=R_{i+1,j}\)
* \(R_{i,j}^{\text{left}}=R_{i,j-1}\)  
Of course, when two tiles are merged, the set of neighbors of the resulting sub-region is the intersection of neighbors of the initial tiles.