나는 가중치가 적용된 항목의 순서 목록을 가지고 있으며, 각각의 가중치는 N보다 작거나 같습니다. 클러스터 목록으로 변환해야합니다. 각 클러스터는 여러 개의 연속 항목에 걸쳐 있어야하며 클러스터의 총 가중치는 N보다 작거나 같아야합니다.정렬 된 데이터 집합을 최소 수의 클러스터로 그룹화
총 클러스터 수를 최소화하고 가중치를 균등하게 유지하면서 알고리즘을 수행하는 알고리즘이 있습니까? 가능한 한?
예. [(a, 5), (b, 1), (c, 2), (d, 5) 3), ([d], 5)]
데이터 집합이 정렬되었으므로 가능한 한 각 클러스터에 "badness"점수를 할당하고 Knuth의 단어 줄 바꿈 (http://en.wikipedia.org/wiki/Word_wrap)을 연상시키는 동적 프로그램을 사용하여 나쁜 점 점수의 합계를 최소화합니다. 나쁜 기능을 사용하면 클러스터 수를 최소화하고 (큰 상수 항) 균형을 잡는 것 (평균 항목 수에서 벗어난 경우 더 큰 페널티) 사이의 절충 점을 탐색 할 수 있습니다.
위대한, 너무 동적 프로그래밍에 대해 생각. 아아아, 내 일에 너무 많은 일이있는 것 같아서, 나는 그 일을 부르거나 근사치로 생각할 것이다. – yk4ever
문제가 제대로 지정되지 않았습니다.
결과 데이터의 두 가지 속성을 최적화하려고하고 있는데,이 속성은 서로 반대 일 수 있습니다. 주어진 데이터 세트의 경우, 가장 균등 한 분포에는 많은 클러스터가 있고 가장 적은 수의 클러스터는 매우 고르지 않은 분포를 가질 수 있습니다.
예를 들어, 고려 : (a, 1), (b, 1), (c, 1), (d, 1), (즉, 1), N = 2
가장 ([a], 1), ([b], 1), ([d], 1), ([e], 1)]
알고리즘은 어떻게 이러한 (또는 [], (1), (2), (3) 그들 사이에 클러스터링) 당신이 원하는가? 당신은 을 몇 가지 방법으로 찾아야합니다.은 클러스터의 수와 분포의 균등성 사이에서 받아 들일 수있는 트레이드 오프입니다.
2k + 1 요소가있는 집합을 만들고 N/2 값을 모두 할당하여 두 가지 가능성간에 임의의 큰 불일치가있는 예제를 만들 수 있습니다. 이것은 가장 큰 클러스터와 가장 작은 클러스터 사이의 N/2의 가중치 차를 갖는 k + 1 클러스터 (2 요소의 k와 1의 1) 인 클러스터의 최소 수를 유도합니다. 그리고이 세트에 대한 가장 균일 한 분포는 각각 1 원소의 2k + 1 클러스터가 될 것이고 무게 차이는 없습니다.
편집 : 또한 "균등 함"자체는 잘 정의 된 아이디어가 아닙니다. 클러스터 간의 가중치의 최대 차 또는 가중치의 평균 차 또는 가중치의 중간 차이 또는 가중치의 표준 편차를 최소화하려고하십니까?
예 : 모든 것을 단일 클러스터에 넣습니다. 의미 : 당신은 클러스터의 수에 다른 제약이 필요합니다. – Nicolas78
http://en.wikipedia.org/wiki/Bin_packing_problem – Ron
배포의 균등성을 최적화하려는 추가 요구 사항이 있으므로 빈 포장과 정확하게 일치하지 않습니다 (빈 포장보다 더 어려울 수 있음) –