異なるユーザを考慮した3次元を取り扱うDBSCANプログラム

2024年2月12日

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)