[SOCIAL MEDIA MINING8] - Classification withNetwork Information

Nearest neighbor classifier

 

instance에서 가까이 있는 n개의 neighbor(instance)를 구해서 분류 수행

To determine the neighbors of an instance, we need to measure its distance to all other instances based on some distance metric.

– Often Euclidean distance is employed

 

유사도 크면-유사 / 작음-유사하지 않음

거리 멀다-유사하지 않음/작음-유사

 

Classification with Network Information

Consider a friendship network on social media

 

friendship information that may be helpful in building better classification models

network 구조를 통해 구매여부를 예측

In wvRN, to find the label of a node, we compute a weighted vote among its neighbors

이미 구매여부가 확정된 경우, 1,0 부여 / 모를때는 0.5 부여

 

y4, y6 예측값이기 때문에 반복해서 값을 안정화 시킬 것

=>순서에 따라 값이 바뀔 수 있기에 순서를 고정하고 반복할 것

앞 뒤 값이 같으면 stop

 

Regression

descret한 값이 아닐 때, 회귀분석

이정도만 알고 있으면 됨

Supervised Learning Evaluation

The correct labels of the test dataset are unknown,

– In practice, the training set is divided into two parts,

• One used for training and

• The other used for testing

 

When testing, the labels from this test set are removed.

– After these labels are predicted using the model, the predicted labels are compared with the masked labels (ground truth). => 감춰진 정답이 있는 경우

 

• Dividing the training set into train/test sets

nn개로 쪼개고 그 중 1개만 빼고 나머진 다 train에 쓰고 1개는 test로 씀

 

– k-fold cross validation training

k-fold cross validation으로 나온 각각에 대한 test를 수행하고,

k개의 평균이 전체 학습모델의 성능

회귀 분석의 경우,

Example. When the observed temperature is 71, any prediction in the range of 71±0.5 can be considered as a correct prediction

d오차 +=0.5범위의 경우 정답으로 인정하지만 정확성이나 장비의 민감도로 달라질 수 있음

 

Unsupervised Learning

class 정보가 없음 -> 비슷한 데이터끼리 clustering(군집화)

• Clustering Goal: Group together similar items

Instances are put into different clusters based on the distance to other instances => 거리에 대한 measure 필요

Euclidean Distance / 맨하튼 == |X1-Y1| +  |X2-Y2| / 직선 == 루트( |X1-Y1|^2 +  |X2-Y2|^2 )

L1 = mManhatton / L2 = Euclidian

Lp = 맨하튼, 유클리디언 모두 결합 / Lp-nor

Lpnorm

Clustering

군집의 센터가 군집을 대표하는 point / 특징을 잘 반영하는 알고리즘이 각각 있음

 

1. partional Algorithms(ex. K-means)

k개의 그룹으로 분할

어떤 instance가 여러 그룹에 동시에 군집화되진 않음

 

K-means

• Assignment step

- 각 데이터 포인트를 가장 가까운 중심점을 가진 클러스터 에 할당됨

- 각 데이터 포인트는 정확히 하나의 클러스터에 할당됩니다.
• update step

- 클러스터 내 데이터 포인트의 평균을 새로운 중심점으로 계산합니다.

 

이 프로세스는 수렴(convergence)이 될 때까지 반복됩니다.
• 수렴:
- 중심점이 더 이상 변하지 않을 때
- 클러스터 할당이 더 이상 변하지 않을 때
- 두 연속적인 단계에서의 중심점 사이의 유클리드 거리가 어떤 작은 양의 값보다 작을 때 알고리즘을 중지할 수 있습니다.

 

군집 개수를 정확히 모르면 실제 data에서의 군집 개수를 모르면

실제 군집과 설계한 군집에 대한 차이가 있을 수 있음 => 정확한 군집의 개수를 주는 것이 중요

 

k means 를 돌수록 centroid가 바뀜 => 변화가 없을 때까지 돌림

 

Convergence:

– Whether centroids are no longer changing

– Equivalent to clustering assignments not changing

– The algorithm can be stopped when the Euclidean distance between the centroids in two consecutive steps is less than some small positive value

 

K means의 기본만 알면됨 71p 부터 볼 필요 없음 !(감사..)

 

Unsupervised Learning Evaluation

• Evaluation without ground truth

 

일관성 (Cohesiveness): 일관성 있는 군집은 동일한 군집 내의 인스턴스들이 서로 가까운 위치에 있음을 의미합니다. 다시 말해, 같은 군집에 속한 인스턴스들은 다른 군집에 속한 인스턴스들에 비해 서로 유사하거나 비슷한 패턴을 가지고 있습니다. 높은 일관성은 같은 군집 내의 인스턴스들이 유사한 특성을 공유하거나 비슷한 패턴을 나타내는 것을 나타냅니다.

분리도 (Separateness): 분리도는 서로 다른 군집 간의 분리 정도를 나타냅니다. 잘 분리된 군집은 서로 구분되어 있고 겹치는 부분이 적습니다. 높은 분리도는 서로 다른 군집들이 서로 다른 특성을 가지고 있고, 공통적인 인스턴스나 특성이 적다는 것을 나타냅니다.

Cohesiveness - 얼마나 밀집되게 뭉쳐있는가 / 값이 작으면 작을수록 밀집되어 있음

Separateness - 서로 다른 군집간의 거리가 얼마나 먼가(분리되어있나)

전체 data에 대한 center 와 / 각 centroid의 거리를 구하라 /클수록 좋음

하나로 합친 게 실루엣 계수 1에 가까울 수록 군집 잘됨 -1에 가까울수록 군집 안됨

 

Silhouette Index

우리는 일관성과 분리도가 모두 높은 군집을 원합니다.

실루엣 지수(Silhouette index)
• 같은 군집 내의 인스턴스들 간의 평균 거리와
• 서로 다른 군집 내의 인스턴스들 간의 평균 거리를 비교합니다.
• 잘 군집화된 데이터셋에서는, 같은 군집 내의 인스턴스들 간의 평균 거리가 작아야 함 (일관성)
서로 다른 군집 내의 인스턴스들 간의 평균 거리가 크거나 먼 거리에 있어야 함 (분리도)

 

실루엣 계수 전까지 시험