BLOG main image
Notice
CATEGORY
FunnyPR (32)
OpenGL (20)
PatternRecognition (7)
Tips (2)
XML (1)
DataMining (1)
TAGS
Recent Entries
Recent Comments
Recent Trackbacks
Calendar
Archive
Link Site
Visitors up to today!
Today hit, Yesterday hit
daisy rss
tistory 티스토리 가입하기!
Principal Component Analysis(주성분 분석)
2014. 4. 12. 15:46
[PatternRecognition]

1. 개념

주성분분석: 고차원의 특징 벡터를 저차원 특징 벡터로 축소하는 특징 벡터의 차원 축소(dimension reduction) 뿐만 아니라 데이터의 시각화 그리고 특징 추출에도 유용하게 사용되는 데이터 처리 기법[1]

- 주성분 분석 방법은 선형(Linear) 투영 기법임 따라서 실시간 처리가 가능함

- 주성분 분석 방법에서는 주성분(PC: Principal Component)이 축(axis) 정보가 됨(예: PC1, PC2, PC3)

- 패턴인식에서 매핑과 사영의 개념이 들어 가는데 주성분 부석 방법은 사영(Projection) 기법임

- 주성분 분석 방법에서는 고유벡터(eigenvectors)와 고유값(eigenvalues)의 개념이해가 중요함

   - 투영하고자 하는 입력 패턴의 고유벡터와 고유값 계산이 필요함 

   - why 투영하는데 고유벡터가 필요한지는 고유벡터 공부해 보면 알게 됨


2. 알고리즘 

[step 1] 입력 패턴의 평균 벡터 계산

[step 2] 입력 패턴과 평균을 가지고 공분산(Covariance) 행렬 계산 

 - 공분산: 두개 이상의 변량 데이터가 주어질 경우 각 변량간의 변화하는 양상을 나타내는 통계적 척도(자료의 분포 즉 흩어진 정도를 계산)

[step 3] 공분산을 통해 고유값와 고유벡터 계산 - 자코비안 방법 사용함

[step 4] 고유값과 고유벡터 정렬(sorting) 및 변환 행렬 생성

[step 5] 차원 축소(2-3차원)


3. C++ 구현

3.1 PCA.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
 
#ifndef PCA_CLASS_H
#define PCA_CLASS_H
 
class CPCA{
public: //멤버 변수
    int m_NumPattern; //입력패턴 수 
    int m_NumSensor; //센서의 갯수 즉 입력 차원수 
    int m_NumClass; //입력패턴 중 클래스의 수
 
    float **m_Covariance; //공분산
    float **m_Data; //입력 패턴
    float *m_Means; //평균 계산
    float **m_EigenVectors;//고유 벡터
    float **m_TransposeEigenVectors; //고유 벡터 전치행렬
    float **m_Result;
 
    //jacobi 관련 변수 
    float *d, **v, **e; //data vector eigen
    int m_nrot;// 반복 횟수 
 
 
public: //멤버 함수
    void PCA_mem_alloc(int NumPattern, int NumSensor, int NumClass); //메모리 할당
    void PCA_free_mem_alloc(); //메모리 해제
    void PCA(); //주성분 분석 실행
    void CalculateTotalMeans(); //평균 계산
    void CalculateCovariance(); //공분산 계산
    void CalculateEigen(); //고유벡터 및 고유값 계산
    void TransposeEigen(); //고유벡터 전치 행렬 구하기
    void Transform(int demensions); //차원 축소
};
 
#endif

3.2 PCA.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include "stdio.h"
#include "PCA.h"
 
#include <math.h>
#include <stdlib.h>
 
#define NRANSI
extern "C" {
#include "nr.h"
#include "nrutil.h"
}
 
void CPCA::PCA_mem_alloc(int NumPattern, int NumSensor, int NumClass){//메모리 할당
 
    m_NumPattern = NumPattern;
    m_NumSensor = NumSensor;
    m_NumClass = NumClass;
 
    //covariance
    m_Covariance = new float*[m_NumSensor];
    for(int i = 0; i < m_NumSensor; i++) m_Covariance[i] = new float[m_NumSensor];
 
    //data
    m_Data = new float*[m_NumPattern];
    for(int i = 0; i < m_NumPattern; i++) m_Data[i] = new float[m_NumSensor];
 
    //m_Means
    m_Means = new float[m_NumSensor];
 
    //m_EigenVectors
    m_EigenVectors = new float*[m_NumSensor];
    for(int i = 0; i < m_NumSensor; i++) m_EigenVectors[i] = new float[m_NumSensor];
 
    //m_TransposeEigenVectors
    m_TransposeEigenVectors = new float*[m_NumSensor];
    for(int i = 0; i < m_NumSensor; i++) m_TransposeEigenVectors[i] = new float[m_NumSensor];
 
    //m_Result
    m_Result = new float*[m_NumPattern];
    for(int i = 0; i < m_NumPattern; i++) m_Result[i] = new float[m_NumSensor];
 
    d=vector(1,m_NumSensor); 
    v=matrix(1,m_NumSensor,1,m_NumSensor);
}
 
void CPCA::PCA_free_mem_alloc(){//메모리 해제 
    //covariance
    for(int i = 0; i < m_NumSensor; i++ ) delete[] m_Covariance[i];
    delete[] m_Covariance;
 
    //data
    for(int i = 0; i < m_NumPattern; i++ ) delete[] m_Data[i];
    delete[] m_Data;
 
    //m_Means
    delete[] m_Means;
 
    //m_EigenVectors
    for(int i = 0; i < m_NumSensor; i++ ) delete[] m_EigenVectors[i];
    delete[] m_EigenVectors;
 
    //m_TransposeEigenVectors
    for(int i = 0; i < m_NumSensor; i++ ) delete[] m_TransposeEigenVectors[i];
    delete[] m_TransposeEigenVectors;
 
    //m_Result
    for(int i = 0; i < m_NumPattern; i++ ) delete[] m_Result[i];
    delete[] m_Result;
 
    free_matrix(v,1,m_NumSensor,1,m_NumSensor);
    //free_matrix(m_eigenVectors,1,m_NumSensor,1,m_NumSensor);
    free_vector(d,1,m_NumSensor);
}
 
void CPCA::PCA(){
    printf("=======================[step 1] 평균 계산 ===========================\n");
    CalculateTotalMeans();
 
    printf("\n=======================[step 2] 공분산 계산 ===========================\n");
    CalculateCovariance();
 
    printf("\n=======================[step 3,4] 고유벡터 및 고유값 계산, 정렬 ===========================\n");
    CalculateEigen();
    
    printf("\n=======================[step 5] 차원 축소 ===========================\n");
    TransposeEigen();
    Transform(3);
}
 
void CPCA::CalculateTotalMeans(){ //평균 계산
    float sum;
 
    for(int i=0; i<m_NumSensor;i++){
        sum=0.0f;
        for(int j=0; j<m_NumPattern;j++){
            sum+=m_Data[j][i];
        }
        m_Means[i]=sum/(float)m_NumPattern;
        
        printf("%f\t",  m_Means[i]);
    }
}
 
void CPCA::CalculateCovariance(){ //공분산 계산
    
    for(int i=0; i<m_NumSensor;i++){
        for(int j=0; j<m_NumSensor;j++){
            m_Covariance[i][j]=0.0F;
        }        
    }
    
    for(int k=0; k<m_NumSensor;k++){
        for(int l=0; l<m_NumSensor;l++){
            for(int m=0; m<m_NumPattern;m++){
                m_Covariance[k][l]+=((m_Data[m][k] - m_Means[k])*(m_Data[m][l] - m_Means[l]))/(float)(m_NumPattern-1);
            }
        }
    }
 
    for(int i=0; i<m_NumSensor; i++) {
        for(int j=0; j<m_NumSensor; j++) {
            printf("%f\t", m_Covariance[i][j]);
        }printf("\n");
    }
}
 
void CPCA::CalculateEigen(){ //고유벡터 및 고유값 계산, 정렬
 
    float **eigen_buffer;
    eigen_buffer=matrix(1,m_NumSensor,1,m_NumSensor);
    
    
    for (int i=1; i<=m_NumSensor; i++){ //데이터 복사 
        for (int j=1;j<=m_NumSensor;j++) { //fix wrong data
            eigen_buffer[i][j] = m_Covariance[i-1][j-1];
        }
    }
    
    jacobi(eigen_buffer,m_NumSensor,d,v,&m_nrot); //Gets the eigenvalues and corresponding eigenvectors
 
    eigsrt(d,v,m_NumSensor);//Sort eigen values and vectors in ascending order d:eigenvalue v:eigenvector
 
    for (int z=1; z<=m_NumSensor; z++){//정렬된 벡터 저장 
        for (int k=1;k<=m_NumSensor;k++) {
            m_EigenVectors[z-1][k-1]=0.0f;
            m_EigenVectors[z-1][k-1]=v[z][k];
            printf("%f\t",m_EigenVectors[z-1][k-1]); 
        }
        printf("\n");
    }
    
    free_matrix(eigen_buffer,1,m_NumSensor,1,m_NumSensor);
}
 
void CPCA::TransposeEigen(){ //정렬된 고유벡터 전치행렬 만들기 
    printf("=========Traspose(eigenvector)=============\n");
    for (int i=0; i<m_NumSensor; i++){
        for (int j=0; j<m_NumSensor; j++) {
            m_TransposeEigenVectors[i][j] = m_EigenVectors[j][i];
            printf("%f\t", m_TransposeEigenVectors[i][j]); 
        }printf("\n");
    }
    
}
 
void CPCA::Transform(int demensions){
    for (int i = 0; i < m_NumPattern; i++) //init
        for (int k = 0; k < m_NumSensor; k++) m_Result[i][k] =0.0f;
 
    printf("=========Transform(demensions)=============\n"); // multiply the data matrix by the selected eigenvectors
    for (int i = 0; i < m_NumPattern; i++){
        for (int j = 0; j < demensions; j++){
            m_Result[i][j] =0.0f;
            for (int k = 0; k < m_NumSensor; k++){
                m_Result[i][j] += m_Data[i][k] * m_EigenVectors[k][j];
            }printf("  [%d][%d] %12.6f",i ,j,m_Result[i][j]);
        }printf("\n");
    }
}

3.3 PCA_Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include "PCA.h"
 
#define NUM_PATTERN 30
#define NUM_SENSOR 8
#define NUM_CLASS 3
 
#pragma warning(disable:4305) //double float 잘림 경고 비활성
#pragma warning(disable:4244)
 
int main(){
 
    CPCA *pPCA = new CPCA; // 클래스 생성 및 메모리 할당 
 
    float data[NUM_PATTERN][NUM_SENSOR] = { 
        {10.7263f,15.5307,9.38547,8.26815,16.8715,9.38547,17.9888,11.8436},
        {10.7263,15.5307,9.38547,8.26815,16.8715,9.38547,17.9888,11.8436},
        {10.7263,15.5307,9.38547,8.26815,16.8715,9.38547,17.9888,11.8436},
        {10.7263,15.5307,9.38547,8.26815,16.8715,9.38547,17.9888,11.8436},
        {10.7263,15.5307,9.27373,8.26815,16.8715,9.38547,18.1006,11.8436},
        {9.88057,16.0695,9.98915,8.46905,17.0467,9.55482,18.3496,10.6406},
        {9.97831,16.0521,9.97831,8.35142,17.1367,9.54446,18.3297,10.6291},
        {9.86985,16.0521,9.97832,8.45986,17.1367,9.54446,18.3297,10.6291},
        {9.86985,16.0521,9.97832,8.45986,17.1367,9.54446,18.3297,10.6291},
        {9.86985,16.0521,9.97832,8.45986,17.1367,9.54446,18.3297,10.6291},
        {5.57164,29.5224,24.1679,4.05209,12.8799,4.63097,13.6758,5.49928},
        {5.63583,29.4798,24.1329,4.04624,12.8613,4.69654,13.6561,5.49133},
        {5.63583,29.4798,24.1329,4.11849,12.8613,4.62428,13.6561,5.49133},
        {5.62364,29.4881,24.1528,4.10958,12.7614,4.68638,13.6265,5.55156},
        {5.61959,29.4669,24.1354,4.10662,12.8242,4.683,13.6167,5.54756},
        {6.52483,28.7234,23.2624,3.90071,12.766,4.46808,13.617,6.73759},
        {6.51558,28.7535,23.2295,3.89519,12.7479,4.53258,13.5977,6.72804},
        {6.4539,28.7943,23.2624,3.90071,12.766,4.46808,13.617,6.73759},
        {6.50637,28.7129,23.2673,3.96039,12.7298,4.45544,13.6492,6.71853},
        {6.5678,28.7429,23.2345,3.95479,12.7119,4.44915,13.6299,6.70904},
        {18.1063,11.9601,7.72426,7.6412,13.3721,8.22258,13.7043,19.2691},
        {18.0984,11.6764,7.50625,7.75647,13.5113,8.34028,13.8449,19.2661},
        {18.22,11.2511,7.22082,7.89252,13.602,8.48027,13.9379,19.3955},
        {18.4277,10.8199,6.93154,8.03043,13.694,8.53761,14.0321,19.5266},
        {18.569,10.477,6.64395,8.09199,13.7138,8.68825,14.1397,19.6763},
        {18.3625,12.3211,7.94912,7.55167,12.8776,8.10811,13.275,19.5548},
        {18.3479,12.3114,7.94281,7.54567,12.9468,8.10167,13.2645,19.5393},
        {18.4127,12.3016,7.93651,7.53968,12.9365,8.09524,13.254,19.5238},
        {18.4127,12.3016,7.93651,7.53968,12.9365,8.09524,13.254,19.5238},
        {18.4127,12.3016,7.93651,7.53968,12.9365,8.09524,13.254,19.5238}
    };
 
    pPCA->PCA_mem_alloc(NUM_PATTERN,NUM_SENSOR,NUM_CLASS); //메모리 할당
 
    printf("=========Input Patterns=============\n");
    for(int i=0; i<NUM_PATTERN; i++){ //입력 데이터 복사 
        for(int j=0; j<NUM_SENSOR; j++){
            pPCA->m_Data[i][j] = data[i][j];
            printf("%f\t", pPCA->m_Data[i][j]); //데이터 확인
        }printf("\n");
    }
 
    pPCA->PCA(); //주성분 분석 수행
 
    pPCA->PCA_free_mem_alloc(); //메모리 해제
 
    delete pPCA; // 클래스 메모리 해제
 
    return 0;
}


3.4 실행 화면 - 현재 작업 중이 프로그램



4. Reference

[1] 한학용, "패턴인식개론", 한빛미디어, pp. 275-303, 2005.


프로그램 저작권은 글 작성자에게 있습니다. 

'PatternRecognition' 카테고리의 다른 글

Linear Discriminant Analysis(LDA) - C-Classes  (0) 2014.06.02
Linear Discriminant Analysis(LDA) - 2 classes  (0) 2014.05.30
Neural Networks: Data normalization  (0) 2014.04.25
The Basic Artificial Neuron: Bias neuron(Backpropagation)  (3) 2014.04.23
기초 통계(Statistic)  (0) 2014.04.14
Trackback : Comment
블로그를 시작하며...
2014. 4. 12. 14:51
[카테고리 없음]

아마도 이 블로그에 접속하는 사람들은 기본적인 지식을 가지고 관련 소스나 이해를 돕는 자료는 찾는데 목적이 있을것 같다. 

패턴인식 프로그램을 개발하면서 많은 자료를 검색해 보고 정리하지만 C로 구현하여 설명한 자료를 많이 없었으며, 대부분이 Matlab 그리고 lib 형태로 정보가 공유되는 글을 많이 본다. 

이 블로그의 목적은 다음과 같다. 

1. C, C++ Pattern Recognition 자료 공유

2. 패턴인식 데이터의 가시화를 위한 프로그래밍 기법에 대한 정리

3. 각종 기타 재밌는 취미 프로젝트 

====================================================================================================

나 또한 구글링을 많이 하지만 패턴인식 부분에서는 알고리즘의 순서와 눈으로 확인해 가면서 이해하는 것이 가장 빠른것 같아서 이 블로그를 시작한다. 



Trackback : Comment
prev"" #1 #··· #8 #9 #10 #11 next

티스토리툴바