# A Geo-Clustering Approach for the Detection of Areas-of-Interest and Their Underlying Semantics +
## 3 Proposed Methodology
### Geo-Clustering Algorithm
#### 3.1.3 Region Merging  
One of the challenges when comparing two sets is to select an appropriate distance/similarity measure. Herein we use the Jaccard (Tanimoto) distance [38], which consists a well-known measure for comparing the similarity and diversity of sample sets. The Jaccard similarity \(J(A,B)\) between two sets \(A,B\) is given by  
\[J(A,B)=\frac{|A\cap B|}{|A\cup B|}=\frac{|A\cap B|}{|A|+|B|-|A\cap B|}\, \tag{1}\]  
where in our case \(A,B\) are the sets of tags that have been chosen to represent two tiles, e.g., using the methodology described in Section 3.2. Using the aforementioned notation, tiles \(R_{A},R_{B}\) with descriptions \(D_{A},D_{B}\) are merged when (a) they are neighbors and (b) \(J(D_{A}^{L},D_{B}^{L})>S\), where \(S\in[0,1]\) is a user-defined similarity threshold.  
The merging process begins from the tile \(R_{1,1}\), i.e., the one of the first row, first column and continues horizontally. The distance to all its neighbors is checked. It is merged with the tile whose similarity is the max among all those whose similarity is greater than \(S\), if any. For a new tile, its description is calculated based on the union of the sets of tags and the process continues by checking the similarities to its neighbors. In case there does not exist a neighbor with similarity greater than \(S\), the process continues with the next tile which has not been merged. A graphical example of the tile merging process is illustrated in Figure 2. The semantic geo-clustering process is presented in pseudocode in Algorithm 1, while we also present pseudocode for Jaccard similarity and the region merging process for the sake of clarity in Algorithms 2 and 3, respectively.  
```
Input: Set of tiles \(R\), set of Descriptions \(D\), Similarity threshold \(S\), Description length \(L\) Output: Final Set of merged regions \(R\)
1 FunctionSemantic_Geo_Clustering(\(R\), \(S\), \(L\)):
2 forall the \(R_{ij}\in R\)do
3 merge_flag \(\leftarrow\) TRUE
4 best_match_N \(\leftarrow\)\(\emptyset\)
5 best_match \(\gets\)\(S\)
6 whilemerge_flag = TRUEdo
7 forall the \(N\in N_{ij}\)do
8 if\(\text{Jaccard}\left(D_{1,j},D_{1,j}^{N},L\right)>S\)ANDJaccard(\(D_{1,j},D_{1,j}^{N},L\))\(>\)best_match then
9 best_match \(\leftarrow\)\(\text{Jaccard}\left(D_{1,j},D_{1,j}^{N},L\right)\)
10 best_match_N \(\leftarrow\)\(N_{ij}\)
11 end if
12
13 end if
14 if\(\text{best\_match\_N}\
eq\emptyset\)then
15\(R_{ij}\leftarrow\)\(\text{Merge}\left(R_{ij}\text{best\_match\_N}\right)\)
16 merge_flag\(\leftarrow\)TRUE
17
18 end if
19
20 end if
21
22 end if
```  
**Algorithm 1**Semantic Geo-Clustering  
```
Input: Tile Description \(D_{1}\), Tile Description \(D_{2}\), Tile Description Length \(L\) Output: Jaccard Similarity Measure \(J_{S}\) of Descriptions \(D_{1},D_{2}\)
1 Function\(\text{Jaccard}(D_{1},D_{1},L)\):
2\(D_{1}\leftarrow\)Sort(\(D_{1}\))//Sort tags based on number of users
3\(D_{1}\leftarrow\)\(\texttt{Trim}\left(D_{1},L\right)\)//Keep first \(L\) tags
4\(D_{2}\leftarrow\)Sort(\(D_{2}\))
5\(D_{2}\leftarrow\)Trim(\(D_{2},L\))
6\(J_{S}\leftarrow\left|D_{1}\cap D_{2}\right|/\left(\left|D_{1}\right|+\left|D_{2} \right|-\left|D_{1}\cap D_{2}\right|\right)\)return\(J_{S}\)
```  
**Algorithm 2**Jaccard Similarity  
Figure 2: Merging process of tiles: For a given tile (**a**), at a given step, one of its neighbors is considered as a candidate for merging (**b**). Their similarity is above the given threshold \(S\), thus they are merged (**c**). At another step, one neighbor of the new tile is considered as a candidate for merging (**d**). Their similarity is above \(S\), thus, they are merged (**e**).