알고리즘 찾기 : '유사성'에 의한 클러스터링

Question

나는 '벡터'세트를 가지고 있는데, 나는 '유사점'에 근거하여 정렬해야합니다.

벡터 {1,0,0} {1,1,0} {0,1,0} {1,0,1}은 꽤 유사하며 결국에는 서로 가깝게 있어야합니다. 그러나 벡터 {1, 0, 0} {8, 0, 0} {0, 5, 0} -은 그렇지 않습니다.

A와 B 사이의 메트릭은 max (abs (A [i] -B [i]))이지만 어떤 알고리즘이 상대 비교를 기반으로 정렬 할 수 있습니까?

UPD : 입력 : N 벡터의 어레이
OUPUT : N 벡터 인덱스 벡터에 의해 가까운 (도착 [I] 도착 [I + 1] 예를 들면)는 '비슷한'= 메트릭 도착의 [사이의 배열 i] 및 arr [i + 1]은 임의의 i, j에 대해 가능한 한 낮다.
메트릭 - 벡터 구성 요소의 최대 차이

upd2 : 지금 보인다 은 @jogojapan은 옳았다 - 내가 A의 그룹

Answer 1

에 의해, 그룹 벡터를 클러스터 후에, 일부 선형 순서로 인쇄해야 거리는 max norm (aka sup norm or l-infinity norm)에 의해 유발됩니다. 선형 정렬을 생성하기에 거리가 충분하지 않습니다. 정렬을하면 시퀀스에서 ordring을 의미합니다.

Answer 2

모든 정렬 알고리즘을 통해 원하는 결과를 얻을 수 있습니다.

질문은 벡터를 비교하는 방법입니다. 규모 만 비교하고 싶습니까? 또는 다른 것?

Answer 3

정렬은 본질적으로 1 차원 문제입니다. 여기서 설명하는 것은 더 많은 가중 그래프처럼 들리지만 목표가 무엇인지는 분명하지 않습니다. Hamming Distance과 같은 정보 이론의 일부 개념은 알려진 벡터에 "가장 가까운"벡터를 식별하려는 경우 유용 할 수 있습니다.

Answer 4

글쎄, 명백한 접근법은 항상 가장 작은 거리와 그 클러스터를 병합 (IMHO 심하게 명명 된) "계층 적 클러스터링"것입니다. 거기에 메트릭을 연결할 수 있습니다. 대부분의 구현은 O (n^3)에 있으므로 대규모 데이터 세트에는 유용하지 않습니다. 또한, 읽기 어려운 거대한 맹검 법 (dendrogram)을 얻을 수 있습니다.

OPTICS를 사용해 볼 수도 있습니다. 위키 백과에서 찾아보세요. 실제로는 종류의 포인트가이므로 귀하의 요구를 아주 잘 충족시킬 수 있습니다. 그것은 하나의 클러스터에서 다른 클러스터로 이동하며 사실상 계층 적 ("중첩 된"클러스터링과 같은) 클러스터링을 생성 할 수 있습니다. 좋은 구현은 O (n^2)에서 인덱스 구조없이 실행되어야하고 O (n log n)에서는 인덱스 가속으로 실행되어야합니다.