关于机器学习：映射应用程序的聚类算法

Clustering Algorithm for Mapping Application

我正在寻找地图上的聚类点(纬度/经度)。是否有关于快速且可扩展的合适算法的建议？

更具体地说，我有一系列的纬度/经度坐标和一个地图视口。我正在尝试将靠近的点聚在一起以消除混乱。

我已经有解决问题的方法(请参阅此处)，只是我想知道是否有任何形式的算法可以有效地解决问题。

对于虚拟地球应用程序，我使用了以下描述的群集
这里。闪电般快速且易于扩展。

Google Maps Hacks上有一个" \\ Hack69。高缩放级别的群集标记"。

此外，有关群集算法，请参见Wikipedia。

您可以考虑使用QuadTile方案为所有点编制索引，然后根据比例将四叉形拆分的范围进一步缩小。然后，索引中所有位置相似的点将彼此靠近，从而可以有效地进行聚类。

QuadTiles是莫顿密码的一个示例，该Wikipedia文章中链接了一个python示例，可能会有所帮助。

我查看了各种库，发现它们太复杂了，无法理解一个单词，所以我决定制定自己的聚类算法

这是我用Java语言编写的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static int OFFSET = 268435456;
static double RADIUS = 85445659.4471;
static double pi = 3.1444;

public static double lonToX(double lon) {
return Math.round(OFFSET + RADIUS * lon * pi / 180);
}

public static double latToY(double lat) {
return Math.round(OFFSET
- RADIUS
* Math.log((1 + Math.sin(lat * pi / 180))
/ (1 - Math.sin(lat * pi / 180))) / 2);
}

//这将计算特定缩放级别下两个长点之间的像素距离

1
2
3
4
5
6
7
8
9
10
11

public static int pixelDistance(double lat1, double lon1, double lat2,
double lon2, int zoom) {
double x1 = lonToX(lon1);
double y1 = latToY(lat1);

double x2 = lonToX(lon2);
double y2 = latToY(lat2);

return (int) (Math
.sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2))) >> (21 - zoom);
}

//实际计算聚类的主要功能
1.将纬度长点的ArrayList迭代为length。
2.内部循环从i 1位置迭代同一arraylist的副本，即保留顶部循环的索引
3.将第0个元素作为质心，并比较所有其他点(如果它们的像素距离很小)将其添加到群集中
4.从顶部数组列表中删除所有元素，并复制已形成集群的数组列表
5通过从0重新初始化索引来重新启动过程；
6如果选择的质心没有聚类，则不会删除该元素

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228

static ArrayList<Cluster> cluster(ArrayList<Marker> markers, int zoom) {

ArrayList<Cluster> clusterList = new ArrayList<Cluster>();

ArrayList<Marker> originalListCopy = new ArrayList<Marker>();

for (Marker marker : markers) {
originalListCopy.add(marker);
}

/* Loop until all markers have been compared. */
for (int i = 0; i < originalListCopy.size();) {

/* Compare against all markers which are left. */

ArrayList<Marker> markerList = new ArrayList<Marker>();
for (int j = i + 1; j < markers.size();) {
int pixelDistance = pixelDistance(markers.get(i).getLatitude(),
markers.get(i).getLongitude(), markers.get(j)
.getLatitude(), markers.get(j).getLongitude(),
zoom);

if (pixelDistance < 40) {

markerList.add(markers.get(i));
markerList.add(markers.get(j));

markers.remove(j);

originalListCopy.remove(j);
j = i + 1;
} else {
j++;
}

}

if (markerList.size() > 0) {
Cluster cluster = new Cluster(clusterList.size(), markerList,
markerList.size() + 1, originalListCopy.get(i)
.getLatitude(), originalListCopy.get(i)
.getLongitude());
clusterList.add(cluster);
originalListCopy.remove(i);
markers.remove(i);
i = 0;

} else {
i++;
}

/* If a marker has been added to cluster, add also the one */
/* we were comparing to and remove the original from array. */

}
return clusterList;
}

Just pass in your array list here containing latitude and longitude

then to display clusters
here goes the function

@Override
public void onTaskCompleted(ArrayList<FlatDetails> flatDetailsList) {

LatLngBounds.Builder builder = new LatLngBounds.Builder();

originalListCopy = new ArrayList<FlatDetails>();
ArrayList<Marker> markersList = new ArrayList<Marker>();
for (FlatDetails detailList : flatDetailsList) {

markersList.add(new Marker(detailList.getLatitude(), detailList
.getLongitude(), detailList.getApartmentTypeString()));

originalListCopy.add(detailList);

builder.include(new LatLng(detailList.getLatitude(), detailList
.getLongitude()));

}

LatLngBounds bounds = builder.build();
int padding = 0; // offset from edges of the map in pixels
CameraUpdate cu = CameraUpdateFactory.newLatLngBounds(bounds, padding);

googleMap.moveCamera(cu);

ArrayList<Cluster> clusterList = Utils.cluster(markersList,
(int) googleMap.getCameraPosition().zoom);

// Removes all markers, overlays, and polylines from the map.
googleMap.clear();

// Zoom in, animating the camera.
googleMap.animateCamera(CameraUpdateFactory.zoomTo(previousZoomLevel),
2000, null);

CircleOptions circleOptions = new CircleOptions().center(point) //
// setcenter
.radius(3000) // set radius in meters
.fillColor(Color.TRANSPARENT) // default
.strokeColor(Color.BLUE).strokeWidth(5);

googleMap.addCircle(circleOptions);

for (Marker detail : markersList) {

if (detail.getBhkTypeString().equalsIgnoreCase("1 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk1)));
} else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk_2)));

}

else if (detail.getBhkTypeString().equalsIgnoreCase("3 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk_3)));

} else if (detail.getBhkTypeString().equalsIgnoreCase("2.5 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk2)));

} else if (detail.getBhkTypeString().equalsIgnoreCase("4 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk_4)));

} else if (detail.getBhkTypeString().equalsIgnoreCase("5 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk5)));

} else if (detail.getBhkTypeString().equalsIgnoreCase("5+ BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk_5)));

}

else if (detail.getBhkTypeString().equalsIgnoreCase("2 BHK")) {
googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(detail.getLatitude(), detail
.getLongitude()))
.snippet(String.valueOf(""))
.title("Flat" + flatDetailsList.indexOf(detail))
.icon(BitmapDescriptorFactory
.fromResource(R.drawable.bhk_2)));

}
}

for (Cluster cluster : clusterList) {

BitmapFactory.Options options = new BitmapFactory.Options();
options.inMutable = true;
options.inPurgeable = true;
Bitmap bitmap = BitmapFactory.decodeResource(getResources(),
R.drawable.cluster_marker, options);

Canvas canvas = new Canvas(bitmap);

Paint paint = new Paint();
paint.setColor(getResources().getColor(R.color.white));
paint.setTextSize(30);

canvas.drawText(String.valueOf(cluster.getMarkerList().size()), 10,
40, paint);

googleMap.addMarker(new MarkerOptions()
.position(
new LatLng(cluster.getClusterLatitude(), cluster
.getClusterLongitude()))
.snippet(String.valueOf(cluster.getMarkerList().size()))
.title("Cluster")
.icon(BitmapDescriptorFactory.fromBitmap(bitmap)));

}

}

ANY QUESTIONS OR DOUBTS PLEASE ASK WILL CLEAR THEM ALL ...........THANKS