NAIAHD

그래프 이론

그래프 : 

그래프 라고 하면 막대그래프나 파이 그래프 등 표 형식의 데이터를 그림으로 나타낸 것을 연상하는 분을 많을 겁니다. 

그러니 여기에서 말하는 그래프는 점과 선을 연결한 것을 의미합니다. 

점을 꼭지점, 정점 Vertext, 노드 node라고 하면 , 선을 변 또는 간선 Edge이라고 합니다. 

연결 그래프 : Connected Grapah : 모든 정점 사이를 연결한 (경로가 존재하는)그래프

비연결 그래프:

고립 정점 Isolated vertex: 어떤 정점도 연결되지 않은 정점

평행 변 Parallel edge: 그래프에서 정점 2개가 2개 이상의 변으로 연결되는 변 

양 끝이 같은 변 self-loop: 1개의 정점에 시작과 끝이 연결된 변이 존재하면 

무향 그래프:

유향 그래프: Directed Graph :

그래프의 변에 방향이 존재하면 

특히 어떤 정점에서 출발 한 후 해당 정점에 돌아오는 경로가 하나인 그래프는 유항 비순환 그래프 directed acylic graph, DAG

무향 그래프 : Undirected graph 

변에 방향이 존재하지 않는 그래프는 무향 그래프 

가중 그래프 Weighted Graph : 유향 그래프 중 가중치 정보가 추가된 그래프는 

변에 가중치 숫자를 적어 가중치를 표현합니다. 

변에 숫자를 적는 것 외에 선의 굵기로 가중치를 나타낼 수 도 있다. 

간선 가중 그래프 : 가중치는 정점에도 적을 수 있으므로 변에 가중치를 나타내면 간선 가중 그래프 Edge-weighted Graph

정점 가중 그래프 : Vertex-Weighted Graph: 정점에 가중치를 나타내면

그래프의 행렬 표현 :

인접 행렬 Adjacency matrix: 정점 사이의 관계를 나타내는 행렬

근접 행렬 incidence matrix: 정점과 변의 관계를 나타내는 행렬

20211121

트리 구조 그래프 :

그래프에 있는 여러 개 정점에서 출발점이 되는 정점으로 돌아가는 경로가 유일하며, 출발점이 되는 정점이 막다른 정점(더는 새로운 변을 통해 이동할 수 없는 정점)인 그래프를 트리 구조라고 합니다. 

출발점이 있는 정점은 루트Root(뿌리)라고 합니다. 

20211122

그래프 탐색과 최적화

탐색 트리 구축: 

이진 탐색 트리 

깊이 우선 탐색 Depth-first search DFS: 루트 노드에 연결된 경로 중 하나를 선택해 막다른 노드에 도착할 때 까지 일단 탐색한 후 , 다시 바로 앞 노드로 이동해 다음 막다른 노드까지 탐색을 반복합니다. 

너비 우선 탐색 Breath-first search BFS:루트 노드와 연결된 노드를 모두 탐색한 다음 바로 다음에 깊이의 노드들을 전부 탐색하는 과정을 반복합니다. 

20211123

탐색 트리의 탐색에 필요한 목록:

1. 탐색 대상 노드와 연결된 주변 노드를 포함하는 탐색 노드의 목록 : 오픈 리스트

2. 탐색을 종료한 노드의 목록 : 클로즈드 리스트 , 클로즈드 리스트에 도달 목표 노드가 포함되면 탐색을 종료합니다. 

깊이 우선 탐색은 노드를 오픈 리스트의 맨 위에 추가해 첫번째 노드부터 차례대로 탐색합니다. 

LIFO

FIFO

20211125
동적계획법:Dynamic Programming

출처 : 처음 배우는 인공지능

신경망과 베이즈 네트워크 등을 이용해 데이터를 분석하려면 그래프 네트워크를 알야야 합니다.

01. 그래프 이론

그래프 라고 하면 막대 그래프나  파이 그래프 등 표 형식의 데이터를 그림으로 나타낸 것을 연상한는 분이 많을 겁니다.

그러나 여기에서 말하는 그래프는 점과 선을 연결한 것을 의미합니다.

점을 꼭지점, 정점Vertex, 노드 라고 하며 ,선을 변 또는 간선 Edge이라고 합니다.

모든 정점 사이를 연결한(경로가 존재하는 ) 그래프를 연결 그래프 connected graph그렇지 않은 것을 비연결 그래프라고 합니다. 어떤 정점도 연결되지 않은 정점을 고립 정접Isolated vertex이라고 합니다.

그래프에서 정점 2개가 2개 이상의 변으로 연결되는 변은 "편행 변Parallel edge"이라고 합니다.

1개의 정점에 시작과 끝이 연결된 변이 존재하면 " 양 끝이 같은 변 self-loop'입니다.

무향 그래프와 유향 그래프 

유향 그래프direced graph 그래프의 변에 방향이 존재하면 

특히 어떤 정점에서 출발 한 후 해당 정점에 돌아오는 경로가 하나인 그래프는 유향 빈순회 그래프 Directed acyclic graph, DAT라고 합니다. 

변에 방향이 존재하지 않는 그래프는 무향 그래프 Undirected graph라고 합니다.

가중 그래프 Weighted Graph: 유향 그래프 중 가중치 정보가 추가된 그래프

간선 가중 그래프 Edge-Weighted Graph가중치는 정점에도 적을 수 있으므로 변에 가중치를 나타내며 간선 가중 그래프

정점에 가중치를 나타내면 정점 가중 그래프 Vertex-Weighted Graph라고 합니다.

그래프의 행렬 표현

인접행렬 adjacency matrix: 정점 사이의 관계를 나타내는 행렬입니다.

  정점 수가 n일 때 n*n행렬이며 정점 사이가 변으로 연결되어 있으면 1, 연결되어 있지 않으면 0이 됩니다.

근접행렬 incidence matrix: 정점과 변의 관계를 나타내는 행렬입니다.

  변수가 m일 때 n*m행렬이며 정점과 변이 연결되어 있다면 1, 연결되어 있지 않으면 0이 됩니다.

트리 구조 그래프

그래프에 있는 여러 개 정점에서 출발점이 되는 정점으로 돌아가는 경로가 유일하며 , 출발점이 되는 정점이 막다른 정점(더는 새로운 변을 통해 이동할 수 없는 정점)인 그래프를 트리 구조라고합니다.

출발점이 되는 정점은 루드 Root(뿌리)라고 합니다

의사결정트리는 통계 모델 예측을 위한 조건 분기에 사용되는 규칙으로 사용합니다.

탐색 트리는 상태(조건이 포함된 정보 구조)를 나누는 수단으로 사용합니다.

02. 그래프 탐색과 최적화

탐색 트리 구축

이러한 최적 경로 탐색은 현재 시간 t에 해당하는 상태에 어떤 행동을 했을 때 얻을 수 있는 이익이나 지불 비용을 계산해 다음 시각인 t+1의 상태를 결정하는 것과 같습니다. 이 과정을 반복 실행하면 목적지에 도달했을 때 시간인 T의 이익을 최대화하거나 비용을 최소화하는 계획 문제로 다룰 수 있습니다. 이러한 계획 문제를 단단계(의사)결정 문제라고 합니다.

이진 탐색 트리 binary search tree:  인덱스 정렬된 데이터를 반으로 나눠 저장하는 작업을 반복해 트리구조를 만든 후 원하는 데이터를 빠르고 효율적으로 찾습니다. 

탐색 트리 추적방법

깊이 우선 탐색Depth-first search DFS : 루트 노드에 연결된 경로 중 하나를 선택해 막다른 노드에 도착할 때 까지 일단 탐색한후 , 다시 바로 앞 노드로 이동해 다음 막다른 노드까지 탐색을 반복합니다.

너비 우선 탐색 Breadth-first search , BFS: 루트 노드와 연결된 노드를 모두 탐색한 다음 바로 다음에 깊이의 노드들을 전부 탐색하는 과정을 반복합니다.

노드들 넣는 상자를 스택이라고 합니다.

노드를 넣는 상자를 큐라고 합니다.

효율적인 탐색 방법

비용에 따른 탐색 방법

게임 트리를 전략에 이용하는 방법

동적 계획법

03. 유전 알고리즘

유전 알고리즘구조

생물이 살아가면서 교차 , 돌연변이 도태 등으로 환경에 적합하도록 진화한다는 가설에 기반을 둔 최적화 기법을 유전 알고리즘이라고 합니다.

이 과정에서 교차와 돌연변이 등 진화론 아이디어를 도입한 계산 방법을 진화연산이라고 합니다.

진화연산은 다음 특징이 있습니다.

집단성 : 개체 다수를 집단으로 설정해 동시에 탐색할 때는 병렬 연산합니다.

탐구 가능성 : 탐색 공간(설명 변수와 목적 변수 등이 취할 수 있는 값의 법위)의 자세한 사전 지식을 요구하지 않습니다.

다양성 : 집단에 있는 개체의 다양성으로 노이즈와 동적 변화에 적응성을 갖게 되므로 견고한 답을 얻을 수 있습니다.

유전 알고리즘 용어와 알고리즘 흐름

도태(선택) 개체를 남기는 처리 유전 알고리즘에서 적합도가 높은 개체를 선택해 남기면 다음 세대가 되었을 때 집단 안에서 더 최적 해결책에 가까운 개체가 많아지는 상태를 만들 수 있습니다.

교차 개체 2개에서 자식 둘을 생성하는 처리 부모의 유전자를 재조합해 자식 둘을 생성하는 것

돌연변이 개체 1개의 유전자를 변화시키는 처리 부모의 유전자를 재조합해 자식 한 명을 생성하는 것으로 적합도를 높인다는 기준으로 개체를 다루는 도태나 교차와 달리 무작위 탐색에 가깝습니다.

유전 알고리즘의 사용예:

외판원 문제 Traveling salesman problem TSP

복수 지점을 한번 만 통과하는 최단거리(또는 최단시간)을 이동해 출발점으로 돌아오는 경로를 계산하는 조합 최적화 문제

04. 신경망

헵의 법칙과 형식 뉴런

신경망 : 신경 세포(뉴런_는 다른 신경 세포에게 전기 신호를 받았을 때 전기 신호가 일정 기준을 넘으면 다음 신경 세포로 신호를 전달합니다.

헵의 법칙Hebb : 시냅스의 유연한 연결, 즉 가소성 있는 변화를 의미하며 실제로 일어난다는 사실이 나중에 밝혀졌습니다. 

신경망

계층

입력계층 -> 출력 계층

입력계층 -> 중간계층 -> 출력계층

계층: 신경망에서는 같은 종류의 형식 뉴런을 여러 개 병렬로 배열해 유닛을 형성하는 것

활성화 함수 :

형식 뉴런에서 받은 입력값을 출력할 때 일정 기준에 따라 출력값을 변화시키는 비선형 함수를 활성화 함수라고 합니다.

단위 계단 함수

시그모이드 함수

계단 함수

퍼셉트론

볼츠만 머신 : 각 노드가 양방향으로 연결된 신경망 구조를 제압합니다. 

이웃 노드가 받은 자신의 출력값을 다시 자신이 받는 피드백 메커니즘이 동작한다는 것이 핵심입니다.

요차역전파법backpropagation : 

다층 퍼셉트론: 입력 계층과 출력 계층만 있는 간단한 퍼셉트론의 약점은 선형 분리할 수 있는 데이터에만 적용할 수 있으며 계산 시간이 길다는 것입니다.

다층 퍼셉트론에서는 순방향으로 계층마다 출력을 계산한 후 오차역전파법을 이용해 출력 계층에서 역방향으로 가중치 업데이트를 실행합니다.

자기조직화 self-organization: 신경망의 학습 과정에서 네트워크가 데이터 입력과 출력 후의 가중치를 업데이트해서 스스로 일관성 있게 변화해 나가는 것

05. 텐서플로를 이용한 신경망 만들기 예제 

필요한 모델 이불러오기

import tensorflow as tf
import numpy as np

MNIST 데이터 다운로드하기

학습용 데이터 : 55,000

검증용 데이터 5,000

테스트용 데이터 10,000

이미지와 라벨 쌍으로 구성합니다.

from tensorflow.examples.tutorials.mnist import input_data
mnist = input_data.read_data_sets('./data/mnist/',one_hot = True)

뭔가 이상한것 나왔을 경우 다시 실행하면 된다.

결과

one_hot True로 설정한다.

Mnist 데이터 살펴보기

print(len(mnist.train.labels))
print(len(mnist.train.images))

print(mnist.validation.num_examples)
print(mnist.test.num_examples)

mnist.test.labels.shape

(10000, 10)

mnist.test.labels[0:5,:]

mnist.test.cls = np.argmax(mnist.test.labels, axis = 1)
mnist.test.cls[0:5]

array([7, 2, 1, 0, 4], dtype=int64)

하이퍼파라미터 설정하기

num_epochs = 30
learning_rate = 0.01

num_node_input = 28 * 28 #입력 계층의 노두 개수
num_node_hidden1 = 256 # 은닉 계층 1의 노드 개수
num_node_hidden2 = 256 #은닉 계층 2의 노드 개수
num_node_output = 10 # 출력 계층의 노드 개수

모델 만들기

입력 계층

x_true = tf.placeholder(tf.float32, [None, num_node_input])
y_true = tf.placeholder(tf.float32, [None, num_node_output])

은닉 계층 1

weight_1 = tf.Variable(tf.truncated_normal([num_node_input, num_node_hidden1], stddev = 0.01))
bias_1 = tf.Variable(tf.zeros([num_node_hidden1]))

은닉 계층 2

weight_2 = tf.Variable(tf.truncated_normal([num_node_hidden1, num_node_hidden2], stddev = 0.01))
bias_2 = tf.Variable(tf.zeros([num_node_hidden2]))

출력 계층

weight_3 = tf.Variable(tf.truncated_normal([num_node_hidden2, num_node_output], stddev = 0.01))
bias_3 = tf.Variable(tf.zeros([num_node_output]))

hidden_1 = tf.nn.relu(tf.add(tf.matmul(x_true, weight_1), bias_1))
hidden_2 = tf.nn.relu(tf.add(tf.matmul(hidden_1, weight_2), bias_2))
y_pred = tf.nn.relu(tf.add(tf.matmul(hidden_2, weight_3), bias_3))

cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(logits = y_pred, labels = y_true))
optimizer = tf.train.AdamOptimizer(learning_rate).minimize(cost)

cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits_v2(logits = y_pred, labels = y_true))
optimizer = tf.train.AdamOptimizer(learning_rate).minimize(cost)

학습하기

세션을 실행

sess = tf.Session()
sess.run(tf.global_variables_initializer())

batch_size = 100
total_batch = int(mnist.train.num_examples/batch_size)

for epoch in range(num_epochs):
    total_cost = 0
    
    for i in range(total_batch):
        batch_xs, batch_ys = mnist.train.next_batch(batch_size)
        sess.run(optimizer, {x_true: batch_xs, y_true: batch_ys})
        total_cost += sess.run(cost, {x_true: batch_xs, y_true: batch_ys})
        
    print("Epoch : {%04d}" % (epoch+1), "Cost : {:.3f}".format(total_cost / total_batch))

print("최적화를 완료했습니다.")

평가하기

correct_prediction = tf.equal(tf.argmax(y_pred,1), tf.argmax(y_true,1))
accuracy = tf.reduce_mean(tf.cast(correct_prediction , tf.float32))
print("정확도 : " , sess.run(accuracy, {x_true: mnist.test.images, y_true: mnist.test.labels}))

정확도 : 0.7453

출처 : 처음 배우는 인공지능