?96 ? ? double splitValue = findMiddleva lue(splitAttributeva lues);
?97 ? ? //cout << "splitValue" << splitValue ?<< endl;
?98?
?99 ? ? // 根据选定的切分属性和切分值，将数据集分为两个子集
100 ? ? vector > subset1;
101 ? ? vector > subset2;
102 ? ? for (unsigned i = 0; i < samplesNum; ++i)
103 ? ? {
104 ? ? ? ? if (splitAttributeva lues[i] == splitValue && tree->root.empty())
105 ? ? ? ? ? ? tree->root = data[i];
106 ? ? ? ? else
107 ? ? ? ? {
108 ? ? ? ? ? ? if (splitAttributeva lues[i] < splitValue)
109 ? ? ? ? ? ? ? ? subset1.push_back(data[i]);
110 ? ? ? ? ? ? else
111 ? ? ? ? ? ? ? ? subset2.push_back(data[i]);
112 ? ? ? ? }
113 ? ? }
114?
115 ? ? //子集递归调用buildKdTree函数
116?
117 ? ? tree->leftChild = new KdTree;
118 ? ? tree->leftChild->parent = tree;
119 ? ? tree->rightChild = new KdTree;
120 ? ? tree->rightChild->parent = tree;
121 ? ? buildKdTree(tree->leftChild, subset1, depth + 1);
122 ? ? buildKdTree(tree->rightChild, subset2, depth + 1);
123 }
124?
125 //逐层打印kd树
126 void printKdTree(KdTree *tree, unsigned depth)
127 {
128 ? ? for (unsigned i = 0; i < depth; ++i)
129 ? ? ? ? cout << "\t";
130 ? ? ? ? ? ??
131 ? ? for (vector::size_type j = 0; j < tree->root.size(); ++j)
132 ? ? ? ? cout << tree->root[j] << ",";
133 ? ? cout << endl;
134 ? ? if (tree->leftChild == NULL && tree->rightChild == NULL )//叶子节点
135 ? ? ? ? return;
136 ? ? else //非叶子节点
137 ? ? {
138 ? ? ? ? if (tree->leftChild != NULL)
139 ? ? ? ? {
140 ? ? ? ? ? ? for (unsigned i = 0; i < depth + 1; ++i)
141 ? ? ? ? ? ? ? ? cout << "\t";
142 ? ? ? ? ? ? cout << " left:";
143 ? ? ? ? ? ? printKdTree(tree->leftChild, depth + 1);
144 ? ? ? ? }
145 ? ? ? ? ? ??
146 ? ? ? ? cout << endl;
147 ? ? ? ? if (tree->rightChild != NULL)
148 ? ? ? ? {
149 ? ? ? ? ? ? for (unsigned i = 0; i < depth + 1; ++i)
150 ? ? ? ? ? ? ? ? cout << "\t";
151 ? ? ? ? ? ? cout << "right:";
152 ? ? ? ? ? ? printKdTree(tree->rightChild, depth + 1);
153 ? ? ? ? }
154 ? ? ? ? cout << endl;
155 ? ? }
156 }
157?
158?
159 //计算空间中两个点的距离
160 double measureDistance(vector point1, vector point2, unsigned method)
161 {
162 ? ? if (point1.size() != point2.size())
163 ? ? {
164 ? ? ? ? cerr << "Dimensions don't match！！" ;
165 ? ? ? ? exit(1);
166 ? ? }
167 ? ? switch (method)
168 ? ? {
169 ? ? ? ? case 0://欧氏距离
170 ? ? ? ? ? ? {
171 ? ? ? ? ? ? ? ? double res = 0;
172 ? ? ? ? ? ? ? ? for (vector::size_type i = 0; i < point1.size(); ++i)
173 ? ? ? ? ? ? ? ? {
174 ? ? ? ? ? ? ? ? ? ? res += pow((point1[i] - point2[i]), 2);
175 ? ? ? ? ? ? ? ? }
176 ? ? ? ? ? ? ? ? return sqrt(res);
177 ? ? ? ? ? ? }
178 ? ? ? ? case 1://曼哈顿距离
179 ? ? ? ? ? ? {
180 ? ? ? ? ? ? ? ? double res = 0;
181 ? ? ? ? ? ? ? ? for (vector::size_type i = 0; i < point1.size(); ++i)
182 ? ? ? ? ? ? ? ? {
183 ? ? ? ? ? ? ? ? ? ? res += abs(point1[i] - point2[i]);
184 ? ? ? ? ? ? ? ? }
185 ? ? ? ? ? ? ? ? return res;
186 ? ? ? ? ? ? }
187 ? ? ? ? default:
188 ? ? ? ? ? ? {
189 ? ? ? ? ? ? ? ? cerr << "Invalid method!!" << endl;
190 ? ? ? ? ? ? ? ? return -1;
191 ? ? ? ? ? ? }
192 ? ? }
193 }
194 //在kd树tree中搜索目标点goal的最近邻
195 //输入：目标点；已构造的kd树
196 //输出：目标点的最近邻
197 vector searchNearestNeighbor(vector goal, KdTree *tree)
198 {
199 ? ? /*第一步：在kd树中找出包含目标点的叶子结点：从根结点出发，
200 ? ? 递归的向下访问kd树，若目标点的当前维的坐标小于切分点的
201 ? ? 坐标，则移动到左子结点，否则移动到右子结点，直到子结点为
202 ? ? 叶结点为止,以此叶子结点为“当前最近点”
203 ? ? */
204 ? ? unsigned k = tree->root.size();//计算出数据的维数
205 ? ? unsigned d = 0;//维度初始化为0，即从第1维开始
206 ? ? KdTree* currentTree = tree;
207 ? ? vector currentNearest = currentTree->root;
208 ? ? while(!currentTree->isLeaf())
209 ? ? {
210 ? ? ? ? unsigned index = d % k;//计算当前维
211 ? ? ? ? if (currentTree->rightChild->isEmpty() || goal[index] < currentNearest[index])
212 ? ? ? ? {
213 ? ? ? ? ? ? currentTree = currentTree->leftChild;
214 ? ? ? ? }
215 ? ? ? ? else
216 ? ? ? ? {
217 ? ? ? ? ? ? currentTree = currentTree->rightChild;
218 ? ? ? ? }
219 ? ? ? ? ++d;