2015년 6월 29일 월요일

javascript bind는 무엇인가?

아래의 질문에 대해 답해보자!
function foo() {};
foo.bind(this) !== foo.bind(this);
false
왜일까? 문제를 좀더 간단하게 바꾼 후 생각해보자
var a = {};
var b = {};
//묵시적으로 인터프리터에서 아래 문장으로 변환후 처리
//var a = new Object();
//var b = new Object();
a === b (a == b) 인가?
아니다 왜냐하면 a 와 b 는 다른 object 이기 떄문이다.
아래 주석처리된 부분을 보면 명확해 진다.
하나의 클래스에서 populate 된 두개의 다른 instance 이기 때문이다.(각기 다른 메모리 주소를 레퍼런스로 가지고 있다.)
Features of comparisons:
If both operands are objects, then JavaScript compares internal references which are equal when operands refer to the same object in memory
(https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Comparison_Operators)
위의 문장이 이해가 되었다면 아래 문장을 생각해보자
function foo() { console.log(this); console.log(arguments)};
var obj = {};
var a = foo.bind(obj,1);
var b = foo.bind(obj,1);
a(2,3);//1,2,3
b(2,3);//1,2,3
a === b
즉 2개의 새로운 함수를 생성한 후 위와 같이 두개의 래퍼런스가 같니라고 물어보는 상황인 것이다.
즉 false 가 나와야 함이 명확하다.
하지만 bind가 조금 애매하다.. 머하는 놈이었는지….
그럼 좀더 bind가 머하는 애인지 살펴보자!
Function.prototype.bind()
The bind() method creates a new function that, when called, has its this keyword set to the provided value, with a given sequence of arguments preceding any provided when the new function is called.
(https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/bind)
즉 새로운 함수를 생성하는대 해당 함수의 this 키워드를 주어진 argument의 첫번째 값으로 설정한 함수를 돌려 준다.
그후에 정의된 파라미터가 있으면 이후 호출시 해당 value를 미리 채워서 넘겨준다 라고 설명되어있다.
위의 설명을 확인하면 Function.prototype.bind 라는 함수는 아래처럼 정의 될수있다.
Function.prototype.bind = function() {  
  var _this = this;
  var outArg = Array.prototype.slice.call(arguments,0);
  return function() {
      var inArg = Array.prototype.slice.call(arguments,0);
    return _this.apply(outArg[0], outArg.slice(1).concat(inArg));
  }
}
var obj = {};
var a = foo.bind(obj,1);
var b = foo.bind(obj,1);
a(2,3);//1,2,3
b(2,3);//1,2,3
실재로 실행해보면 두개의 결과가 동일하다는걸 알 수 있다.
그렇다면 이제 처음 질문으로 돌아가 보자
function foo() {};
foo.bind(this) !== foo.bind(this);
여기서 this는 global object이기 때문에 host의 최상위 객체를 집어넣는다.
브라우저의 경우 window 이다.
즉 같은 파라미터를같는 두개의 펑션의 인스턴스를 생성한 후 두개의 인스턴스가 같니?
라는 질문이기 때문에 false 가 나와야 함이 자명하다!

2015년 4월 21일 화요일

장소별 유사도 비교

유사한 두개 회사의 동일 데이터를 찾아서 통합해라


1. 목적

  • 기본문제: 두개 회사에 유저셋1, 유저셋2가 있다 해당 유저중 비슷한 유저를 찾아서 통합해라
  • 필자문제: 두개 회사에 장소셋1, 장소셋2가 있다 해당 장소중 비슷한 장소를 찾아서 통합해라
  1. 그림 설명
    아래 그림을 보면 투어라는 회사에서 어떤 장소를 선택한 후 유사도 검색을 하면 위시빈 이라는 회사의 장소에서 가장 유사한 애들을 나열 한후 유사도를 보고 아래 통합 버튼을 눌러서 통합 할 수 있다.
  • 유사도 0.5 이상이 존재하는경우 1
    alt img
  • 유사도 0.5 이상이 존재하는경우 2
    alt img
  • 존재하지 않는 경우
    alt img
  1. 목적 설명
    필자의 경우 투어 회사의 데이터가 적었기 때문에 완전 자동화 할필요는 없었다.(구현 시간보다 사람이 하는게 더빠르다….) 그래서 기본적인 툴만 만들어 주면 되었다 만약 비교할 데이터가 많았으면 LSH 알고리즘을 사용해서 유사항 쌍을 찾고 특정 한계값을 기준으로 통합 시키고 남은 애들만 사람이 수동으로 통합하거나 버리거나 하는 방법을 사용했을거 같다.
    • 데이터가 조금이라도 많아지면 시간 복잡도는 O(M*N)에 유사도를 계산하는 비용까지들어가야한다… LSH를 사용하지 않고 하나의 장소를 다른 셋의 모든 데이터와 비교하는건 힘들다.
  2. 유사도 계산
    문제는 어떻게 해당 애들의 유사도를 계산하느냐이다 일단 유사할것이라고 예측하는 4개의 필드를 뽑았다. 필자의 경우 최초 장소명으로 검색을 했지만 필요하다면 LSH를 사용해서 전체를 대상으로 비교 할수도 있다.또는 장소일 경우는 특정 범위를 기준으로도 가능하다
    • 장소명
    • 장소 전화번호
    • 장소 홈페이지
    • 장소 위도,경도
    위의 필드를 사용해서 어떻게 유사도를 계산을 할까?

각속성별 계산방법

  1. 장소명 속성
    장소명의 경우 아래와 같이 동일한 스팟의 경우에도 이름이 다를 수있다. 최초 유사도로 edit distance 를 생각했지만
    관련논문을 보고 2gram 후 jaccard similarity 를 사용했다.
    • 노보텔 클락키 싱가포르 | 노보텔 (Novotel)
      function nGram(str){
        return n_Gram(2)(str.replace(/\s/g,'').toLowerCase());
      }
      nameSim = jaccard.index(nGram(wName),nGram(tName))
      
      jaccard.index(nGram('IFC 몰'),nGram('IFC 몰 (IFC Mall)'));
      //0.3
      
      nGram 호출전에 전처리 작업으로 공백 캐릭터를 없애고 전부 로우어 케이스로 변경했다. 하지만 솔직이.. 해당 속성은 유사도에 그렇게 많은 영향을 주지 않을 거라고 생각한다.(오타, 한영 등.. )
  2. 장소 전화번호 속성
    전화 번호의 경우 동일하다면 해당 스팟이 동일한 스팟이라고 확신 할수 있을 정도다 (물론 앞부분에 국가 번호 (도시번호) 등의 특수 번호를 처리한다면…) 필자의 경우 특수 번호를 전처리 하지 않았기 떄문에 가중치를 주지는 않았다. 또한 전화번호의 경우 0~10까지의 숫자임으로 ngram후 jarccard를 할 경우 유사도를 잘 판단할수 없다.그래서 숫자추출 후 공백 문자로 분리 그 후 자카르 유사도를 계산했다.
     function getNumberArr(str){
       var temp = str.split(/\s/);
       for(var i = 0; i < temp.length;i++){
         temp[i] = temp[i].replace( /^(\D+)/g, '');
       }
       return temp;
     }
    
     jaccard.index(getNumberArr('+852 2295 3308'),getNumberArr('852 2295 3308'))
     //1
    
  3. 장소 홈페이지 속성
    해당 장소가 동일한 홈페이지(도메인) 주소를 가지고 있을 경우 동일한 스팟으로 볼수있다. 도메인만 추출 후 -> ngram 으로 후 자카드를 계산했다.
     jaccard.index(nGram(parseUri('naver.com/aaaa/a')),nGram(parseUri('http://www.naver.com')))
     //0.9
    
  4. 장소 위치 속성
    가장 중요한 부분이다. 해당 장소가 1000미터 이상 떨어질 경우(공원, 쇼핑몰 등은 폴리곤으로 만들지 않는이상 lat,lng가 차이날 가능성이 많다.) 0 1000 미터 이내일 경우 가까울수록 높은 유사도를 리턴 하도록 했다. 또한 가장 중요한 속성이라 고 생각했기 때문에 가중치 3배를 주었다.
     distanceWeight = 3
     function getDistanceProbability(a){
       var max = 1000;
       var distance =  Math.abs(max - a);
       return (distance >= max ? 1 : distance)/max;
     }
     distanceSim = getDistanceProbabilty(geolib.getDistance(
       {latitude: wLat, longitude: wLng},
       {latitude: tLat, longitude: tLng}
     ));
     totPro += distanceSim * distanceWeight;
     totCnt += 1 * distanceWeight ;
    

결론

  1. 전체 유사도계산
    검색엔진에서 처리하듯이 그냥 유사도 점수로 계산했다
     유사도 = 전체 sum / 카운트
    
  2. 결론
    threshold 를 0.5 로 잡은 결과 필자의 확인 결과로는 95%로 이상의 정확도를 보여줬다.
    시간이 없어서 이쯤에서 마무리 하기는 했지만 재미 있었다.

2015년 4월 7일 화요일

What is high bias and variance

What is high bias and variance?

  • 늘 이상했던게 overfitting 과 underfitting 은 직관적으로 이해하기 쉽다.
  • 하지만 high bias , low bias, high variance, low variance .. 난 해당 사항을 각각 2개의 경우로 구분했다. 하지만 복합되어 4개의 경우로 표현된다.
  • 일단 단어의 뜻을 보자 bias 는 편향 이라고 생각하면 된다 즉 정확한 값이 있을 때 모델이 얼마나 해당 값을 편향 없이 잘예측 하는가 이다.
  • variance는 분산이다. 즉 예측값이 얼마나 정확한 값에서 분산 되어 있냐를 나타낸다.
  • 자 아래 그림을 보자 가운데는 정확한 값이고 파란점은 우리가 모델을 통해 예측 한 값이다.
  • 한장의 그림이 마디 말보다 낫다는 격언이 떠오르는 그림이다. :)
  • 아래 출처에 가면 설명이 아주 잘 나와있다.

  1. 그래픽 정의
    alt arg
    그림 및 설명 출처

2015년 4월 6일 월요일

Recommander System

Recommander System


  1. Collaborative Filtering
    x가 피쳐 백터
    \Theta가 유저별 liner regression 파라미터 백터라고 할때
    x^{(1)},\dots,x^{(n_{m})}을 주면 \Theta^{(1)},\dots,\Theta^{(n_{u})} 을 구할수있다.
    \min\limits_{\Theta^{(1)},...,\Theta^{(n_{u})}}\frac{1}{2}\sum_{j=1}^{n_{u}}\sum_{i:r(i,j)=1}((\Theta^{(j)})^{T}x^{(i)} - y^{(i,j)})^2 + \frac{\lambda }{2}\sum_{j=1}^{n_{u}}\sum_{k=1}^{n}(\Theta^{(j)}_{k})^2
    반대로 \Theta^{(1)},\dots,\Theta^{(n_{u})} 을 주면 x^{(1)},\dots,x^{(n_{m})} 을 구할수있다.
    \min\limits_{x^{(1)},...,x^{(n_{m})}}\frac{1}{2}\sum_{i=1}^{n_{m}}\sum_{j:r(i,j)=1}((\Theta^{(j)})^{T}x^{(i)} - y^{(i,j)})^2 + \frac{\lambda }{2}\sum_{i=1}^{n_{m}}\sum_{k=1}^{n}(x^{(j)}_{k})^2
    결국 닭이 먼저냐 달걀이 먼저냐 라는 생각이 든다. 하지만 우리는 유저가 각 영화에 점수를 매긴 값을 가지고 있다 어떻게 보면 x 와 세타는 유저별 영화평점에서 파생된 점수 들이라는 관점에서 볼수있다.
    그렇다면 세타와 x를 랜덤벨류로 주고 gradient descendent를 돌린다면? 둘다 구할수 있다 여기서 우리는 아래의 cost function 을 얻을수 있다
    J(x^{(1)},...,x^{(n_{m})},\Theta^{(1)},\dots,\Theta^{(n_{u})}) = \frac{1}{2}\sum_{(i,j):r(i,j)=1}((\Theta^{(j)})^{T}x^{(i)} - y^{(i,j)})^2 + \frac{\lambda }{2}\sum_{i=1}^{n_{m}}\sum_{k=1}^{n}(x^{(j)}_{k})^2 + \frac{\lambda }{2}\sum_{j=1}^{n_{u}}\sum_{k=1}^{n}(\Theta^{(j)}_{k})^2
    위의 펑션을 cost funciton으로 하고 아래의 코스트 펑션의 미분 식 으로 파라미터 값을 동시에 갱신하면 된다.
    \frac{\partial J}{\partial x^{(i)}_{k}} = \sum_{j:r(i,j)=1}((\Theta^{(j)})^{T}x^{(i)} - y^{(i,j)})\Theta^{(j)}_{k}  + \lambda x^{(i)}_{k}
    \frac{\partial J}{\partial \Theta^{(j)}_{k}} = \sum_{i:r(i,j)=1}((\Theta^{(j)})^{T}x^{(i)} - y^{(i,j)})x^{(i)}_{k}  + \lambda \Theta^{(j)}_{k}
    이렇게 우리는 피쳐백터 x 와 각 유저별 파라미터 벡터를 얻을수 있기 때문에 해당 유저가 평점을 매기지 않은 점수도 예측할수 있게 된다.
    하지만 위의 식에서 평점을 0~5 라고 할때 평점을 매기지 않은 점수를 0으로 가정해서 알고리즘을 적용하면 문제가 발생할 요지가 있다.
    유저가 평가를 안했으면 0점이 아니라 평균 점수를 주는게 맞기 때문이다.
    그래서 우리는 평점을 nomaliztion 해서 사용할경우 좀더 좋은 결과를 얻을수있다.

2015년 4월 2일 목요일

mmd ch10 Mining Social-Network Graphs

10 Mining Social-Network Graphs

페이스북 친구 관계처럼 그래프로 그려 낼수 있는 데이터는 많다. 우리는 해당 소셜 네트워크에서 커뮤니티를 찾아 내는 방법을 공부할것이다. 해당 알고리즘은 클러스터링과 비슷하게 보일수도 있지만 커뮤니티가 중첩될수 있다는 부분이 다르다. 예를 들어 페이스북 친구들에서 커뮤니티를 찾아낸다면 A는 대학교 커뮤니티면서 A는 고등학교 커뮤니티에 동시에 속할수 있다. 해당 부분에 대해서 공부해보자

  1. 10.1 Social Networks as Graphs
    소셜 네트워크 그래프 모델에 대해서 공부해 보자 소셜 네트워크 특징은 안의 노드들이 동일한 커뮤니티에 속해 있을 경우 클러스터링 되어 있다는것이다.
  2. 10.1.1 What is a Socail Network?
    우리는 페이스북, 트위터 ,구글+ 등을 보고 소셜 네트워크라고 부른다. 즉 사회적인 관계를 표현한 네트워크 란 의미이다. 자 소셜 네트워크 주된 특징은 무엇일까?
    • 네트워크에 참여하는 entities 들이 있으며 대체적으로 사람이다(하지만 다른경우도 있음)
    • entities 사이에 관계가 존재한다. 관계의 종류는 다양하며 페이스북에서는 친구 이며 관계는 친구이거나 아니거나로 표현된다. 하지만 구글+에서는 관계가 숫자로 나타난다. 친구, 가족 등 (예를 들면 두사람이 대화하는 날짜/모든 사람이 평균적으로 대화하는 날짜 같은 비율로 나타난다.)
    • nonrandomness 또는 locality 라는 가정이 존재한다. 관계가 있는 애들은 클러스터링 되어 있을 가능성이 높다라는 가정이다. 예를 들어 A가 B 와 C 에게 연결 관계가 있으면 B 와 C 가 서로 알 가능성이 평균에 비해 훨씬 높다는것이다.
  3. 10.1.2 Social Networks as Graphs
    소셜 네트워크는 그래프를 이용해서 모델링 할수있다. 소셜 그래프라고 불린다.
    엔터티는 노드라고 부르며 에지는 두 노드간의 관계를 표현한다. 만약 엣지에 등급(degree)을 줘야 하면 엣지에 레이블을 붙여서 표현 할수 있다. 소셜 그래프는 방향성이 있을 수도 (twiter followe) 없을 수도 있다. (facebook friend)
    alt text
     ex(10.1)
      figure 10.1 은 A~G까지는 사람이고 각 엣지는 친구 관계를 나타낸다. 예를 들면 B는 A,C,D와 친구이다.
    
    위의 그래프에서 locality 를 확인해 보자 9개의 엣지와 7개의 노드가 있다.
    노드간 존재 할수 있는 엣지의 총수는 {7\choose 2} = 21 이다.
    위의 그래프에서 X,Y,Z 를 뽑는다고 생각해보자(예를 들어 X = A, Y = B, Z = C)
    X,Y가 연결되어있고 X,Z가 연결되어 있을떄 Y,Z 가 연결될 확률을 구해보자
    물런 그래프가 엄청크다면 확률을 9/21 = 0.429 일것이다. 하지만 그래프가 작음으로 진짜 확률과 비율의 차이를 볼수 있다. 이미 (X,Y),(X,Z)의 연결이 존재함으로 엣지는 7개 노드는 19 개가 남아있다 즉 (Y,Z)의 확률은 7/19 = 0.368 이라는걸 알수있다.
    하지만 정말로 위의 그래프에 X,Y,Z를 대입해서 구해보자 X가 정해질 경우 Y,Z의 순서는 상관없다.
    X 가 A 라면 B,C 의 노드만 가능하고 두개가 연결되어 있음으로 +1 이라고 하자
    위의 상황은 X가 C,E,G 일때도 동일하다.
    X 가 F 라고 하면 F는 3개의 이웃노드를가지고 있고 (D,E,G) Y, Z가 D,E 또는 D,G일 경우 엣지가 존재한다. 하지만 E,G일 경우 엣지가 존재하지 않는다. +2, -1 이라고 하자
    X 가 B라면 +1 = {(A,C)}, -2 = {(A,D).(C,D)} 가된다.
    X 가 D라면 +2 = {(E,F),(G,F)}, -4 = {(B,G),(B,E),(B,F),(E,G)}가된다.
    위의 모든 수를 계산하면 +9, -7의 경우를 알수있다. 그렇다면 실제 가지고 있을 확률은 9/16 = 0.563이다. 이 확률은 0.368 에 비해 충분이 크다 그러므로 관계가 있는 애들끼리는 다른 애들보다 관계가 있을 확률이 높다는 locality 를 증명한다.

  1. 10.1.3 Varieties of Social Networks
    locality 와 relationships 속성이 있는 다른 종류의 소셜 네트워크를 나열해보자
    • Telephone Networks
      노드는 전화번호이며 특정한 기간에 A 와 B가 전화로 연결되었으면 관계가 있다고 정의하고 그 해당 기간 동안에 연결된 횟수를 degree로 나타낼수 있다.
    • Email Networks
      노드는 이메일이며 두개의 주소가 한번이라도 이멜을 발송(or 수신)한적이 있으면 관계가 있다고 보자(스팸머를 피할려면 수신,발신 둘다 있을때로 정의)또는 한쪽간의 연결관계가 있으면 약함 양쪽도 있으면 강함으로 나타낼수도 있다.
    • Collaboration Networks
      노드는 개인이며 연결과계는 같은 논문을 공동 저자로 나올때 생긴다고 보자 또는 논문을 노드로 보고 두 논문에 같은 저자가 있으면 연결관계를 만든다로 정의 할수도 있다.
      또한 양방향 관계가 있는 경우는 관계를 나타낼수 있다. 예를 들어 위키 피디아의 editior을 노드로 보고 두 editer가 동일한 article을 수정했다면 관계를 맺을수있다.
      ch9에 나오는 유저와 공산물과의 관계도 네트워크로 나타낼수도 있다. 예를 들어 동일한 물건을 산 유저들을 하나의 커뮤니티로 볼 수 있다.
      반대로 동일한 유저들에 의해 구매된 공산물들을 하나의 커뮤니티로 볼수있다.
    • other Examples of Social Graphs
      다른 종류의 많은 현상들도 소셜 그래프로 볼수있다 특히 locality 를 가지고 있다면..
      inforamtion networks(documents, web garph, patents)
      biological networks(genes, proteins, food-web of animal each other)
      product co-puchaing networks

  1. 10.1.4 Graphs With Serveral Node Types
    여러종류의 노드 타입을 같는 현상들이 존재한다.
    우리가 조금전에 이야기한 collaboration networks 의 경우 user 와 proudct의 2가지 노드로 구성되어 있다.
    또한 조금전에 이야기한 논문의 경우 논문, 저자로 표현할수있다.(좀전에는 둘중 하나를 없애서 표현한 경우 이다.)
    좀더 복잡한 예를 들자면 유저가 페이지에 주제별로 테깅을 한다고 생각해보자 3개의 종류의 노드가 존재하는경우이다.
    이럴 경우 k-partite 그래프라고 하며 k > 1 보다 크다. k-partite 그래프는 k 의 서로 다른 set 으로 구성되며 같은 set 끼리는 엣지가 없다.
     ex10.2)
     users = {U1,U2}
     tags = {T1,T2,T3,T4}
     webPages = {W1,W2,W3} 가 존재한다고 하고 
     {U1,T2}의경우 user1이 T2를 태깅했다고 생각하자 
     {T2,W2}의 경우 w2 page에 T2태그가 태깅된 것이다.
    
    alt text

  1. 10.2 Clustering of Social-Network Graphs
    소셜 네트워크의 경우 하나의 노드가 여러커뮤니티에 속할 수 있음으로 ch7 에서 이야기한 알고리즘이 잘맞지 않는다.
    (A노드는 고등학교 커뮤니티에 속하면서 대학교 커뮤니티에도 속할수 있다.)

  1. 10.2.1 Distance Measures for Social-Networks Graphs
    일단 클러스터링을 할려면 거리를 측정하는 방법을 정해야 한다 만약 그래프 사이에 degree가 존재하면 해당 정도를 쓸수 있지만 그렇지 않은 그래프가 더 많다 예를 들어 페이스북의 경우 친구이거나 아니거나 이다. 예를 들어 우리가 친구 이면 0 아니면 1이라고 거리를 정한다고 생각해보자 (거리기 때문에 가까울수록 작다) 또는 친구이면 1 아니면 무한대 라고 할 경우 해당 측정은 삼각 거리 ( triangle inequality)측정에 위배 된다. 예를 들면 (A,B)그리고 (B,C)가 친구이고 (A,C)가 친구가 아니라면 A -> C = 1 이고 A -> B -> C 는 0 이된다 삼각거리가 성립될려면 거처서 연결된 점은 바로 연결된 점보다 같거나 커야 된다.

  1. 10.2.2 Applying Standard Clustering Methods
    만약 우리가 일반적인 클러스터링 알고리즘 중 hierarchical 을 사용한다고 가정하면 우리는 거리를 측정 할수 없게 연결된 두 노드중 랜덤으로 뽑아서 결합 할것이다. 그래프가 크가면 결과 또한 랜덤하게 나옴으로 클러스터링 된다고 할 수 없다.
     위의 그림에는 {A,B,C}와 {D,E,G,F}클러스터가 존재한다고 볼수 있다 문제는 어떻게 해당 클러스터를 찾아낼수 있을까이다.
    
    다음으로는 kmean을 사용한다고 가정해보자 k=2 이고 우리가 정말 잘뽑아서 시작점을 B,와 F를 뽑앗다고 하자 D는 어디에 속해야 하는가? 정확이 F에 속한다고 인간은 판단하지만 알고리즘에서는 랜덤하게 됨으로 해당 알고리즘도 사용할수 없다.(D를 제일 마지막에 배치한다고 하고 주변에들과 비교해 가장 가까운 쪽
    에 붙일수 있지만 그래프가 커지면 에러가 생길수 있는 로직이다.)

  1. 10.2.3 Betweenness
    위에서 설명한 문제들을 해결하기 위해 여러 클러스터링 방법론이 만들어졌고 그중 심플한 알고리즘을 소개한다.
    기본 아이디어는 커뮤니티에 속하지 않을 가장 그럴사한 엣지를 찾아내는것이다.
    betweeness 라는걸 엣지 (a,b)사이에 존재하는 모든 노드 쌍x,y의 가장 짧은 거리(shortest path)라고 정의하자
    betweeness가 클수록 해당 엣지를 커뮤니티를 분리하는 엣지로 정의하는 방법이다.(아래에 상세 설명됨)
    참고:Betweenness centrality
  2. 10.2.4 The Girvan-Newman Algorithms
    엣지들의 betweenness 를 계산하기 위해서 우리는 각 엣지들을 지나는 shortest paths 들의 숫자를 새야한다.이방법중 하나인 Girvan-Newman(GN)알고리즘을 소개한다. 우리는 그래프의 모든 노드를 돌면서 해당 노드에서 다른 노드까지의 shortest path를 구할것이다. 해당 알고리즘은 그래프에 BFS(breath-first serach)를 행함으로 시작된다. BFS 표현에서 레벨은 X에서 해당 노드까지 갈수 있는 shortest path의 길이를 의미한다. 그러므로 같은 레벨에 있는 노드들끼리의 엣지는 X를 기준으로 절대 shortest path가 될수 없다.
    레벨사이에 존재하는 엣지들을 DAG 엣지라고 부르자(directed acyclic graph). 모든 DAG 엣지들은 루트 X에서부터 다른 노드들 사이를 가장 잛게 연결하는 shortest path의 일부분이 된다.
    만약 (Y,Z)의 DAG엣지가 존재한다고 가정하자 이떄 Y노드의 레벨이 Z노드보다 루트에 가까운 레벨의 노드라면 Y를 Z의 parent, Z를 Y의 자식 이라고 호칭하자 (부모가 유니크할 필요는 없다.)
    alt text
     ex10.6)f10.4를 보면 f10.3을 BFS로 표현한것이다. 루트는 E이다.
     1. 그래프를 BFS로 표현한다.
     2. 루트에 1을 표시하고 트리를 내려가면서 모든 자식 노드들의 점수는 연결된 부모노드의 점수의 합계로 정의한다.
    
     ex10.7)위의 2번째 스탭을 자세이 설명해 보자 
     1. E는 루트임으로  E는 1
     2. D,F의 부모는 E임으로 각각D,F는 1
     3. B의 부모는 D임으로 D는 1, G의 부모는 D,F임으로 합계 G는 2
     4. A,C의 부모는 B임으로 각각 A,C는 1
    
    3번쩨 스탭은 각각의 엣지 e의점수를 계산한다.
    e의 점수 = 루트 X에서 엣지e 를 통해 Y로 가는 모든 shortest path / 루트 X에서 Y로 가는 모든 shortest path
    해당 점수를 계산하는 방법은 아래와 같다.
     1. 모든 DAG 엣지의 leaf노드는 1점을 부여한다.
     2. 리프노드가 아닌 모든 노드들은 해당 노드에 DAG엣지의 합계 + 1을 부여한다.
     3. Z으로 들어오는 엣지e의 점수는 루트에서 Z으로 e를 통해 들어오는 모든 shortest path / Z로 들어오는 모든 shortestpath 이다.
    
    3.1 위의 식을 좀 추상화 하면 Z의 부모를 Y_{1},Y_{2},\dots,Y_{K}라고 할때 p_{i}를 루트로 부터 Y_{i}로 들어오는 shortest path의 수량이라고 하자(fig10.4의 점수)그러면 우리는 엣지(Y_{i},Z)의 점수를 \frac{Z * p_{i}}{\sum_{j=1}^kp_{j}}라고 할수 있다 위식의 Z는 위의 2번 규칙에 때라 각 노드에 부여한 점수이다.
    alt text
     ex10.8)위의 f10_5를 보자 우리는 맨아래 3레벨에서 부터 계산해 올라갈것이다. 
     1. 3레벨의 A와 C는 리프임으로 1을 같는다.
     2. 각 노드들은 하나의 부모를 같고 있음으로 엣지(B,A),(B,C)에 각각 1점을 부여한다.
     3. 2레벨의 G는 리프임으로 1, B는 리프가 아님으로 자기에게 들어오는 엣지의 합 + 1를 주면 3이된다.
     (B가 3인이유는 B를 통과해 가는 shortest path 가 많기 때문이다.)
     4. 1레벨로 가면 B는 D하나만 부모로 가짐으로 (B,D)는 3이다. G의 경우 (D,G),(F,G)를 가짐으로 점수를 분리한다
     근대 무슨 기준으로 분리해야할까? fig10.3의 D,F가 각각 1점임을 알수 있고(Root E에서 각각,D,F로 갈수 있는 shortest path의 수) 위의 3.1의 식을 적용하면 1*1/1+1 즉 각각 0.5 임을 알수 있다.
     5. 1레벨노드를 계산하면 D는 엣지합(3.5) + 1 = 4.5, Fsms 0.5 + = 1.5임을 알수있다.
    
    alt text
    우리가 모든 노드에 대하여 위의 알고리즘을 돌리면 모든 관계가 2번씩 발견됨으로 2로 나누어 주어야된다.
  3. 10.2.5 Using Betweenness to Find Communities
    betweeness 점수는 그래프에서 각 노드들간의 distance measure 와 비슷하다.(물런 정확히 그렇지는 않다 왜냐하면 연결되지 않은 노드끼리의 점수는 정의 되지 않았기 때문에 또한 정의한다고 해도 triangle inequality를 만족하지 못할것이다.)
    어째든 우리는 betweenness를 증가 하는 순서대로 하나씩 붙임으로써(작은 점수부터) 조금씩 큰 클러스터를 만들수 있다.
    위의 아이디어는 edge removal로 표현될수 있다 그래프를 모든 연결된 엣지에서 시작해 높은 betweeness 엣지를 삭제해 나간다 (만족할 만한 커뮤니티 그룹을 찾을때까지)
     ex10.9)f10_7을 보면 우리가 구한 betweeneess점수가 모든 엣지에 적혀있다.(아래 점수는 reader기분으로 왼쪽에서 부터 계산된 결과이다 )
    
    alt text
     일단 (B,D)가 가장높은 점수임으로 삭제한다 그러면 {A,B,C}와 {D,E,F,G}로 클러스터링 할수있다. 하지만 우리가 계속 높은 점수대로 제거해 나가면 {A,C},{B},{D},{E,F,G}로 나누어진다.
    
    alt text
    위의 그림은 조금 이상하게 느껴진다. 하지만 {A,C}가 연결되고 B가 분리된 이유는 B가 외부와 연결하는 통로이기 떄문이다.{E,G,F} 와 D도 동일한 맥락에서 이해 할수 있다.

정리중..


원본책  http://www.mmds.org