왜 kmeans를 할 때마다 결과가 다르지?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| K-means 알고리즘에서 결과가 실행할 때마다 달라지는 주요 이유는 초기 중심(centroid)의 선택이 무작위이기 때문입니다. K-means 알고리즘의 과정은 다음과 같습니다:
초기 중심 선택: 먼저, 데이터 포인트 중에서 무작위로 K개의 포인트를 선택하여 초기 군집의 중심으로 설정합니다.
군집 할당: 각 데이터 포인트를 가장 가까운 중심에 할당하여 군집을 형성합니다.
중심 재계산: 할당된 군집에 기반하여 각 군집의 중심을 다시 계산합니다.
수렴 여부 판단: 군집의 할당이 변하지 않거나, 지정된 최대 반복 횟수에 도달하거나, 중심의 변화가 특정 임계값보다 작아질 때까지 2~3단계를 반복합니다.
이 과정에서 1단계인 초기 중심의 선택이 무작위로 이루어지기 때문에, 알고리즘이 시작할 때마다 다른 초기 중심점을 갖게 됩니다. 이는 궁극적으로 다른 군집 할당 결과와 최종 중심점을 초래할 수 있습니다. 특히 데이터가 여러 군집의 경계에 걸쳐 있거나 군집 간 분포가 명확하지 않을 경우 결과의 변동성이 더욱 두드러질 수 있습니다.
결과의 일관성을 개선하기 위한 몇 가지 방법은 다음과 같습니다:
초기 중심의 스마트한 선택: K-means++ 초기화 방법은 군집의 초기 중심을 보다 전략적으로 선택하여, 무작위 선택에 비해 더 좋은 성능과 일관된 결과를 얻을 수 있게 합니다.
여러 번 실행 및 최적 결과 선택: 알고리즘을 여러 번 실행하고, 가장 낮은 오류(또는 최적의 평가 지표)를 가진 결과를 최종 결과로 선택합니다.
고정된 랜덤 시드 사용: 결과의 재현성을 위해 무작위 선택 과정에 사용되는 랜덤 시드를 고정합니다. 이 방법은 동일한 초기 중심점을 재사용하여 실행할 때마다 일관된 결과를 얻을 수 있게 합니다.
이러한 방법들은 K-means 알고리즘의 결과에 대한 변동성을 줄이고, 더 안정적이고 예측 가능한 결과를 얻는 데 도움이 될 수 있습니다.
|
K-means++ 초기화 방법을 사용해서 스마트하게 초기 중심을 선택하게 해줘.
1
2
3
| K-means++ 초기화 방법은 초기 중심을 보다 스마트하게 선택하는 방식으로, 첫 번째 중심을 무작위로 선택한 후, 각 데이터 포인트에 대해 기존 중심들로부터의 거리를 기반으로 다음 중심을 확률적으로 선택합니다. 이 방법은 초기 중심들이 서로 멀리 떨어져 있게 하여, K-means의 결과의 품질을 향상시킵니다.
아래 코드는 K-means++ 초기화 방법을 적용한 _initializeCentroids 메서드의 구현 예시입니다. 이 예제는 KMeans 클래스 내에 있어야 하며, 기존의 무작위 중심 초기화 방법을 대체합니다.
|
(코드 생략)
1
2
3
4
5
6
| 이 코드는 다음 단계를 따릅니다:
데이터 세트에서 첫 번째 중심을 무작위로 선택합니다.
각 데이터 포인트에 대해, 이미 선택된 중심들 중 가장 가까운 중심까지의 거리를 계산합니다.
각 거리의 제곱에 비례하는 확률로 다음 중심을 선택합니다. 이는 더 먼 데이터 포인트가 다음 중심으로 선택될 확률을 높입니다.
이 방법은 초기 중심이 데이터 세트 내에서 균등하게 분포될 확률을 높여, k-means 알고리즘의 성능을 향상시키는 데 도움을 줍니다.
|
최대한 뭉치지 않고 골고루 평등하게 쪼개지기를 바란다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 데이터를 최대한 골고루 평등하게 쪼개기 위해서는 몇 가지 전략과 수정 사항을 K-means 알고리즘에 적용할 수 있습니다. 이러한 방법은 알고리즘의 기본 로직을 조정하여, 각 클러스터가 가능한 한 동일한 수의 데이터 포인트를 가지도록 유도합니다. 다음은 이를 달성하기 위한 몇 가지 접근 방법입니다:
1. K-means++의 개선된 초기화 사용
K-means++ 초기화 방법을 사용하여 시작하는 것은 좋은 출발점이지만, 클러스터의 크기 균형을 맞추는 데에는 직접적인 영향을 미치지 않습니다. 대신, 초기 중심을 설정할 때 각 데이터 포인트가 이전에 선택된 중심으로부터 가능한 한 멀리 떨어지도록 하여, 데이터 공간을 더 고르게 커버할 수 있도록 합니다.
2. 균형 잡힌 클러스터링을 위한 알고리즘 조정
K-means 알고리즘을 조정하여 각 클러스터가 비슷한 크기를 가지도록 강제할 수 있습니다. 이를 위해 클러스터 할당 단계에서 데이터 포인트를 가장 가까운 중심에 할당하는 대신, 클러스터 크기도 고려하는 방식을 적용할 수 있습니다. 예를 들어, 할당 시 클러스터의 현재 크기에 비례하여 가중치를 주어, 이미 많은 데이터 포인트를 가진 클러스터보다는 작은 클러스터에 새 데이터 포인트가 할당될 확률을 높일 수 있습니다.
3. 최대-최소 클러스터링(Max-Min Clustering)
이 방법은 각 단계에서 최대 거리 또는 최소 크기 기준을 사용하여 데이터 포인트를 클러스터에 할당합니다. 예를 들어, 가장 적은 수의 데이터 포인트를 가진 클러스터에 새로운 데이터 포인트를 우선적으로 할당할 수 있습니다. 이러한 방식은 클러스터 크기의 균형을 더욱 적극적으로 조정합니다.
4. 후처리를 통한 클러스터 균형 조정
클러스터링이 완료된 후, 클러스터의 크기를 분석하고 너무 크거나 작은 클러스터를 조정할 수 있습니다. 예를 들어, 가장 큰 클러스터에서 일부 데이터 포인트를 제거하고 이를 다른 클러스터에 재할당할 수 있습니다. 이 과정은 여러 번 반복하여 각 클러스터의 크기가 비슷해질 때까지 조정할 수 있습니다.
5. 사용자 정의 거리 메트릭
거리 계산에 클러스터 크기를 반영하는 사용자 정의 거리 메트릭을 도입할 수 있습니다. 이는 클러스터 크기가 클수록 해당 클러스터까지의 거리가 가상으로 더 멀게 계산되도록 해, 새로운 데이터 포인트가 큰 클러스터보다는 작은 클러스터에 할당될 가능성을 높입니다.
적용 예시
위의 전략을 K-means 알고리즘에 적용하기 위해서는 알고리즘의 핵심 로직을 수정해야 합니다. 예를 들어, 클러스터 할당 로직에 클러스터 크기에 따른 가중치를 추가하거나, 클러스터링 후 최종 클러스터 크기를 조정하는 후처리 단계를 구현할 수 있습니다. 이러한 수정은 표준 K-means 알고리즘을 사용하는 대신, 클러스터링 프로세스를 더 세밀하게 제어할 수 있게 해주며, 데이터 포인트를 더 균등하게 분배하고자 할 때 유용합니다.
|
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
| Future runKMeansClustering(
List points,
int numClusters,
DistanceCalculator calculator,
int dataIndex) async {
// Initialize data based on T and dataIndex
List> data = points
.where((point) => point.data[dataIndex] is T) // Ensure the data matches the type T
.map((point) => [point.data[dataIndex] as T])
.toList();
if (data.isEmpty) {
print("No data points of type ${T.toString()} found.");
return;
}
final kmeans = KMeans(numClusters, calculator, data);
kmeans.run();
// Mapping cluster results back to MultiTypePoints
for (int i = 0; i < points.length; i++) {
points[i].updateFinalClusterIdStep2((kmeans.labels[i]));
}
}
|
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
| class KMeans {
final int k;
List> centroids = [];
List> data;
final DistanceCalculator calculator;
List labels = []; // To store the cluster label for each data point
KMeans(this.k, this.calculator, this.data);
void run() {
_initializeCentroids();
bool changed;
List newLabels = List.filled(data.length, -1);
do {
changed = false;
for (int i = 0; i newLabels) {
List newCentroids = List.generate(k, (_) => null);
List counts = List.filled(k, 0);
for (int i = 0; i 0) {
if (T == DateTime) {
// Ensure division by zero is handled
int avgTimestamp = (newCentroids[i] / counts[i]).round();
newCentroids[i] = [DateTime.fromMillisecondsSinceEpoch(avgTimestamp)];
} else {
// Handle other types (e.g., calculating mean for numeric types)
// This logic needs to be implemented based on the nature of T
// Ensure proper handling for non-DateTime types as well
}
} else {
// Handle the case where a cluster has no points
// You may choose to leave the centroid as null or assign a default value
if (T == DateTime) {
newCentroids[i] = [DateTime.fromMillisecondsSinceEpoch(0)]; // Example default value
} else {
// Assign a default value or handle accordingly for non-DateTime types
}
}
}
centroids = newCentroids.cast>();
}
double _calculateDistance(List a, List b) {
// Use the calculator to compute distance
double distance = 0.0;
for (int i = 0; i distances = List.filled(data.length, 0.0);
// Step 2: For each data point, find the distance to the nearest centroid.
for (int i = 0; i sum + dist * dist);
double r = random.nextDouble() * totalDistance;
double sum = 0.0;
for (int i = 0; i = r) {
centroids.add(data[i]);
break;
}
}
}
}
}
|