숫자 클러스터링/파티셔닝 알고리즘

Question

숫자의 1 차원 배열이 있습니다. 배열 길이와 배열의 숫자 값은 모두 임의입니다. 숫자 값에 따라 배열을 k 개의 파티션으로 나누고 싶습니다. 30 %/30 %/20 %/20 %, 즉 상위 30 % 값, 다음 30 % 등으로 분산 된 4 개의 파티션을 원한다고 가정 해 봅시다. k와 분포의 백분율을 선택합니다. 또한 동일한 숫자가 배열에 두 번 이상 나타나면 두 개의 다른 파티션에 포함되어서는 안됩니다. 즉 위의 분배 비율은 엄격하지 않고 원하는 경우 "목표"또는 "시작 지점"입니다.

예를 들어, 내 배열이 ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8]이라고 가정 해 봅니다.

난 k = 4 선택하고 숫자 pA = pB = pC = pD = 25% 비율로 파티션 A, B, C 및 D에 분산되어야한다.

내가 위에서 준 제약을 감안할 때, 결과 파티션이 있어야한다 : 발생하는 (달성/수정) pcA = 10%, pcB = 20%, pcC = 20%, pcD = 50%

비율 내가 수정 된 K-이 필요하다는 것을 날 것으로 보인다와

A = [1] B = [5, 5] C = [6, 7] D = [8, 8, 8, 8, 8]

표준 알고리즘이 내 백분율 및/또는 동일한 값이 둘 이상의 클러스터/파티션에있을 수 없다는 요구 사항을 준수하지 않기 때문에 알고리즘을 의미합니다.

그래서 이런 종류의 클러스터링을위한 알고리즘이 있습니까?

Answer 1

순진 방법은 다음과 같이 갈 것 :

말의 P1을 ... PK 파티션에 대한 비율은 (P1 + ... + PK = 1)

는 배열의 N 요소를 말해봐

초기 경계 (k 파티션이 있기 때문에 어레이 끝을 포함하여 k + 1이 있습니다) : 0, p1 * N, (p1 + p2) * N, ..., N 일부 반올림 할 것입니다).

경계를 이동하는 경우 경계의 각면에있는 두 개의 배열 요소 (이동 가능한 k-1 경계)를 살펴 봅니다. 두 요소가 같으면 적어도 제약 조건이 충족 될 때까지 왼쪽, 오른쪽으로 경계로 이동해야합니다. 순진한 접근법은 왼쪽에서 시작하여 최소한의 조정을 수행하는 것입니다 (최소 이동을 유발하는 측면에 대한 제한을 조정하고 경계를 더 이상 이동하지 마십시오).

이 알고리즘은 파티션의 전체 공간을 차지하지는 않습니다. 단지 하나의 솔루션 만 제공합니다. 최상의 솔루션을 찾으려면 일종의 가지 치기 (예 : 동적 프로그래밍, 초기 배열의 하위 배열에 가장 적합한 분할을 기억하는)와 함께 전체 파티션 공간에서 무차별 강제 검색을 수행해야합니다.

Answer 2

클러스터링 알고리즘은 다차원 데이터에 사용됩니다. 1 차원 데이터의 경우 정렬 알고리즘을 사용하면됩니다.

데이터를 정렬하십시오. 그런 다음 예제에 따라 배열의 맨 아래에서 맨 위로 선형으로 작업하는 데이터 세트를 분할하십시오.

Answer 3

다음은 부품 크기의 오차 제곱의 합을 최소화하는 파티션을 찾는 동적 프로그래밍 솔루션입니다. 따라서 [1, 5, 6, 7, 8, 8, 8, 8, 8]의 예에서 크기의 부분을 원합니다 (2.5, 2.5, 2.5, 2.5)이고이 코드에 의해 주어진 결과는 (9.0, (1, 2, 2, 5))입니다. 이것은 선택된 파티션이 크기가 1,2, 2, 5이고 총 오류가 9 = (2.5-1)^2 + (2.5-2)^2 + (2.5-2)^2 + (2.5- 5)^2.

def partitions(a, i, sizes, cache): 
    """Find a least-cost partition of a[i:]. 

    The ideal sizes of the partitions are stored in the tuple 'sizes' 
    and cache is used to memoize previously calculated results. 
    """ 
    key = (i, sizes) 
    if key in cache: return cache[key] 
    if len(sizes) == 1: 
     segment = len(a) - i 
     result = (segment - sizes[0]) ** 2, (segment,) 
     cache[key] = result 
     return result 
    best_cost, best_partition = None, None 
    for j in xrange(len(a) - i + 1): 
     if 0 < j < len(a) - i and a[i + j - 1] == a[i + j]: 
      # Avoid breaking a run of one number. 
      continue 
     bc, bp = partitions(a, i + j, sizes[1:], cache) 
     c = (j - sizes[0]) ** 2 + bc 
     if best_cost is None or c < best_cost: 
      best_cost = c 
      best_partition = (j,) + bp 
    cache[key] = (best_cost, best_partition) 
    return cache[key] 


ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8] 
sizes = (len(ar) * 0.25,) * 4 
print partitions(ar, 0, (2.5, 2.5, 2.5, 2.5), {})