3次元を取り扱うDBSCANプログラム
このプログラムでは、同一座標は1つの座標として纏められてしまって、異なるユーザの座標として取り扱ってくれません。
これに対応するために修正したプログラムは以下の通りです。
// ~/tomioka_school/src/trip_school/dbscan_3d_2.go
package main
import (
"fmt"
"math"
)
// Point represents a 3D point with coordinates x, y, and t
type Point struct {
User string
X, Y, T float64
}
// DistanceTo calculates the Euclidean distance between two 3D points
func (p Point) DistanceTo(other Point) float64 {
dx := p.X - other.X
dy := p.Y - other.Y
dt := p.T - other.T
return math.Sqrt(dx*dx + dy*dy + dt*dt)
}
// Cluster represents a cluster of points
type Cluster struct {
Points []Point
}
// DBSCAN performs density-based clustering of 3D points
func DBSCAN(points []Point, epsilon float64, minPts int) []Cluster {
var clusters []Cluster
var visited = make(map[string]bool)
for _, point := range points {
pointKey := fmt.Sprintf("%s,%f,%f,%f", point.User, point.X, point.Y, point.T)
if visited[pointKey] {
continue
}
visited[pointKey] = true
neighbours := getNeighbours(points, point, epsilon)
if len(neighbours) < minPts {
continue
}
var clusterPoints []Point
expandCluster(&clusterPoints, points, visited, point, neighbours, epsilon, minPts)
clusters = append(clusters, Cluster{Points: clusterPoints})
}
return clusters
}
// getNeighbours returns all points within distance epsilon of the given point
func getNeighbours(points []Point, point Point, epsilon float64) []Point {
var neighbours []Point
for _, other := range points {
if point.DistanceTo(other) <= epsilon {
neighbours = append(neighbours, other)
}
}
return neighbours
}
// expandCluster expands the cluster from the given point
func expandCluster(cluster *[]Point, points []Point, visited map[string]bool, point Point, neighbours []Point, epsilon float64, minPts int) {
*cluster = append(*cluster, point)
for _, neighbour := range neighbours {
neighbourKey := fmt.Sprintf("%s,%f,%f,%f", neighbour.User, neighbour.X, neighbour.Y, neighbour.T)
if !visited[neighbourKey] {
visited[neighbourKey] = true
neighbourNeighbours := getNeighbours(points, neighbour, epsilon)
if len(neighbourNeighbours) >= minPts {
expandCluster(cluster, points, visited, neighbour, neighbourNeighbours, epsilon, minPts)
}
}
}
}
func main() {
points := []Point{
{"A", 1, 2, 0},
{"A", 1.5, 1.8, 1},
{"A", 5, 8, 2},
{"A", 8, 8, 3},
{"A", 1, 0.6, 4},
{"A", 9, 11, 5},
{"A", 8, 2, 6},
{"A", 10, 2, 7},
{"A", 9, 3, 8},
{"B", 1, 2, 0},
{"B", 1.5, 1.8, 1},
{"B", 5, 8, 2},
{"B", 8, 8, 3},
{"B", 1, 0.6, 4},
{"B", 9, 11, 5},
{"B", 8, 2, 6},
{"B", 10, 2, 7},
{"B", 9, 3, 8},
{"C", 1, 2, 0},
{"C", 1.5, 1.8, 1},
{"C", 5, 8, 2},
{"C", 8, 8, 3},
{"C", 1, 0.6, 4},
{"C", 9, 11, 5},
{"C", 8, 2, 6},
{"C", 10, 2, 7},
{"C", 9, 3, 8},
}
// epsilon := 3.0
// minPts := 5
epsilon := 2.5
minPts := 5
clusters := DBSCAN(points, epsilon, minPts)
fmt.Println("Combined Clusters:")
for i, cluster := range clusters {
fmt.Printf("Cluster %d:\n", i+1)
for _, point := range cluster.Points {
fmt.Printf(" (%s, %.2f, %.2f, %.2f)\n", point.User, point.X, point.Y, point.T)
}
}
}
出力結果は以下の通りです。
C:\Users\ebata\tomioka_school\src\trip_school>go run dbscan_3d_2.go
Combined Clusters:
Cluster 1:
(A, 1.00, 2.00, 0.00)
(A, 1.50, 1.80, 1.00)
(B, 1.00, 2.00, 0.00)
(B, 1.50, 1.80, 1.00)
(C, 1.00, 2.00, 0.00)
(C, 1.50, 1.80, 1.00)
Cluster 2:
(A, 8.00, 2.00, 6.00)
(A, 10.00, 2.00, 7.00)
(A, 9.00, 3.00, 8.00)
(B, 8.00, 2.00, 6.00)
(B, 10.00, 2.00, 7.00)
(B, 9.00, 3.00, 8.00)
(C, 8.00, 2.00, 6.00)
(C, 10.00, 2.00, 7.00)
(C, 9.00, 3.00, 8.00)
