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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define SIZE_ATTR 3 /* 属性维度 */
#define SIZE_TRAIN 500 /* 训练集大小 */
#define SIZE_TEST 500 /* 测试集大小 */
#define K 7 /* 所选k值 */
#define FILE_TRAIN "train.txt"
/* 记录所构成的结构体变量 */
typedef struct _DataVector {
int id; /* 标号 */
float attr[SIZE_ATTR]; /* 属性 */
int label; /* 类别 */
} DataVector;
/* 把记录中的属性换成距离后的结构体变量 */
typedef struct _DistanceVector {
int id; /* 标号 */
int label; /* 类别 */
float distance; /* 距离 */
} DistanceVector;
/* 属性的结构体变量
可以先对属性值做一个分析，再做下一步针对性处理（如归一化特征值处理） */
typedef struct _AttrValue {
float max; /* 属性的最大值 */
float min; /* 属性的最小值 */
float length; /* 属性的长度 */
} AttrValue;
/* 定义全局变量 */
DataVector trainSet[SIZE_TRAIN]; /* 训练集 */
DataVector testSet[SIZE_TEST]; /* 测试集 */
DistanceVector knn[SIZE_TRAIN]; /* 距离存储 */
AttrValue av[SIZE_ATTR]; /* 属性的属性 */
/* 从文件中加载数据到内存 */
void loadDataFromFile(FILE *fp, char *fileName, DataVector *dv, int length) {
int i, j;
if ((fp = fopen(fileName, "r")) == NULL) {
printf("open \"%s\" failured!/n", fileName);
exit(1);
}
for (i = 0; i < length; ++i) {
for (j = 0; j < SIZE_ATTR; ++j) {
fscanf(fp, "%f ", &dv[i].attr[j]);
}
fscanf(fp, "%d\n", &dv[i].label);
}
fclose(fp);
}
/* 准备数据 */
void loadData() {
FILE *fp = NULL;
loadDataFromFile(fp, FILE_TRAIN, trainSet, SIZE_TRAIN);
loadDataFromFile(fp, FILE_TRAIN, testSet, SIZE_TEST);
printf("loading data success!\n");
}
/* 数据分析（预处理）
计算每个属性长度，为归一化特征值准备 */
void preProcess() {
int i, j;
/* 初始化 */
for (i = 0; i < SIZE_ATTR; ++i) {
av[i].max = trainSet[0].attr[i];
av[i].min = trainSet[0].attr[i];
}
/* 计算属性最大最小值 */
for (i = 0; i < SIZE_TRAIN; ++i) {
for (j = 0; j < SIZE_ATTR; ++j) {
if (trainSet[i].attr[j] > av[j].max) {
av[j].max = trainSet[i].attr[j];
} else if (trainSet[i].attr[j] < av[j].min) {
av[j].min = trainSet[i].attr[j];
}
}
}
/* 计算属性长度 */
for (i = 0; i < SIZE_ATTR; ++i) {
av[i].length = av[i].max - av[i].min;
}
}
/* 归一化特征值
公式：newValue = (oldValue - min) / (max - min) */
float autoNorm(float oldValue, AttrValue *av) {
return (oldValue - (av->min)) / (av->length);
}
/* 距离计算
这里计算的是欧式距离 */
float calcDistance(DataVector d1, DataVector d2) {
float sum = 0.0;
float newValue;
int i;
for (i = 0; i < SIZE_ATTR; ++i) {
newValue = autoNorm((d1.attr[i] - d2.attr[i]), av+i);
sum += newValue * newValue;
}
return (float) sqrt(sum);
}
/* 把每个数据的属性向量转化为距离 */
void transDistance(DataVector dv) {
int i;
for (i = 0; i < SIZE_TRAIN; ++i) {
/* 对距离进行赋值 */
knn[i].id = i;
knn[i].label = trainSet[i].label;
knn[i].distance = calcDistance(trainSet[i], dv);
}
}
/* 对所有距离进行排序，选取距离最小的k个数据向量（此处使用直接选择排序） */
void knnSort() {
int i, j, k;
DistanceVector temp;
for (i = 0; i < K; ++i) {
k = i;
/* 从无序序列中挑出一个最小的元素 */
for (j = i + 1; j <= SIZE_TRAIN; ++j) {
if (knn[k].distance > knn[j].distance) {
k = j;
}
}
temp = knn[i];
knn[i] = knn[k];
knn[k] = temp;
}
}
/* 预测分类 */
int forecastClassification() {
int freq[K] = {0};
int maxFreq = 0;
int i, j, k = 0;
/* 确定前k个点所在类别出现的概率
这里有点欠妥，因为分类最多能出现k个，出现了重复类别重复计算*/
for (i = 0; i < K; ++i) {
for (j = 0; j < K; ++j) {
if (knn[j].label == knn[i].label) {
freq[i]++;
}
}
}
/* 找到最大频率 */
for (i = 0; i < K; ++i) {
if (freq[i] > maxFreq) {
maxFreq = freq[i];
k = i;
}
}
/* 得到最大频率的类别 */
return knn[k].label;
}
/* 对测试数据进行测试 */
void test() {
int i;
int k = 0;
loadData();
preProcess();
/* 对每一条测试数据进行计算 */
for (i = 0; i < SIZE_TEST; ++i) {
transDistance(testSet[i]);
knnSort();
if (testSet[i].label == forecastClassification()) {
printf("1");
} else {
printf("0");
++k;
}
}
printf("\nTest end, wrong time is %d, the correct rate is %.2f%%\n", k, (float) (SIZE_TEST - k)/SIZE_TEST*100);
}
void main() {
test();
system("pause");
}
|
