Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Метод главных компонент и линейные многообразия на практике: применение к Российской банковской системеУТВЕРЖДАЮ Заведующий кафедрой _________ / Шайдуров В. В (подпись) «___» ________2012 г.
МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ
МЕТОД ГЛАВНЫХ КОМПОНЕНТ И ЛИНЕЙНЫЕ МНОГООБРАЗИЯ НА ПРАКТИКЕ: ПРИМЕНЕНИЕ К РОССИЙСКОЙ БАНКОВСКОЙ СИСТЕМЕ
Направление 010300.68 “Математика. Компьютерные науки” Магистерская программа 010300.68.10 Компьютерные технологии в гуманитарных и социально-экономических науках
Научный руководитель кандидат технических наук, доцент ___________/ Л.И. Покидышева (подпись, дата)
Выпускник ____________/ К.Ю. Веретнова (подпись, дата)
Красноярск 2012
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1 Ожегов С.И., Шведова Н.Ю. Толковый словарь русского языка. М.: изд-во «Азь», 1992. 976 с. 2 Gorban A. N., Zinovyev A. Y. Principal Graphs and Manifolds, Chapter 2 in: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, PA, USA. 2009. P. 28-59. 3 Gorban A. N., Zinovyev A. Y. Principal manifolds and graphs in practice: from molecular biology to dynamical systems // International Journal of Neural Systems. 2010. V. 20. №. 3. P. 219–232. 4 Рейтинги банков: рейтинговое интернет-агентство. 2012. URL: http://www.banki.ru (дата обращения 15.01.2012). 5 Центральный банк Российской Федерации: Интернет-ресурс. 2012. URL: http://www.cbr.ru (дата обращения 15.01.2012). 6 Pearson K. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 1901. 559-572 c. 7 Метод главных компонент: свободная энциклопедия. 2012. URL: http://ru.wikipedia.org (дата обращения 03.04.2012). 8 Jolliffe I.T. Principal Component Analysis, Springer: Springer Series in Statistics, 2nd ed., Springer, NY, 2002. P. 487 c. 9 Ланцош К. Практические методы прикладного анализа: Справочное руководство. М.: Государственное издательство физико-математической литературы, 1961. 524 c. 10 Зиновьев, А.Ю. Визуализация многомерных данных / Зиновьев А.Ю. – Красноярск: издательство КГТУ, 2000. 168с. 11 MacQueen J. Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability. 1967. 281-297 c. 12 Россиев А.А. Итерационное моделирование неполных данных с помощью многообразий малой размерности: дис. … 12.00.00: защищена 31.05.00: утв. 19.10.00. Красноярск, 2000. 83 с. 13 Самарский А. А. Введение в численные методы. М.: изд-во «Лань», 2005. 288 с. 14 Аттетков А.В., Галкин С.В., Зарубин В.С Методы оптимизации. М.: изд-во МГТУ им. Н. Э. Баумана, 2003. 441 с. 15 Распределение Гиббса: свободная энциклопедия. 2012. URL: http://ru.wikipedia.org (дата обращения 03.04.2012). 16 Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing. Science. 1983. 671–680 c.
ПРИЛОЖЕНИЕ 1
Таблица 2 - Банки, участвующие в исследовании
ПРИЛОЖЕНИЕ 2
Список показателей, которые были выбраны для исследования системы банков:
ПРИЛОЖЕНИЕ 3
Фрагмент программы, реализующей процесс нормирования матрицы данных перед вычислением векторов главным компонент. В программе – матрица данных. Функция вычисления выборочного среднего: double average(double *a, int n) { double average = 0; for (int i = 0; i < n; i++) average = average + a[i]; average = average/n; return average; }
Функция вычисления выборочной дисперсии: double dispersion(double *a, int n) { double avg1 = 0, avg2 = 0, dispersion; for (int i = 0; i < n; i++) { avg1 = avg1 + a[i]; avg2 = avg2 + a[i]*a[i]; } avg1 = avg1/n; avg1 = avg1*avg1; avg2 = avg2/n; dispersion = avg2 - avg1; return dispersion; } Нормировка по столбцам: for (j = 0; j < m; j++) { for (i = 0; i < n; i++) c[i] = X[i][j]; tmp = average(c, n); tmp1 = sqrt(dispersion(c, n)); for (i = 0; i < n; i++) if (tmp1!= 0) X[i][j] = (X[i][j] - tmp)/tmp1; }
ПРИЛОЖЕНИЕ 4 Фрагмент программы, реализующей поиск векторов главных компонент. На вход подается нормированная матрица данных . Затем вычисляется ковариационная матрица , после чего находятся собственные вектора и собственные значения этой матрицы с помощью метода вращений Якоби. Найденные собственные вектора – вектора главных компонент. Функция нахождения коэффициента ковариации: double kfr (int n, double *a, double *b) { int i; double sr1, sr2, sum1=0, sum2=0, pr1=0, d, kf;
//Находим среднее: sr1 = average(a, n); //функция average(x,y) – функция из предыдущего фрагмента программы sr2 = average(b, n); sum1 = 0;
//Перемножаем центрированные компоненты: for(i=0; i<n; ++i) { pr1=(a[i]-sr1)*(b[i]-sr2); sum1=sum1+pr1; }
d=sum1/n; kf=d; return kf; }
Вспомогательная функция, для вычисления модуля числа: double modul (double n) { if (n >= 0) return n; else return (-1)*n; }
Вспомогательная функция для вычисления функции sign(x): double sign (double n) { if (n > 0) return 1; else { if (n == 0) return 0; else return -1; } } Вычисляем ковариационную матрицу: double b1[n], b2[n]; double kf;
for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { b1[j] = X[j][i]; b2[j] = X[j][i]; } kf = kfr(n, b1, b2); cov[i][i] = kf; }
for(int t = 0; t < m; t++) { for(int k = t; k < m - 1; k++) { for(j = 0; j < n; j++) { b1[j] = X[j][t]; b2[j] = X[j][k+1]; } kf=kfr(n, b1, b2); cov[k+1][t] = kf; cov[t][k+1] = kf; } }
/Переменные для нахождения собственных векторов: int k, l; double v[m][m], vt[m][m], vta[m][m], V[m][m], W[m][m], max, max1, q, eps, cos, sin;
for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { if (i!= j) V[i][j] = 0; else V[i][j] = 1; } } while (N!= 1551) { max = cov[1][0]; k = 1; l = 0; //Находим максимальный по модулю элемент for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { if(i!= j) { if (max < modul(cov[i][j])) { max = modul(cov[i][j]); k = i; l = j; } } } } //Строим матрицу Vk: for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { if(i == j) v[i][j] = 1; else v[i][j] = 0; } }
Строим ротацию: q = sqrt(1-((4*cov[k][l]*cov[k][l])/(pow((cov[k][k] - cov[l][l]),2)+pow(2*cov[k][l],2)))); if (cov[k][k] == cov[l][l]) eps = sign(cov[k][l]); else eps = sign((cov[k][k] - cov[l][l])/(2*cov[k][l])); cos = sqrt((1+q)/2); sin = eps*sqrt((1-q)/2); v[k][k] = cos; v[l][l] = cos; v[k][l] = (-1)*sin; v[l][k] = sin;
//Транспонирование Vk: for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { vt[i][j] = v[j][i]; } } // Умножение матриц: for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { tmp=0; for(z = 0; z < m; z++) { tmp += vt[i][z]*cov[z][j]; } vta[i][j] = tmp; } } //Матрица а(k+1): for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { tmp = 0; for (z = 0; z < m; z++) { tmp += vta[i][z]*v[z][j]; } cov[i][j] = tmp; } } //Матрица собственных векторов: for(i = 0; i < m; i++) { for(j = 0; j < m; j++) { tmp = 0; for(z = 0; z < m; z++) { tmp += V[i][z]*v[z][j]; } W[i][j] = tmp; } } for (i = 0; i < m; i++) { for(j = 0; j < m; j++) { V[i][j] = W[i][j]; } } N = N + 1; }
ПРИЛОЖЕНИЕ 5 Таблица 3 – Вектора главных компонент
Окончание Таблицы 3
ПРИЛОЖЕНИЕ 6
Фрагмент программы, реализующей процесс проецирования точек-банков из пространства показателей в пространство главных компонент. В программе – матрица данных, – вектора главных компонент. for(i = 0; i < n; ++i) { sum1=0; sum2=0;
for(j = 0; j < m; ++j) b[j] = a[i][j];
for(j = 0; j < m; ++j) { sum1 = sum1+x1[j]*b[j]; sum2 = sum2+x2[j]*b[j]; }
y1[i] = sum1; //координата на векторе первой главной компоненты y2[i] = sum2; //координата на векторе второй главной компоненты }
ПРИЛОЖЕНИЕ 7
Таблица 4 – Координаты точек-банков на плоскости главных компонент
Продолжение Таблицы 4
Окончание Таблицы 4
ПРИЛОЖЕНИЕ 8
Фрагмент программы, реализующей построение упругой кривой. В программе через обозначена матрица данных, – матрица координат узлов кривой.
Функция, вычисляющая расстояние между точками: double distance (double x1, double y1, double x2, double y2) { return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2)); }
Функция, для вычисления номера узла, который ближе всего находится к точке данных: int min_dist (double *d, int n) { int i, k; double min;
min = d[0]; k = 0;
for (i = 0; i < n; i++) { if (d[i] < min) { min = d[i]; k = i; } }
return k; }
Функция, вычисляющая значение функции : int delta (int i, int j) { if (i == j) return 1; else return 0; }
Вспомогательные функции для вычисления коэффициентов матрицы системы, которую надо будет решать: int deltaE (int i, int k) { return delta(i, k) - delta(i+1, k); }
int deltaR (int i, int k) { return delta(i + 1, k) + delta(i - 1, k) - 2*delta(i, k); }
Функция для вычисления нормы элемента: double norm (double **y, int p, int m) { int i, j; double n = 0;
for (i = 0; i < p; i++) { for (j = 0; j < m; j++) { n = n + y[i][j]*y[i][j]; } }
n = sqrt(n);
return n; }
Функция для вычисления значения функционала : double Uy (double **X, int n, double **y) { double tmp, tmpr,**K, *d, uy; int i, j, k, min;
K = new double *[p]; d = new double [p];
for (i = 0; i < p; i++) { K[i] = new double [n]; }
for (i = 0; i < p; i++) { for (j = 0; j < n; j++) K[i][j] = -1; }
for (i = 0; i < n; i++) { for (j = 0; j < p; j++) { d[j] = distance(X[i][0], X[i][1], y[j][0], y[j][1]); }
min = min_dist(d, p); K[min][i] = i; }
uy = 0;
for (i = 0; i < p; i++) { k = 0;
for (j = 0; j < n; j++) { if (K[i][j] >= 0) { k = k + 1;//количество точек в i-ом таксоне
//формирование U(y): uy = uy + pow(distance(X[j][0] - y[i][0], X[j][1] - y[i][1], 0, 0), 2); } }
}
uy = uy/(double)n; return uy; }
Функция для вычисления значения функционала : double U (double **y, int p, int m, double uy, double lyambda, double mu) { int i; double u = uy;
for (i = 0; i < p - 1; i++) { u = u + lyambda*pow(distance(y[i+1][0] - y[i][0], y[i+1][1] - y[i][1], 0, 0), 2); }
for (i = 1; i < p - 1; i++) { u = u + mu*pow(distance(y[i+1][0] + y[i-1][0] - 2*y[i][0], y[i+1][1] + y[i-1][1] - 2*y[i][1], 0, 0), 2); }
return u; }
Задается начальное положение узлов: min = (int)X[0][0]; for (i = 0; i < n; i++) { if (X[i][0] < min) min = (int)X[i][0]; } min = min - 1;
for (i = 0; i < p; i++) { y[i][0] = min + i*hx; y[i][1] = 0; } do { count++; //Формирование матрицы K: for (i = 0; i < p; i++) { for (j = 0; j < n; j++) K[i][j] = -1; }
for (i = 0; i < n; i++) { for (j = 0; j < p; j++) { d[j] = distance(X[i][0], X[i][1], y[j][0], y[j][1]); }
min = min_dist(d, p); K[min][i] = i; }
//Формирование правой части: for (i = 0; i < p; i++) { b[i][0] = 0; b[i][1] = 0;
k = 0;
for (j = 0; j < n; j++) { if (K[i][j] >= 0) { b[i][0] = b[i][0] + X[j][0]; b[i][1] = b[i][1] + X[j][1];
k = k + 1;//количество точек в i-ом таксоне
} }
b[i][0] = b[i][0]/(double)n; b[i][1] = b[i][1]/(double)n;
qt[i] = k; }
uy = Uy(X, n, y);
uOld = U(y, p, m, uy, lyambda, mu);
if (count == 1) { ubest = uOld; for (i = 0; i < p; i++) { for (j = 0; j < m; j++) { ybest[i][j] = y[i][j]; } } }
if (count > 1) { mu = mu/2; lyambda = lyambda/2; } //Формирование матрицы А: for (j = 0; j < p; j++) { for (k = 0; k < p; k++) { e = 0;
for (i = 0; i < s; i++) { e = e + (lyambda/p)*deltaE(i, j)*deltaE(i, k); }
r = 0;
for (i = 1; i < s; i++) { r = r + (mu/p)*deltaR(i, j)*deltaR(i, k); }
A[j][k] = (qt[j]*delta(j, k))/(double)n + e + r; } }
//Решение системы методом Зейделя:
for (j = 0; j < p; j++) { for (k = 0; k < m; k++) { yk[j][k] = y[j][k]; } } do { for (j = 0; j < p; j++) { for (k = 0; k < m; k++) { yki[j][k] = yk[j][k]; } }
for (j = 0; j < p; j++) { tmp = 0; tmpr = 0; for (k = 0; k < p; k++) {
if (j!= k) { tmp = tmp + A[j][k]*yk[k][0]; tmpr = tmpr + A[j][k]*yk[k][1];
} }
yk[j][0] = (b[j][0] - tmp)/A[j][j]; yk[j][1] = (b[j][1] - tmpr)/A[j][j]; }
for (j = 0; j < p; j++) { for (k = 0; k < m; k++) { yki[j][k] = yki[j][k] - yk[j][k]; } } norma = norm(yki, p, m);
} while (norma > eps); //Метод имитации отжига: uy = Uy(X, n, yk);
u = U(yk, p, m, uy, lyambda, mu);
if(count == 1) { Q = uOld - u; }
if (u < uOld || (double(rand()%10))/10 < exp((-1)*(u - uOld)/mu)) { for (i = 0; i < p; i++) { for (j = 0; j < m; j++) { y[i][j] = yk[i][j]; } } }
Q = Q*0.895;
uy = Uy(X, n, y);
u = U(y, p, m, uy, lyambda, mu);
if (u < ubest) { difference = abs(u - ubest);
ubest = u;
for (i = 0; i < p; i++) { for (j = 0; j < m; j++) { ybest[i][j] = y[i][j]; } } } } while (difference > eps);
ПРИЛОЖЕНИЕ 9
Фрагмент программы, реализующей процесс проецирования точек из пространства главных компонент на упругую кривую. В программе – матрица координат точек в пространстве главных компонент, – матрица координат узлов упругой кривой. Функция, вычисляющая наклонных коэффициент прямой, проходящей через две заданные точки: double main_str_a (double x1, double y1, double x2, double y2) { return (y2 – y1)/(x2 – x1); } Функция, вычисляющая сдвиг по оси прямой, проходящей через две заданные точки: double main_str_b (double x1, double y1, double x2, double y2) { return y1 – main_str_a(x1, y1, x2, y2)*x1; } Функция, вычисляющая наклонных коэффициент прямой, перпендикулярной данной: double adv_str_A (double x1, double y1, double x2, double y2) { return (-1)/(main_str_a(x1, y1, x2, y2)); } Функция, вычисляющая сдвиг по оси прямой, перпендикулярной данной: double adv_str_B (double x1, double y1, double x2, double y2) { return 0.5*(y1 + y2) – ((-1)/(main_str_a(x1, y1, x2, y2)))*(x1 + x2)*0.5; }
double adv_str_Bj (double x1, double y1, double x2, double y2, double x, double y) { return y – ((-1)/(main_str_a(x1, y1, x2, y2)))*x; }
Функция, вычисляющая первую координату точки пересечения двух прямых: double pc_x (double A1, double B1, double A2, double B2) { return (B2 – B1)/(A1 – A2); } Функция, вычисляющая вторую координату точки пересечения двух прямых: double pc_y (double A1, double B1, double A2, double B2) { return (B2*A1 – B1*A2)/(A1 – A2); } Находим узел, который находится ближе всего к точке данных: for (I = 0; I < n; i++) { for (k = 0; k < p; k++) { d[k] = distance(x[i][0], x[i][1], y[k][0], y[k][1]); }
min = min_dist(d, p); if (min == 0 || min == p – 1) { if (min == 0) { Am = main_str_a(y[min][0], y[min][1], y[min + 1][0], y[min + 1][1]); Bm = main_str_b(y[min][0], y[min][1], y[min + 1][0], y[min + 1][1]);
A1 = adv_str_A(y[min][0], y[min][1], y[min + 1][0], y[min + 1][1]); B1 = adv_str_Bj(y[min][0], y[min][1], y[min + 1][0], y[min + 1][1], x[i][0], x[i][1]); }
if (min == p – 1) { Am = main_str_a(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]); Bm = main_str_b(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]);
A1 = adv_str_A(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]); B1 = adv_str_Bj(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1], x[i][0], x[i][1]); }
pl[i][0] = pc_x(Am, Bm, A1, B1); pl[i][1] = pc_y(Am, Bm, A1, B1);
}
else { A1 = adv_str_A(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]); B1 = adv_str_B(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]);
A2 = adv_str_A(y[min][0], y[min][1], y[min + 1][0], y[min + 1][1]); B2 = adv_str_B(y[min][0], y[min][1], y[min + 1][0], y[min + 1][1]); //Находим координаты точки пересечения серединных перпендикуляров: h[0] = pc_x(A1, B1, A2, B2); h[1] = pc_y(A1, B1, A2, B2); A1 = main_str_a(x[i][0], x[i][1], h[0], h[1]); B1 = main_str_b(x[i][0], x[i][1], h[0], h[1]);
Am = main_str_a(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]); Bm = main_str_b(y[min][0], y[min][1], y[min – 1][0], y[min – 1][1]);
pl[i][0] = pc_x(A1, B1, Am, Bm); pl[i][1] = pc_y(A1, B1, Am, Bm);
} } ПРИЛОЖЕНИЕ 10
Фрагмент программы, реализующей вычисление ошибки аппроксимации. В программе – матрица координат объектов до проекции на кривую, – матрица координат объектов после проекции на кривую. ms = 0; for (i = 0; i < n; i++) { ms = ms + pow(distance(x[i][0], x[i][1], xp[i][0], xp[i][1]), 2); }
ms = sqrt(ms/n);
ПРИЛОЖЕНИЕ 10 Таблица 5 – Таблица расстояний между точками-банками и их проекциями на упругую кривую
Окончание Таблицы 5
|