2011-05-02 2 views
1

예. "고래"는 동물의 "자식"이지만 "고래"는 "개"보다 "돌고래"와 더 비슷하다고 말할 수도 있습니다. 이 경우 "고래", "돌고래", "개"는 모두 동물의 아이들이지만 "고래"와 "돌고래"는 분명히 관계가 있습니다.트리의 형제 간의 친밀도가 어떻게 표현됩니까?

나는 우리가 밖으로 우리의 방법을 "정의"할 수 맡기 단순히 ... 위의 예는 단지 설명을위한 것입니다 ("육상 동물", "바다 동물"예를 들어)의 서브 클래스를 정의에 관심이 아니다 문제.

하나는 단순히 그 그래프의 일부 부분 집합은 정말 (필요에 걸친되지 않음) 나무라는 지식 가중 파트 비순환 그래프를 정의 하는가?

편집 : 많은 사람들이 더 많은 설명을 요구했습니다. 나도 같은 예제를 사용하지만, 아마

우리는 다음과 같은 범주 말해봐 더 자세히로 갈거야 :

Animals, Place, Object. 
    The following sub categories: [land animals, sea animals], [country, state], 
[heavy object, light object] 
    And we have the following entries: Whale, Dolphin, Dog, Cat, Hawaii, Japan, 
London, Stone, Rock, Leaf, Car. 

    I have an isLike(entry x) function that I can call on any of the entries. 

    for example say whale.isLike(dolphin) = 0.7, whale.isLike(dog) = 0.2 and 
a table like the following one stores all the values for the isLike() function 

      Whale dolphin dog cat hawaii japan london stone 
    whale 1  0.7  0.2 0.2 0.01 0.01 0.01 0.008 
    dolphin 0.7 1  0.2 0.2 0.01 0.01 0.01 0.008 
    dog  etc 
    cat  etc 
    hawaii etc 
    japan etc 
    london etc 
    stone etc 

이 데이터를 표현하는 가장 좋은 방법은 무엇입니까?

나는 계층 정보 (트리)뿐만 아니라인가 봐요() (가중 그래프)의 관계 정보를 유지하는 방법에 대한 가장 걱정

그래서 그냥 할 수있는 표준 것은 감독이 사용하는 것입니다 여부를 묻는 그래프 (트리의 경우) + 가중치가 적용되지 않은 그래프 (관계의 경우) 구조 유형? 이 표준이 있습니까? 아니면보다 표준적인 방법이 있습니까?

+0

정확하게 표현하려고하는 이유와 그 이유가 무엇인지는 분명하지 않습니다. 동물을 비교할 수있는 수많은 방법이 있습니다. 어떤 관계는 수치 적으로 (수영 속도와 같이) 표현 될 수 있고, 다른 관계는 그래프로 더 잘 표현 될 수 있습니다. 입력 데이터가 무엇입니까? 또한, 결국 당신은 무엇을 달성하려고합니까? – Rotsor

답변

1

당신은 아마 그래프에 친밀감을 표현하기 위해 가중, 방향성 에지를 사용하고 싶습니다. 하지만 여기서 성취하려고하는 것은 분명하지 않습니다. 성취하려는 대상에 따라 분류 계층에서 관계를 분리 할 수 ​​있습니다.

+0

Michael 더 명확하게하기 위해 질문을 편집했습니다 ... 지금 어떻게 생각하십니까? ... 감사합니다! – algorithmicCoder

1

트리의 노드 간 거리를 정의하는 데는 여러 가지 방법이 있습니다. 부모, 형제, 삼촌 등을 사용할 수 있습니다. 자세한 내용은 Red-Black Trees을 확인하십시오.

귀하의 정의에 대한 정의가 이치에 맞지 않습니다. 거리를 정의 할 수있는 유일한 방법은 노드에 배열 방법을 알 수 있도록 구조 정보를 트리에 추가하는 것입니다. 그것이 "하위 클래스"가 계층 적 관계에서하는 역할입니다. 링크는 본질적으로 단지 "가장자리"입니다 (tree can be transformed into a graph).

당신의 노드 그냥 라벨 경우

는, 그들은 데이터의 nominal pieces 있습니다. 비율이나 간격을 계산할 방법이 없으므로 거리 메트릭은 원하는 노드의 링크 수와 같아야합니다. 트리에 노드 (예를 들어, 동물에 대한) 데이터 구조에 해당하는 경우

, 우리는 그 구조의 각 특성을 공유하고 있다고 가정 할 수 있습니다. (예 : 눈 색깔, 체중, 높이, isFurry 등)이 속성에는 간격 또는 비율 척도로 영역과 범위가있을 수 있습니다.이 경우 의미있는 거리를 계산할 수 있습니다.

여기서 오브젝트 간의 거리를 나타 내기 위해 실제로하고있는 일은 일련의 변수 (x = 눈색, y = 무게, z = 높이, isFurry = q)에 걸쳐 좌표 공간을 정의하는 것임을 알 수 있습니다. 따라서 각각의 개별 노드는 실제로 공통 속성 집합에 의해 정의 된 좌표 공간의 벡터입니다. 따라서 유클리드 거리, Mahabolis 거리, 맨하탄 거리, 코사인 유사도 또는 원하는 거리 거리를 계산할 수 있습니다.

+0

정의는 유사성 척도를 사용하지 않고 대신 여러 가지를 그룹화 함을 의미합니다 ... – algorithmicCoder

+0

하지만 유사성 측정을 사용하려면 유사성을 비교해야합니다. 그룹화는 유사성 척도를 정의 할 때 우리가 활용하는 연관성과 구조를 만듭니다. 그룹화하는 방법은 암시 적으로 거리를 만듭니다. –

0

나는 당신이 일을하려고하는 것은 hierarchical clustering이라고 생각하고, 당신이해야하는 거리 행렬이라고합니다.

+0

이것은 하나가 이미 패턴을 알고 그것을 표현하려고하는 것과는 대조적으로 데이터에서 패턴을 찾으려고 할 때 더 적합합니다. – algorithmicCoder

+0

이미 가지고있는 것은 매트릭스입니다. 만족한다면 매트릭스가 답입니다. 그러나 나는 나무와 같은 구조를 원했지만 그 구조는 아직 가지고 있지 않았습니다. 계층 적 클러스터링 및 결과 트리 구조 (요소의 단순한 그룹화)는 바로 그 것입니다. – sawa

+1

질문에 대한 편집 내용과 제공된 예제 (거리 매트릭스를 정의 함)를 기반으로하면 여기에있는 것과 똑같은 소리가납니다. 나는 작전 본부가 그가 무엇을 할 것인지를 잘 모르겠다. 선험적으로 계층 구조 관계를 알 수 있다면 이미 거리가 있고 각 노드와 다른 노드 사이에 링크를 저장할 수 있습니다. 예, 모든 것을 그래프에 저장합니다. 이 정보를 사용하여 새 노드를 분류하려면 K-Nearest Neighbors를 사용할 수 있습니다. 계층 적 관계를 모르는 경우 HAC를 사용하여 계층 관계를 찾을 수 있습니다. –

관련 문제