Computer & Books

이제 전에 얻은 단말 노드의 갯수와 단계의 갯수로 트리 전체를 플롯할 수 있다. def getTreeDepth(myTree):     maxDepth = 0     firstStr = myTree.keys()     secondDict = myTree[firstStr]     for key in secondDict.keys():         if type(secondDict[key]).__name__=='dict':#딕셔너리인지 아닌지 검사             thisDepth = 1 + getTreeDepth(secondDict[key])         else:   thisDepth = 1         if thisDepth > maxDepth: maxDepth = thisDepth     return maxDepth def plotMidText(cntrPt, parentPt, txtString):     xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]     yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]     createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30) def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on     numLeafs = getNumLeafs(myTree)  #this determines...

3.2 매스플롯라이브러리 주석으로 파이썬에서 트리 플롯하기 3.2.1 매스플롯라이브러리 주석  매스플롯라이브러리에는 애너테이션이라는 훌륭한 도구를 포함하고 있다. 이 애너테이션은 그려진 플롯 내에 있는 데이터 점들을 설명할 수 있도록 주석을 추가하는 도구이다. 우리는 주석을 이용하여 트리를 플롯하는 데 사용할 것이다. 우리는 텍스트 상자에 색을 칠할 수도 있고 우리가 좋아하는 형태로 변경할 수도 있다. 텍스트 주석을 가진 트리 노드를 플롯하는 함수를 만들어보자. decisionNode = dict(boxstyle="sawtooth", fc="0.8") leafNode = dict(boxstyle="round4", fc="0.8") arrow_args = dict(arrowstyle=" def plotNode(nodeTxt, centerPt, parentPt, nodeType):     createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',              xytext=centerPt, textcoords='axes fraction',              va="center", ha="center", bbox=nodeType, arrowprops=arrow_args ) def createPlot(inTree):     fig = plt.figure(1, facecolor='white')     fig.clf()     axprops = dict(xticks=[], yticks=[])     createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)   ...

3.1.2 데이터 집합 분할하기 이제 데이터 집합에서 어수선함을 계산하는 측정 방법을 보게 될 것이다. 분류 알고리즘을 작동하기 위해서는 엔트로피를 측정하고 데이터 집합을 분할하며, 분할된 집합의 엔트로피를 측정하고 분할이 올바르게 되었는지 확인해야 한다. def splitDataSet(dataSet, axis, value):     retDataSet=[]     for featVec in dataSet:         if featVec[axis] == value:             reducedFeatVec = featVec[:axis]             reducedFeatVec.extend(reducedFeatVec)             retDataSet.append(reducedFeatVec)     return retDataSet 위 코드에서 .append 와 .extend 는 비슷하지만 완전히 다른 함수이다. 아래의 예제를 보면 이해가 빠를 것이다. 위 분할 함수는 분할하고자 하는 데이터 집합, 분할하고자하는 속성 그리고 반환할 속성의 값을 인자로 갖고 데이터를 분할한다. 이제 데이터 분할 시 가장 좋은 속성을 선택하는 함수를 만들어야한다. def chooseBestFeatureToSplit(dataSet):     numFeatures = len(dataSet[0]) -1     baseEntopy = clacShannonEnt(dataSet)     bestInfoGain = 0.0; bestFeature = -1     for ...

공부를 하다보니 파이썬의 리스트, 튜플, 딕셔너리의 정의나 용도의 혼란이 오기 시작했다. 그래서 정리하려 한다. 1. 리스트  a = [1,2,3,4] 리스트를 만들 때는 위에서 보는 것과 같이 대괄호([ ])로 감싸주고 안에 들어갈 값들은 쉼표로 구분해준다. 리스트는 아무것도 포한하지 않는 빈 리스트일 수도 있고. 리스트 자체를 그 요소로 가질 수도 있다. 즉, 리스트 내에는 어떠한 자료형도 포함시킬 수 있다. 리스트 인덱싱 기본적인 것은 c 언어와 동일하다. 하지만 만약 a= [1,2,3,[4,5,6]] 처럼 리스트 안의 리스트를 갖는 리스트가 존재할 때, a[3] 의 값은 [4,5,6]이다. a[3][1] 의 값은 5 이다. 데이터 핸들링 할 때 많이 쓰이는 것이 a[-1] 이다. a[-1]은 배열의 마지막 값을 가진다. 리스트 슬라이싱 a= "12345" 일 때, a[:2]의 값은 '12'이다. 파이썬은 문자열이 배열 안에 들어가면 자동적으로 슬라이싱된다. a=[1,2,3,4,5] 일 때, a[:]는 12345 모두 출력된다. 슬라이싱에는 : 와 문자열 다루는 법이 c언어와 다르다. 리스트를 더하고 반복하기 a= [1,2,3] 일 때, a*3 의 값은 a=[3,6,9] 가 아니라 a = [1,2,3,1,2,3,1,2,3] 의 값인 반복을 뜻한다. 더하기는 c언어와 같다. 리스트 관련 함수들 append sort reverse index insert remove pop : 히스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다. count extend 2. 튜플 리스트는 [] 지만 튜플은 () 이다. 리스트는 그 값을 생성, 삭제,수정이 가능하지만 튜플은 그 값을 변화시킬 수 없다. 덧셈과 곱셈은 되는데, 뺄셈과 나눗셈은 사용할 수 없고(unsupported operand types), list처럼 i...

의사결정 트리는 스무고개와 비슷하다고 한다. 20개의 질문에서 예/아니오로 답해 결론적으로 질문자가 생각하는 답을 추측하는 것이다. 의사결정 트리의 장점 중 가장 좋은 것은 분류 결과를 사람이 쉽게 이해할 수 있다는 것이다. 마지막으로 우리는 분류기를 만들기 위해 재귀를 사용할 것이며, 매스플롯라이브러리를 사용하여 데이터를 표현할 것이다. 3.1 트리 구조 2학기에 자료구조를 배운 나로서는 더 이상 보고 싶지 않은 트리 구조를 마주하게 됐다... 의사결정 트리를 만들기 위해서는 하나의 최초 의사결정을 만들어야한다. 최초 의사결정은 속성으로 결정된다.  일부 의사결정 트리는 데이터를 바이너리로 분할하지만 여기서는 그렇게 하지 않는다. 4 가지 값을 가지는 속성으로 반할하게 되면 , 데이터는 4가지 방법으로 분할된다. 3.1.1 정보 이득 데이터를 분할하기 전과 후의 변화를 정보 이득이라고 한다.  어떤 속성으로 데이터를 분할할 때 가장 높은 정보 이득을 취할 수 있는지를 모든 속성에 대해 확인하며서 분할할 수 있게 된다. 데이터 집합에 대한 정보 측정 방법을 새넌 엔트로피 또 엔트로피라고 한다. l(xi) = log2p(xi) p(xi)는 xi 라는 분류항목이 선택될 확률이다. 여기서 k 는 분류 항목의 개수이다. 파이썬에서 이것을 계산하는 방법을 알아보도록 하자. from math import log def calcShannonEnt(dataSet):     numEntries = len(dataSet)     labelCounts ={}     for featVec in dataSet:         currentLabel = featVec[-1]         if currentLabel not in...

knn을 배워서 책의 필기체 검사하는 코드를 토대로 캐글 101 중 필기체 검사를 해보았다. 결국 혼자의 힘으로는 해내지 못했다.. 아직 파이썬 기술이 많이 부족하다는 것을 깨닫고 캐글에 올라와있는 스크립트 중에 knn을 사용하고 있는 스크립트를 갖고 돌려봤다.. 파이썬이랑 그런지 엄청 오래 걸린다.. 또 다른 스크립트들을 보면서 느낀 건 딥러닝이 너무 우세하다는 것이었다.. from numpy import * import pandas as pd from sklearn.neighbors import KNeighborsClassifier from sklearn.metrics import accuracy_score train_data = pd.read_csv( "C:/Users/llewyn/Downloads/train.csv" ) test_data = pd.read_csv( "C:/Users/llewyn/Downloads/test.csv" ) print ( "train data shape is : " , train_data.values.shape) print ( "test data shape is : " , test_data.values.shape) trainY = ravel(train_data.values[: 10000 , 0 ]) trainX = train_data.values[: 10000 , 1 :] trainX[trainX > 0 ] = 1 print ( "trainX[0] is :" ) print (trainX[ 0 ].reshape(( 28 , 28 ))) validY = ravel(train_data.values[ 40000 : , 0 ]) validX = train_data.values[ 40000 : , 1 :] validX[validX > 0 ] = 1 print ( "validX[0] is :" )...

2.3 예제 : 필기체 인식 시스템 2.3.1 준비 : 이미지를 검사 벡터로 변환하기 32 x 32 로 이루어진 바이너리 이미지를 1 x 1024 벡터로 만들어야한다. 이미지를 하나의 벡터로 만드는 img2vector 함수를 보자. def img2vector(filename):     returnVect = zeros((1,1024))     fr = open(filename)     for i in range(32):         lineStr = fr.readline()         for j in range(32):             returnVect[0,32*i+j] = int(lineStr[j])     return returnVect 2.3.2 검사 : 필기체 번호에 kNN 적용하기 우리는 하나의 형태로 변환된 데이터를 가지게 되었으며, 이 데이터를 분류기로 처리할 수 있게 되었다. 책 소스코드에 있는 handwritingClassTest() 함수를 추가한다. def handwritingClassTest():     hwLabels = []     trainingFileList = listdir('trainingDigits')           #load the training set     m = len(trainingFileList)     trainingMat = zeros((m,1024))     for i in range(m):         fileNameStr = training...

2.2.3 준비 : 수치형 값 정규화하기 서로 다른 범위에 놓여있는 값을 다룰 경우에는 이들을 정규화하는 것이 일반적이다. 정규화 범위는 대개 0에서 1로 정한다. 0에서 1로 모든 것의 크기를 변경하기 위해서는 다음과 같은 공식을 적용해야한다. mewValue = (oldValue - min) / (max- min) autoNorm()이라고 하는 새로운 함수는 자동적으로 데이터를 0과 1 사이의 값으로 정규화하는 함수이다. def autoNorm(dataSet):     minVals = dataSet.min(0)     maxVals = dataSet.max(0)     ranges = maxVals - minVals     normDataSet = zeros(shape(dataSet))     m = dataSet.shape[0]     normDataSet = dataSet - tile(minVals, (m,1))     normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide     return normDataSet, ranges, minVals 2.2.4 검사 : 전체 프로그램으로 분류기 검사하기 기계학습에서 한 가지 공통된 작업은 알고리즘의 성능을 평가하는 것이다.  성능을 평가하는 한 가지 방법은 현재 가지고 있는 데이터의 일부분, 즉 90% 정도를 가지고 분류기의 학습에 사용하는 것이다. 그런 다음 나머지 10%의 데이터를 가지고 분류기를 검사하여, 분류기의 성능이 어느 정도인지 알아본다. 이제 데이트하기 사이트를 위한 분류기 검사 코드를 볼 것이다. def datingClassTest():     hoRatio = 0.10...

2.2 예제 : kNN을 이용하여 데이트 사이트의 만남 주선 개선하기 2.2.1 준비 : 텍스트 파일의 데이터 구문 분석하기 @ 머신 러닝 인 액션에서 첨부 파일로 준 kNN.py 파일을 아나콘다 -> ipython -> Lib 폴더에 넣어야 ipython에서 import kNN을 할 수 있다.  우선 텍스트 파일에 대해 설명하자면 * 연간 항공 마일리지 수 * 비디오 게임으로 보내는 시간의 비율 * 주당 아이스크림 소비량(L) 로 이루어진 텍스트 파일이다. 이제 numpy 구문 분석 코드에 텍스트 기록하기 코드를 보자 def file2matrix(filename):     fr = open(filename)     numberOfLines = len(fr.readlines())         #get the number of lines in the file     returnMat = zeros((numberOfLines,3))        #prepare matrix to return     classLabelVector = []                       #prepare labels return        fr = open(filename)     index = 0     for line in fr.readlines():         line = line.strip()         listFromLine = line.split('\t') ...

두번째 장에서는 k-최근접 이웃 알고리즘에 대해 공부할 것이다. 이 알고리즘은 분류하는 알고리즘인데 예를 들면, 영화 장르를 나누어 영화를 분류하는 것과 비슷하다고 할 수 있다. 그렇다면 어떻게 장르를 구분할 수 있는가? 영화의 장르가 로맨스라면 이성 혹은 동성간의 사랑에 대한 애틋한 장면 혹은 키스 장면들이 다른 장르보다 많을 것이다. 이와 같이 액션 영화라면 발차기가 로맨스보다 많이 나올 것이다. 이렇듯 키스나 발차기 같은 것들을 판단 기준으로 삼는다면 k-nn 알고리즘을 통해 자동적으로 장르를 분류할 수 있을 것이다.  2.1 거리 측정을 통해 분류 kNN의 동작 원리는 이렇다. 1. 기존에 훈련 집합이었던 예제 데이터 집합이 존재한다. 2. 모든 데이터는 분류 항목 표시(Labels)가 붙어 잇으며, 따라서 각각의 데이터가 어떤 분류 한복으로 구분되는지 알 수 있다.  3. 이후 분류 항복 표시가 붙어 있지 않는 새로운 데이터가 주어졌을 때, 기존의 모든 데이터와 새로운 데이터를 비교한다.  4. 그리고 가장 유사한 데이터의 분류항목 표시를 살펴본다. 이 때, 분류 항목을 이미 알고 있는 데이터 집합에서 상위 k개의 가장 유사한 데이터를 살펴보게 된다. (가까운 거리) 5. 마지막으로 k개의 가장 유사한 데이터들 중 다수결을 통해 새로운 데이터의 분류 항목을 결정하게된다. def classify0(inX, dataSet, labels, k):     dataSetSize = dataSet.shape[0]     diffMat = tile(inX, (dataSetSize,1)) - dataSet     sqDiffMat = diffMat**2    sqDistances = sqDiffMat.sum(axis=1)     distances = sqDistanc...

다시 머신 러닝 공부를 시작하려 한다.  O'REILLY 의 파이썬 데이터 분석 책은 흠.. 그냥 파이썬으로 데이터 프레임 다루는 거랑 pandas의 여러가지 기능들을 소개해놓은 느낌인데 머신 러닝 인 액션에서는 머신 러닝 알고리즘에 대해 하나씩 설명되어 있다. 전자의 책 먼저 하고 후자의 책을 학습하려다가  너무 지루해서 그냥 병행하기로 했다. 두 책 모두 파이썬이라 너무 다행이긴 하다.. 그 전에 썼던 글이랑 중복되는 게 많다.. ---------------------------------------------------------------------------------------------- 올바른 알고리즘 선정 방법 지도학습 방법 분류  :  회귀 K-NN :  선형 회귀 나이브 베이스 : 지역적 가중치가 부여된 선형 회귀 지지 벡터 머신 : 리지 의사결정 트리 : 라쏘 비지도학습 방법 군집화  : 밀도 추정 k-평균 : 기대 극대화 디비스캔 : 파젠 윈도우 위와 같이 이 책에서는 8가지의 알고리즘을 설명하고 있다. 어떤 데이터를 끌어 왔을 때, 그 데이터의 상황에 맞게 알고리즘을 선정해야한다. 목적 값을 예측하거나 예견하려고 한다면 지도학습 방법을 살펴보고, 그렇지 않다면 비지도 학습 방법을 살펴보라. 예를 들면, 목접 값이 예/아니오, 1/2/3, A/B/C 와 같이 이산적인 값이면 분류 방법을 살펴보고 수치 값이라면 회귀를 살펴봐야한다. 그리고 목적 값이 아닌 무리에 알맞은지를 알아보고자 하는 것이라면 군집화를 살펴봐야한다. 솔직히 위의 8가지 알고리즘 중 2가지는 처음 들어봤다. 이제 시작이니 각 장에서 하나하나 제대로 살펴보고 공부해야겠다.

재귀와 완전탐색 우선 재귀 함수에 대해 설명하기 전에 두 코드를 비교해보자. 1. 반복문을 통한 1 부터 n 까지의 합 int sum(int n) {    int ret=0,i;    for(int i=1; i <= n; i++)       ret += i;    return ret; } 2. 재귀 함수를 통한 1 부터 n 까지의 합 int recursiveSum(int n) {    if (n==1) return 1; //더 이상 쪼개지지 않을 때    return n + recursiveSum(n-1); } 모든 재귀함수는 위와 같이 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례 라고 한다. 재귀호출은 1번과 같은 반복문과 그리 큰 차이는 없지만 코딩을 훨씬 간편하게 해줄 수 있다. 재귀 함수는 완전 탐색이라는 무식하게 모두 세는 방식을 사용하여 알고리즘을 짤 때 좋다. 처음에 문제를 파악한 뒤 재귀 함수를 써야한다면 기저 사례를 선택해야한다. 여기서 팁이 있다면, 입력이 잘못되었거나 범위에서 벗어난 경우도 기저 사례로 택해서 처음에 처리하면 함수 호출 과정에서 오류 검사를 할 필요가 없어지기 때문에 속도가 빨라진다. 많이 등장하는 완전 탐색 유형 1. 모든 순열 만들기 서로 다른 N 개의 원소를 일렬로 줄 세운 것을 순열이라고 한다. int factorial(int n) { if (n <= 1) return 1; //위에서 본 기저 사례 return n*factorial(n - 1); } 2. 모든 조합 만들기 서로 다른 N 개의 원소 중에서 R 개를 순서 없이 골라낸 것을 조합이라고 한다. int binco(int n,...

알고리즘 패러다임 공부 시작. 1. 무식하게 푸는 재귀함수를 시작으로 2. 분할정복 알고리즘 ---- 병합 정렬                             ---- 퀵 정렬 3. 동적 계획법 4. 탐욕법 5. 조합 탐색 출처 : 알고리즘 문제해결 전략