군중에 대한 클러스터 분석

Question

많은 수의 사용자 (수십만)의 위치 데이터가 있습니다. 나는 현재 위치와 약간의 이력 데이터 포인트 (분 데이터가 1 ​​시간 뒤로 돌아 간다)를 저장한다.

생일 파티와 같은 자연스러운 이벤트에 모이는 군중을 어떻게 감지합니까? 심지어 더 작은 군중 (5 명부터 시작한다고 가정 해 봅시다)이 탐지되어야합니다. 알고리즘은 거의 실시간으로 (또는 적어도 1 분에 1 회) 작동하여 군중이 발생할 때이를 탐지해야합니다.

많은 클러스터 분석 알고리즘을 살펴 보았지만 대부분은 나쁜 선택처럼 보입니다. 그들은 너무 오래 걸리고 (나는 O (n^3)과 O (2^n)을 보았거나) 얼마나 많은 클러스터가 미리 있는지 알아야합니다.

나를 도와 줄 사람이 있습니까? 고맙습니다!

Answer 1

각 사용자가 자신의 클러스터가되도록하십시오. 그녀가 다른 사용자에게 거리 R 이내에 도착하면 새로운 클러스터를 형성하고 사람이 떠날 때 다시 분리하십시오. 그들은 타이머 큰 T보다

파티가 움직이지 (대중 교통을 나타낼 수 있습니다)

에 같은 장소에

N

보다 사람들의

• 번호가 큰 : 때 이벤트가
• 은 그것은 공공 서비스 건물 (병원, 학교 등)
• (다른 조건을 잘 수)에 위치한 아니에요

1 분의 많은입니다 수십만 명의 사람들에게조차도 그것을 할 수있는 시간. 순진한 구현에서는 O (n^2)이지만 각 개인의 위치를 ​​비교하는 데는 아무런 포인트가 없으며 가까운 이웃에있는 사람들 만 비교할 수 있습니다. 첫 번째 근사값에서 "세계"를 섹터로 나눌 수 있으며, 이는 또한 작업을 병렬화하고 차례로 쉽게 확장 할 수있게합니다. 더 많은 사용자가 있습니까? 노드를 몇 개 더 추가하고 크기를 줄이십시오.

하나의 아이디어는 '질량'과 무게 중심의 관점에서 생각하는 것입니다. 무엇보다 먼저 질량이 예를 들어 질량보다 크지 않을 때까지 이벤트로 표시하지 마십시오. 15 대. 물론 위치는 부정확하지만 이벤트의 경우 이벤트의 중심을 기준으로 평균을 계산해야합니다. 만약 당신의 클러스터가 상당한 질량을 추가하지 않고 어떤 방향으로 성장한다면, 그것은 옳지 않을 것입니다. DBSCAN (밀도 기반 클러스터링)과 같은 방법을 살펴보면 제한된 활동이있을 때 이싱 모델 (여기에서는 온도의 관점에서 생각하고 군중에 합류하기 위해 누군가를 "뒤집기")을 적용하여 물리적 시스템에서도 좋은 영감을 얻을 수 있습니다.

의견에서 저자가 언급 한 "단일 연결 문제"를 피하려면 어떻게해야합니까? 하나의 아이디어는 '질량'과 무게 중심의 관점에서 생각하는 것입니다. 무엇보다 먼저 질량이 예를 들어 질량보다 크지 않을 때까지 이벤트로 표시하지 마십시오. 15 대. 물론 위치는 부정확하지만 이벤트의 경우 이벤트의 중심을 기준으로 평균을 계산해야합니다. 만약 당신의 클러스터가 상당한 질량을 추가하지 않고 어떤 방향으로 성장한다면, 그것은 옳지 않을 것입니다. DBSCAN (밀도 기반 클러스터링)과 같은 방법을 살펴보면 실제 시스템에서 좋은 영감을 얻을 수도 있고 심지어 이싱 모델 (여기에서는 온도의 관점에서 생각하고 군중에 합류하기 위해 누군가를 "뒤집기")을 수행 할 수도 있습니다. 그것은 새로운 문제가 아니며, (부분적으로) 그것을 다루는 논문이 있다고 확신합니다. Is There a Crowd? Experiences in Using Density-Based Clustering and Outlier Detection.

Answer 2

전체 클러스터링을 수행하는 데 거의 사용되지 않습니다.

그냥 좋은 데이터베이스 색인을 사용합니다.

현재 위치의 데이터베이스를 유지하십시오.

새로운 좌표를 얻을 때마다 원하는 반경, 즉 50 미터로 데이터베이스를 쿼리하십시오. A 좋은 색인은 작은 반경에 대해 O (log n)에서이를 수행합니다. 충분한 결과를 얻는다면 이것은 사건 일 수도 있고 진행중인 사건에 합류하는 사람 일 수도 있습니다.