yongmin

Data Mining Definition

정의 : bigdata로부터 의미있고 상관관계, 패턴, 경향을 찾아내는 프로세스

background : data의 양은 증가함에도 불구하고 분석과 예측에 사용되는 유용한 정보는 브적

Comprehensive study

database technology

statistics

viusalization

AI

information science

machine learning

data mining and intelligent business

end user : making decisions

business analyst : data presentation, viusalization techniques

data analyst : data mining, information discovery, data exploration, data warehouses

dba : data sources

process of data mining

problem definition

data exploration

data preparation

mdeling

Supervised data vs Unsupervised data

- supervised data : training data는 input과 그에 대한 output값이 라벨링이 되어 있는 targets를 포함

supervised leanring : supervised data와 계산되는 error를 이용하여 모델을 학습

unsupervised data : input에 대해 output값이 라벨링 되어 있지 않는 data

Supervised data prediction

decision tree

neural network

regression analysis

logistic regression

case-based reasoning

Unsupervised data prediction

- association rule discovery

market basket analysis

clustering

Techniques of data mining

association rule

- sequential pattern

clustering

Association rule

Support, Confidence등을 통해서 공통적인 규칙을 찾아나간다.

Support(지지도) - 전체 경우의 수 중 관계를 설정하기 위한 상품들이 동시에 발생될 확률.

- Confidence(신뢰도) - 특정 상품이 선택되었을 경우 다른 상품이 선택될 확률.

Sequential pattern

Orderd data: 데이터 개체의 속성이 시간적인 순서와 연관되는 데이터 집합 (ex) customer shopping sequences)

orderd data에서 연속되는 패턴을 발견한다

Clustering

data들에 대한 사전 정보가 없는 경우, data들 사이의 유사성 을 이용하여, 전체를 몇 개의 집단으로 그룹화

cluster(그룹) 내부의 member들은 다른 cluster의 member들 보다 유사점이 많다

K-mean algorithm

정의 : K Mean Clustering Algorithm은 임의의 데이터 집단을 K개의 Cluster로 나누어주는 알고리즘

과정

1. Clustering 하고자 하는 K를 결정한다.

2. K가 결정되면 그 K개의 수만큼의 임의의 중심점 C를 결정한다. => C1, C2 , C3 ....., Ck

3. 각 중심에서 각 데이터의 거리를 계산하고 가장 가까운 것들을 그 데이터그룹에 소속시킨다.

ex) C1에 가장 가까운 데이터들은 Group 1, Ck에 가장 가까운 데이터들은 Group K.

4. 각 그룹에 대하여 다시 새로운 중심값을 계산한다.

ex) 1그룹에 속한 모든 데이터의 평균을 통해 중심값을 계산하고 그것을 새로운 C1이 되게 한다.

5. 새로운 중심값으로 부터 3번과정(Regroup)을 실행한다.

6. 데이터의 그룹이 변하지 않을 때 까지 3~5번 과정을 반복한다.

web 1.0 과 2.0

- web 1.0 : 사용자는 컨텐츠 열람(단방향)

- web 2.0:사용자가 직접 컨텐츠 생성 및 공유에 참여 (양방향)

Web vs Semantic Web

Web : linked documents

- Semantic Web : 컴퓨터가 사람을 대신하여 정보를 읽고 이해하고 가공하여 새로운 정보를 만들어 낼 수 있도록, 이해하기 쉬운 의미를 가진 차세대 지능형 웹

resources : 인터넷 사전, 위키백과, 인터넷 정보

Distributing Data

why? : distribution solutoin은 flexibility를 제공

Staregies

1. row by row

2. column by column

3. cell by cell

Cell by Cell

row by row 와 cell by cell을 곱한 형태로 양쪽의 장점을 모두 갖는다

각각의 cell은 3가지 value로 나타내어진다

1. global reference for the row

2. global reference for the column

3. the value in the cell itself

Knowledge Representation

지식을 표현, 관리하는 방법론

사실과 관계성 등을 부호화하고 지식 베이스에 저장하는 방법

example

1. production rule : ‘IF A THEN B’ 형식의 추론 규칙

2. RDF : 웹에서의 knowledge representation

RDF (=Resource Description Framework)

semantice web을 구현하기 위한 knowledge representation(지식표현)기법 중의 하나

RDF는 cell by cell 형태

RDF의 cell 하나는 3가지 value(Subject, Predicate, Object)를 나타내는데 이 cell을 triple 이라고 한다.

RDF는 directed graph로 표현 가능. 이때 graph를 knowledge graph라고 한다

Merger

RDF 형식으로 data를 생성, 저장, 공유하면 RDF를 graph로 구조화 할 수 있다.

구조화된 graph들을 SPO관계에 따라 merge 함으로써 모든데이터를 참조 가능

Inference(추론) in Semantic Web

Game Playing에 AI를 적용하는 이유

인간과 바로 비교할 수 있다

game play은 non-trivial

game is well defined and repeatable

game is limited and accessible

One-Ply Search

내가 선택 가능한 case들을 대상으로 evaluation function으로 평가

나에게 제일 유리한 case 선택 => max

Two-Ply Search

내가 선택 가능한 case들을 계산하고, 이후 상대방이 선택 가능한 case들까지 계산하여 evaluation fuction으로 평가

상대의 case들 중에서 나에게 제일 치명적인 것을 선택 => min

나에게 치명적인 것들 중에서 나에게 제일 유리한 것을 선택 => max

어차피 지는 경우라면 mini-max 알고리즘이 아닌 다른 알고리즘 적용

Mini-Max Algorithm

예상되는 최대의 손실(maximum loss)를 최소화 (minimize) 시키기 위해 사용되는 의사 결정 이론의 한 방법

해당 문제에서 탐색이 끝나면 탐색트리로 부터 최상이라고 추정되는 행동을 찾기 위해, 탐색트리의 단말(leaf) 노드에 정적 평가 함수 (static evaluation function)로 추정값을  얻고 그 단말노드의 가치를 통해 최상의 행동을 찾음

Alpha-Beta Pruning (알파-베타 가지치기)

Mini-max 알고리즘에 의해 평가되는 노드들의 수를 감소시키기 위한 기법

- Alpha Cutoff : 최소값에 의한 pruning

- Beta cutoff : 최대값에 의한 pruning

Alpha Cutoff (=Alpha pruning)

minimizing ply에서 일어남

ex) B가 3을 보장하는 상황에서, C의 가능 case중 –5인 case가 존재하면 C의 남은 case들은 연산할 필요 x
-> -5보다 작은 경우가 있으면 minimizing ply이므로–5 보다 작은 case 선택 되어 C<-5, B=3이므로 결국 B가 선택
-> -5보다 큰 경우가 있으면 minimizing ply이므로 C=-5, B=3 이므로 결국 B가 선택

Beta Cutoff (=Beta pruning)

maximizing ply에서 일어남

B = -5 일 때, C의 가능 case중 7이 존재하면 C의 남은 case들은 연산할 필요 x
-> 7보다 작은 경우가 있으면 maximizing ply이므로 C=7, B=5이므로 결국 B가 선택됨
-> 7보다 큰 경우가 있으면 maximizing ply이므로 C>7, B=5이므로 결국 B가 선택됨

Alternatives to Mini-Max

어차피 지는 게임에서는 Mini-Max 알고리즘 대신 다른 알고리즘 적용

Search Techniques

Blind : near optimal은 고려하지 않고 decision을 결정
- DFS (depth first search)

- BFS (breadth first search)

Heuristic : near optimal인 경우 decision

- Hill climbing

- Best-first search

- greedy search

- A* search

Generate-and-Test

generator가 possible solution을 생성

tester가 actual solution인지 확인

  - incorrect solution –> generator가 다시 possible solution 생성

  - correct solution -> stop

Hill climbing

-> new state가 goal state이거나 current state보다 좋으면 선택

evaluate the initial state.

Loop until a solution is found or no new operators left

    select an operator and produce a new state

    evaluate the new state

        if it is a goal state -> quit

        if it is not a goal state but it is better than the current state, then make it the current state

        if it is not better than the current state, continue the loop

Steepest-Ascent Hill Climbing

가능한 new sate들 중 제일 좋은 new state을 선택

문제점 : goal state에 도달하려면 worse state를 선택해야 하는데, Steepest-Ascent Hill Climbing에서는 worse state 선택 x

Best-first Search

현재 open된 노드들 중에 f’이 최선인 것을 우선적으 로 검색

Greedy best-first search

open된 모든 node들을 고려하는 것이 아니라, 당장 눈 앞에 보이는 최선을 따라서 탐색

loop에 빠질 수 있다.

optimal 하지 않다

A* search

출발 노드부터 목표 노드까지의 최적경로를 탐색

f(n) = g(n) + h(n)

- f(n) : 출발 노드에서 시작하여 노드 n을 거쳐서 목표 노드까지 도달하는 비용

- g(n) : 출발 노드로 부터 노드 n까지의 경로비용 (현재 경로까지 확정 비용)

- h(n) : 노드 n으로 부터 목표 노드까지의 경로비용 (현재부터 goal 까지 확정 비용)

f(n)이 최소인 노드를 따라 탐색하면, 최소 비용의 경로를 탐색

- h(n)은 아직 탐색하지 않은 경로이므로 정확히 계산하기 어렵거나 불가능함 -> 경험적 규칙 사용

Intelligent Software Agent

사람을 대신해서 업무를 수행하는 소프트웨어

- Agent가 Sensor를 통해 Enviroment에서 percept 하여서 actuator를 통해 Action이 취해진다.

- Formulate Goal, Formulate problem, Find Soultion : Agent는 목표와 문제를 구체적으로 설정하고 해결책을 찾아야 한다.

Intelligent Software Agent의 4가지 특징

autonomy : Agent는 자율적으로 동작 해야한다.

social ability : 다른 Agent와 상호작용 해야한다.

reactivity(반응성) : 주변 상황이나 다른 agent의 행동 변화를 인식하고 적절한 대응을 해야한다

proactivity(능동성) : 주어진 목적에 따라 정보를 수집하고 작업을 수행 해야한다

Symbolic AI

명시적인 규칙을 충분하게 많이 만들어 지식을 다루면 인간 수준의 인공 지능을 만들 수 있다.
=> 데이터가 존재하지 않으며, 컴퓨터 작동 방식에 맞게 지식을 논리와 기호로 표현

솔루션은 explainable(설명가능) 하다.

Production System

- 규칙을 기반으로 하는 시스템 ,

- Rule을 기반으로 인간 문제 해결방법을 모델링 하는데 그 의의가 있다.

Global database : short-term memory 라고도 하고, 시스템에서 다루는 세계의 현재 상태를 표현

Production rule : long-term memory이다. 생성시스템에 기억된 룰들이다.

Control System : 룰들은 이 컨트롤 시스템에 기초하여 효과적으로 적

Production System

data = initial state

While(data != termination condition)

Begin

Select some rule R in the set of rules // Control system에 기반하여 rule 선택

Apply it

data = result of applying R to data

End

Control Strategies

pick the first rule

pick one rule ar random

Depth-first search

Breadth-first search

Heuristic Search

decision을 할 때 가능한 case를 모두 search 하지 않고, 특정 case마다 heuristic evalutaion function을 사용하여 evaluation을 구하고 near optimal의 case를 선택함으로써 search space를 줄여 효율성을 높이는 기법

ex) 8-puzzle 문제에서 Manhatten distance heuristic 사용

Problem characteristics

decomposable

ignorable

recoverable / irrecoverable

predictable

absolute / relative

the role of knowledge

does the task require interaction with a person?

CNN 개요

컨볼루션 신경망은 입력된 이미지에서 “feature(특징)”을 추출하기 위해 filter(=mask)를 도입하는 기법

input의 다양성 : Trickier cases

translation : 치우침

scaling : 사이즈가 크고 작음

rotation : 회전

weight : 두께

input이 위와 같이 다양하기 때문에 부분을 나누어서 부분별 feature 파악

convolution layer

input과 filter(=kernel)를 합성곱을 하여 input 데이터의 feature를 추출한다.

여러개의 filter를 이용하여 많은 feature들을 추출 => feautre Map이 형성 됨

- 활성화함수로 ReLU를 이용 : 추출된 값들 중에 음수는 0으로 설정

cnn parameter : 입력채널 x 필터폭 x 필터 높이 x 출력 채널

pooling

convolution layer에서 추출한 feature의 사이즈를 축소시키는 과정을 poolig 이라고 한다.

average pooling : 정해진 구역 안에서 평균값을 도출

max pooling : 정해진 구역 안에서 최댓값을 도출

Deep stacking

convolution layer와 Pooling layer를 여러번 반복함으로써 처음에는 작은 부분의 특징을 찾고 점점 큰 부분의 특징을 찾을 수 있다.

Flatten

convolution layer, pooling layer를 지나 Fully connected layer에게 데이터를 전달해야 하는데,
convolution layer와 pooling layer는 2차원 배열을 다루고 fully connected layer는 1차원 배열을 다루므로
2차원 배열을 1차원 배열로 변환한다

CNN Architectures

AlexNet : ReLU와 dropout 사용

VGG Net : 3x3 filter 사용

GoogLeNet : inception 모듈을 사용하고, fully connecy layer 대신 average pooling layer를 사용하여 획기적으로 파라미터 수를 감소

분류(classification)와 예측(prediction)

분류 : 데이터들을 특정 기준으로 나눌 수 있는 ‘선형구분자’를 설정하여 분류. 오차를 이용하여 구분자의 기울기를 조정하는 것을 ‘학습’이라고 한다.

- Error = target – actual

Learning rate(L) : 학습률은 업데이트의 정도를 저장

update parameter : new A = A + dA = A + L(E/x).

예측 : 새로운 data가 들어오면 구분자에 의해 어떤 output으로 분류될지 판단 => 예측과 분류는 다른 것이 아님

XOR 문제의 경우 선형분류자는 하나가 아니다 -> 여러개의 선형 분류자를 이용 -> 인공신경망은 여러개의 분류자가 함께 동작

인공신경망

인공뉴런은 X1부터 Xn까지 입력 값에 각각 W1부터 Wn까지의 가중치를 곱하고 그 모든 합이 임계치(threshold)가 초과되면 출력값이 발생

activation functoin(활성화 함수) : 여러 입력신호를 받아 특정 threshold를 넘어서는 경우에 출력 신호를 생성하는 함수 -> sigomoid 함수(=logistic 함수)가 대표적이다. => y = 1 / (1+ e^-x)

인공신경망 : 상호연결된 생물학적 뉴런을 인공적으로 모델화 한 것으로, 다수의 인공뉴런을 가지고 있는 layer를 여러 층으로 쌓은 후 이전 layer와 이후 layer의 모든 인공뉴런들이 연결되어 있다. 이때 각각의 연결에 weight(가중치)가 존재하는데 학습과정을 통해 weigjt값들을 조정함으로써 input에 대해 올바른 output이 나올 수 있도록 한다.

신경망에서 신호를 전달하는 연산은 행렬곱을 통해 표현

forward propagation : output = sigmoid(X1*W1 + X2*W2 + ... + Xn*Wn)

인공신경망에서의 학습

- 입력 값을 이용하여 인공 뉴런의 출력 값을 계산

- 인공 뉴런이 계산한 출력 값과 사용자가 기대하는 출력 값을 비교. => Error = target – actual

back propagation : error 정보가 뒤쪽으로 계속 전파

중간 계층에 존재하는 노드들의 오차는 출력계층 노드들의 오차를 가중치에 크기에 비례해 나눠서 back propagation

back propagation은 행렬곱으로 표현 : Error(hidden) = W.T(hidden-output) * Error(output)

가중치 업데이트 : 함수의 최저점을 구하는 Gradient Descent 기법을 학습 목표 값과 실제 값 간의 차이를 구하는 Error function에 적용 -> error function = (target-actual)^2인 이차함수 이므로 error function의 최저점은 error function의 기울기(dE/dw)가 가장 작은 지점 -> dE/dw =
-> new W = old W – (LearningRate * (dE/dw))

AI를 engineering과 science의 관점에서 비교

-AI : 사고과정 + 추론을 통한 지능적 행동에 관련된 연구를 하는 학문

-AI in engineering : 실제 지능적으로 사고, 행동할 수 있는 intelligence machine을 만들기 위해 요구되는 개념이나 이론, 실습 등에 관련된 연구 분야. => 뇌의 작동원리를 모델로 하여 프로그래밍

- AI in science : 사람이나 동물이 자연생태에서 사고하고 행동하는 일련의 과정들을 탐구하고 분석하여 관련된 개념이나 원리를 연구하는 분야 (예-인지과학) => 뇌의 학습, 인지과정의 원리를 이해

분야별 AI

인지과학의 AI : 어떻게 자연상태의 생각과 정신적현상이 동작하는지 이해 => 뇌의 학습, 인지과정의 원리를 이해

철학의 AI : 기본적이고 중요한 철학적인 문제들을 탐험하기위한 방법

AI 구현의 패러다임

Symbolic AI : 고전적인 AI 구현방식. 여러 symbolic knowledg들 사이의 관계와 문법을 연구하고 symbolic 추론을 연구

Connectionist AI : mental state은 neural units을 가지고 있는 n차원 벡터들로 표현되는데, 이런 neural units간의 연결을 matrix를 이용하여 계산한다.

Turing Test

- 기계가 생각하고 있는가를 판정하는 시험 (Alan Turing)

사람과 기계가 대화하는 상황에서, 사람은 대화 상대방이 기계인지 사람인지 알아챌 수 있는지 시험

- 어떻게 해서 지능적인 판단과 행동을 할 수 있는가가 주요 연구 대상 => 인간이 그것이 기계임을 구분하지 못하는 것이 중요한 것이 아니라 인간이 하는 말과 행동에 반응하고 이를 바탕으로 새로운 사실을 추론하는 등, 인간에게 유용하게 사용할 수 있어야 함

Video Turing Test

비디오를 컴퓨터에게 보여주고 비디오의 내용을 컴퓨터에게 물어봤을 때, 캄푸타기 사람만큼 잘 대답하는지 알아보는 시험

AI system

ELIZA : 인공지능 채팅 프로그램

ALICEBOT : 인공지능 채팅 프로그램

Deep blue : IBM이 개발한 chess-playing computer

Watson : IBM이 개발한 퀴즈 답변 인공지능 시스템. 자연어처리, 정보검색, 지식표현, 지식추론, 기계학습 응용시스템

AlphaGo : google deepmind가 개발한 바둑 인공지능 프로그램. 실시간 decision-making 기능. MinMax 알고리즘, Monte Calro Tree Search, CNN 기술사용

Amazon Go : 체크아웃이 필요없는 상점. 컴퓨터비전, sensor fusion, deep learning을 이용하여 구현됨

인공지능 vs 머신러닝 vs 인공신경망 vs 딥러닝

- 인공지능 : 사람의 지능을 모방하여 사람처럼 복잡한 일(인지, 추론, 결정 등)을 할 수 있는 기계를 만드는 것

- 머신러닝 : 인공지능을 구현하기 위한 기법으로, 컴퓨터가 명시적으로 프로그램되지 않고도 대량의 데이터와 알고리즘으로 학습할 수 있도록 하는 것.

- 인공신경망 : 생물학적 뉴런 모델을 수학적으로 모델링한 인공뉴런을 여러개 쌓아서 만든 네트워크.

- 딥러닝 : 머신러닝을 구현하기 위해 사용되는 기술로, 인공신경망을 활용하여 데이터를 학습. => 입력값의 결과와 정답의 차이인 에러를 구하고, 에러를 이용하여 가중치를 업데이트 함으로써 스스로 학습