-
Notifications
You must be signed in to change notification settings - Fork 0
/
Lection4.Rmd
173 lines (122 loc) · 6.6 KB
/
Lection4.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
---
editor_options:
markdown:
wrap: sentence
---
# Clustering algorithms in real life problems
[Lesson summary](https://glebpinigin.github.io/tiny_geoda_course/cheatsheets/Lesson 4.pdf)
## Clustering goals:
- Simplifying data processing
- Data compression
- Identification of anomalies (atypical objects)
- Building a hierarchy of objects
## Where was it used?
```{r fig.cap= "Pickpoints in taxi", echo = F, out.width = 600}
knitr::include_graphics("images/pickpoint_taxi.png")
```
```{r fig.cap= "Multy-scale clustering in gallery", echo = F, out.width = 600}
knitr::include_graphics("images/photo_cluster.png")
```
## Clustering issues:
- Fuzzy problem statement
- Variety of quality criteria
- Prevalence of heuristic approaches
- Unknown number of clusters
- Dependence of the result on the selected metric
## Most popular Clustering algorithms:
1. Statistical clustering
- K-mean
- ISODATA
- FOREL (formal elements)
2. Hierarchical/graph clustering
3. Density Clustering (DBSCAN/OPTICS)
## K-means method
1. Set the number of clusters K
2. Select randomly K points as cluster centers
3. Determine the nearest cluster center for each point
4. Calculate a new cluster center based on the coordinates of its points
5. Repeat steps 3-4 until the cluster centers stop changing their location.
```{r fig.cap= "Example with four clusters:", echo = F, out.width = 600}
knitr::include_graphics("images/K-means1.gif")
```
```{r fig.cap= "All points of the resulting clusters are located inside the cells of the Voronoi diagram for the centers of these clusters:", echo = F, out.width = 600}
knitr::include_graphics("images/K-means2.png")
```
```{r fig.cap= "The algorithm is good at identifying only spatially separated clusters of convex shape.:", echo = F, out.width = 600}
knitr::include_graphics("images/K-means3.png")
```
## ISODATA
Iterative Self-Organizing Data Analysis Technique Algorithm
The method starts with one cluster and performs a recursive division of the set along its longest axis until all intra-cluster distances are within a given tolerance.
The working algorithm is presented below:
```{r fig.cap= "ISODATA method", echo = F, out.width = 600}
knitr::include_graphics("images/ISODATA.gif")
```
ISODATA method compared to K-means:
1. It is not necessary to specify the number of clusters.
2. A more robust method for calculating the resulting clusters.
3. Also not effective in identifying irregularly shaped clusters.
## Hierarchical clustering
- It is recommended to use Ward's distance (red line at the picture)
- It makes sense to build several options and choose the best one
- The clustering level is obtained by pruning the tree at a given distance.
```{r fig.cap= "Hierarchical method", echo = F, out.width = 600}
knitr::include_graphics("images/Hierarchical clustering.png")
```
## DBSCAN
Advantages: 1.
The number of clusters is not required.
2.
Can find clusters of stable forms.
It may even find a cluster that is completely surrounded by, but not connected to, another cluster.
3.
Creates noise and is resistant to emissions.
4.
Only two parameters required
DISAdvantages: 1.
Not completely deterministic: edge points accessible from more than one cluster may be part of any cluster, depending on the order in which the data is processed.
2.
Cannot group data sets well where the clusters have different densities.
```{r fig.cap= "DBSCAN method", echo = F, out.width = 600}
knitr::include_graphics("images/DBSCAN1.gif")
```
```{r fig.cap= "DBSCAN method", echo = F, out.width = 600}
knitr::include_graphics("images/DBSCAN2.gif")
```
The described clustering methods are far from the only ones, but they are among the most popular.
The described clustering methods are far from the only ones, but they are among the most popular.
Next, we will look at how these methods are implemented in GEODA.
## GEODA interface
When opening the clustering tools in GeoDA, you can select the clustering method, and then the number of clusters, selection distances, the minimum number of points in the class, etc.
```{r fig.cap= "1 - button with clustering tools, 2 - clustering methods? 3 - window with option of clustering", echo = F, out.width = 600}
knitr::include_graphics("images/Interface_clust.png")
```
## What Data should I use for clustering?
Clustering can occur on the basis of attribute data, spatial data and their joint significance.
At the same time, we can combine attributive and spatial data both in equal importance and giving greater weight to one of the data categories.
```{r fig.cap= "Variants of how clusters look, depending on the choice of data on which clustering is based.", echo = F, out.width = 600}
knitr::include_graphics("images/DATA_TYPE.png")
```
*ATTENTION! Use projected coordinates. NOT geographic coordinates.This is necessary for correct calculation of distances. For example, UTM zone 31 N*
We suggest looking at the results of different clustering methods on test data.
Test Data Attributes (France, 18th century):
1. Used indicators for example:
2. Population per Crime against persons
3. Population per Crime against property.
4. Percent of military scripts who can read and write.
5. Donations to the poor.
6. Population per illegitimate birth.
7. Population per suicide.
```{r fig.cap= "1. K-Means, 2. K-Medoids, 3. Spectral, 4. Hierarchical", echo = F, out.width = 600}
knitr::include_graphics("images/clust_type.png")
```
**HOMETASK: Build a network of electric charging stations for cars in a small town**
Electric charging infrastructure is rapidly developing around the world. Imagine that in the small city of your choice there is not a single fast charger for cars. The cost of their construction is high, which means it is necessary to optimally place a small number of fast charging stations. According to the plan, one charging station will be installed per 10,000 people in the city.
Exercise:
1. Select a small city (50,000 to 100,000 people).
2. For each house, add a field with the number of apartments or number of residents.
3. Get centroids of residential buildings
4. Group a given set of points. The number of clusters must correspond to the population of the selected city (1 charging station = 1 cluster = 10,000 people).
5. Select the optimal location of charging stations, based on the fact that they should be close to the geometric center of the resulting clusters.
6. Justify the choice of clustering method for this task based on the lecture materials. Draw up a map(s) to justify the optimal location of charging stations, describe the characteristics of the resulting clusters.
Send maps and justification for the chosen clustering method to: vitaliy_mapgeo@mail.ru