/*
c:\users\ebata\dscan\dscan3.go
DBSCANアルゴリズムを実装し、3次元空間のデータ（x、y、t）をクラスタリングするシンプルなプログラムです。
このプログラムでは、各データポイントは3次元座標（x、y、t）で表され、距離の計算にはユークリッド距離を使用します。
DBSCANをk-meansの違いで説明します。
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）とk-meansは、クラスタリングアルゴリズムですが、そのアプローチや動作原理にはいくつかの違いがあります。
(1)クラスタリング方法:
- DBSCAN: 密度ベースのクラスタリングアルゴリズムであり、データポイントの密度に基づいてクラスタを形成します。各点は、一定の距離（ε、epsilon）内に最小限の近傍点数（minPts）が存在する場合、その点を中心としたクラスタが形成されます。
- k-means: 距離ベースのクラスタリングアルゴリズムであり、データポイントの距離に基づいてクラスタを形成します。クラスタの数（k）を事前に指定し、各点を最も近いセントロイド（クラスタの中心）に割り当てます。
(2)クラスタの形状:
- DBSCAN: クラスタの形状は任意であり、密度の高い領域に基づいて形成されます。したがって、DBSCANは非凸形状のクラスタを処理できます。
- k-means: クラスタの形状は円形（球形）であり、各クラスタのセントロイドからの距離に基づいて決定されます。したがって、k-meansは凸形状のクラスタを前提としています。
(3)ハイパーパラメータ:
- DBSCAN: ε（epsilon）とminPtsの2つのハイパーパラメータを必要とします。εは近傍点の距離の閾値を定義し、minPtsはクラスタと見なすための最小の近傍点数を指定します
- k-means: クラスタの数（k）を指定する必要があります。
(4)ノイズの処理:
- DBSCAN: ノイズポイントを自動的に検出し、外れ値として扱います。密度が低い領域に存在するポイントは、任意のクラスタに割り当てられず、ノイズとして扱われます。
-k-means: 外れ値やノイズの処理を明示的に行いません。各点は必ずどれかのクラスタに割り当てられます。
要するに、DBSCANは密度ベースのアルゴリズムであり、任意の形状のクラスタを検出し、ノイズを処理する能力があります。一方、k-meansは距離ベースのアルゴリズムであり、クラスタの形状が円形であることを前提としています。
*/
package main
import (
"fmt"
"math"
)
// Point represents a 3D point with coordinates x, y, and t
type Point struct {
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[Point]bool)
for _, point := range points {
if visited[point] {
continue
}
visited[point] = 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[Point]bool, point Point, neighbours []Point, epsilon float64, minPts int) {
*cluster = append(*cluster, point)
for _, neighbour := range neighbours {
if !visited[neighbour] {
visited[neighbour] = true
neighbourNeighbours := getNeighbours(points, neighbour, epsilon)
if len(neighbourNeighbours) >= minPts {
expandCluster(cluster, points, visited, neighbour, neighbourNeighbours, epsilon, minPts)
}
}
// Add neighbour to cluster if not already in another cluster
var isInCluster bool
for _, c := range *cluster {
if c == neighbour {
isInCluster = true
break
}
}
if !isInCluster {
*cluster = append(*cluster, neighbour)
}
}
}
func main() {
// Example usage
points := []Point{
{X: 1, Y: 2, T: 0},
{X: 1.5, Y: 1.8, T: 1},
{X: 5, Y: 8, T: 2},
{X: 8, Y: 8, T: 3},
{X: 1, Y: 0.6, T: 4},
{X: 9, Y: 11, T: 5},
{X: 8, Y: 2, T: 6},
{X: 10, Y: 2, T: 7},
{X: 9, Y: 3, T: 8},
}
epsilon := 3.0
minPts := 2
clusters := DBSCAN(points, epsilon, minPts)
for i, cluster := range clusters {
fmt.Printf("Cluster %d:\n", i+1)
for _, point := range cluster.Points {
fmt.Printf(" (%.2f, %.2f, %.2f)\n", point.X, point.Y, point.T)
}
}
}