n 차원 매칭 알고리즘

Question

여기에 몇 가지 조언을 찾고 있습니다. 누구든지 n 차원 공간에서 일치하는 알고리즘을 조사하기에 좋은 곳을 알고 있습니까? 예를 들어, 데이트 사이트는 2 명의 사람들과 어울리는 일종의 알고리즘을 사용해야합니다. 내가 읽은 것은 n 차원 배열에있는 사람의 특성을 각 특성에 대한 포인트 시스템으로 매핑 할 수 있다는 것입니다. 사람의 모든 (이용 가능한) 특성을 갖게되면, n 차원 배열 내의 한 지점에서이 사람을 나타낼 수 있습니다. 그런 다음 2 명을 일치 시키려면이 n-dim 배열에서 2 점 사이의 최단 거리를 찾는 것만 큼 간단합니다. 누구 알고리즘의 이러한 종류의 구현에 어떤 참조가 있습니까? 이런 종류의 글을 쓸 수있는 최고의 언어는 무엇입니까?

Answer 1

먼저 가장 익숙한 언어를 선택하십시오. 이를 처리하는 알고리즘은 매우 간단하며 모든 현대 언어로 작동해야합니다. (배열과 잠재적으로 매트릭스 라이브러리의 개념이있는 한, 당신은 괜찮을 것이다.) 나는 C, C++, C#에서 이들 중 많은 것을 구현했지만 파이썬, vb.net 등에서는 구현을 보았다.

수행하려는 작업에 따라 몇 가지 옵션이 있습니다.

당신이하고 싶은 것은 당신의 목표에 달려 있다고합니다. 최상의 일치를 찾고 싶다면 간단한 거리 계산 (즉, n 차원 배열의 각 차원/특성에 대한 제곱합의 sqrt)을 사용할 수 있으며, 선택적으로 각 속성 거리에 가중치를주고 가장 가까운 점을 사용할 수 있습니다.

사람들을 함께 그룹화하려면 clustering algorithms을보고 싶을 것입니다. 이런 데이터의 경우, 나는 K-Means 클러스터링이나 퍼지 C- 평균 클러스터링이 가장 잘 작동한다고 의심 할 것입니다. 당신이 한 사람과 가장 가까운 것을 찾으려면

Answer 2

는 벤틀리 & Shamos는 다차원 분할 정복 방법 게시 : O에서 분할 정복을 시간 (N N 로그) : Divide-and-conquer in multidimensional space을의 절차에 계산 이론에 관한 제 8 회 연례 ACM 심포지엄 1976. 사본을 얻을 수 없다면 this도 도움이 될 수 있습니다.

그러나 예를 들어 실제로 가장 가까운 이웃을 찾는 것이 가장 큰 문제는 아닌 것 같습니다. 입력을 차원으로 매핑하는 것이 훨씬 더 까다 롭습니다. 예를 들어 한 차원이 "동물을 좋아한다"면 개를 좋아하는 사람에게 어떤 가치를 부여합니까 & 고양이는 말을 견딜 수 없습니까? 말을 좋아하고, 개가 괜찮다고 생각하고 고양이에게 짜증을 내며 금붕어에 대해 양면성이없는 사람은 어떨까요?

Answer 3

당신이 언급하는 과정은 k- 가장 가까운 이웃 (k = 1)으로 알려져 있습니다. 유사한 벡터를 찾는 가장 직관적 인 방법입니다.

http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

Answer 4

어떻게 솔루션을 다음에 대해.

사용자가 U1, U2, U3, U4, U5 ....라고 가정합니다. 속성은 A1, A2, A3, A4, A5 ..... 오전

스토어 이들

A1

로 - U1, U2, U3 ... A2 - U4, U6, U7 ... A3 -

프로필 속성은 색인이며 모든 사용자를 저장합니다. 이제 새로운 사용자가 오면 그 속성을보고 그 속성에 대해 일반 사용자를 찾습니다. 사람이이 목록에있는 횟수 - 상위 순위.

Answer 5

예제에 설명 된 내용은 n 차원 적으로 일치하는 것이 아니라 복수 기능이있는 노드의 bipartite matching입니다. (두 사람이이 거리를 계산하면 주어진 기능을 제공해야합니다.) 이를위한 매우 효율적인 알고리즘이 있어야합니다. n 차원 적 매칭에서는 두 세트 이상의 노드를 일치 시키려합니다 (예를 들어, 사람을 신체, 영혼 및 음악 선호도로 잘라낸 다음 새로운 노드를 만들어 새로운 인물을 만들 수 있다고 가정하십시오.) 그러면 n 차원 일치는 사람들을 분리하고 재결합하여 새로운 사람들이 실제로 멋진 커플을 만들 수있게하십시오. D) wikipedia article for 3-dimentional matching은 np-complete입니다.

또 다른 설명에 따르면, 목표가 쌍으로 사람을 대조하는 것이 아니라 호환 가능한 그룹을 찾는 경우 그룹으로 클러스터링하는 것이 좋습니다. 이것은 예를 들면 다음과 같이 행해질 수있다. Unsupervised Learning