1 function sheet07
   2 
   3 N = 300; % size of training data set
   4 K = 5;   % number of neighbors
   5 
   6 % generate a training and test data set
   7 [X, Y] = generate_data(N);
   8 [XE, YE] = generate_data(1000);
   9 
  10 % plot training data set
  11 IP = find(Y == 1);
  12 IN = find(Y == -1);
  13 plot(X(IP, 1), X(IP, 2), 'r+', X(IN, 1), X(IN, 2), 'bo');
  14 
  15 % predict on training set
  16 Yh = knn(K, X, Y, X);
  17 
  18 % predict on test set
  19 YEh = knn(K, X, Y, XE);
  20 
  21 % Plot predictions and training and test error in the title.
  22 hold on;
  23 plotgrid(K, X, Y, -6, 6, -6, 6);
  24 hold off;
  25 colormap([0 0 0])
  26 title(sprintf('training error = %.2f%%, test error = %.2f%%', ...
  27               loss(Y, Yh), loss(YE, YEh)));
  28 
  29 function [X, Y] = generate_data(N)
  30 X = [2*randn(N, 2) + repmat([1, 2], N, 1); ...
  31      0.5*randn(N, 2) + repmat([-2, 1], N, 1)];
  32 Y = [ones(N, 1); -ones(N, 1)];
  33 
  34 % Compute all pairwise distances quickly.
  35 function D = pwdist(X, Y)
  36 D = size(X, 2);
  37 N = size(X, 1);
  38 M = size(Y, 1);
  39   
  40 XX = sum(X.*X, 2);
  41 YY = sum(Y.*Y, 2);
  42 D = repmat(XX, 1, M) + repmat(YY', N, 1) - 2*X*Y';
  43 
  44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  45 % Your Solutions Below
  46 
  47 % 1. knn - implement k-nearest neighbor prediction
  48 %
  49 % inputs:
  50 %   K - number of neighbors
  51 %   X - [n, d]-matrix with n training data points of dimension d (in the rows!)
  52 %   Y - [n, 1]-matrix of +1, -1 training labels
  53 %   XE - [m, d]-matrix with test labels, for which predictions should
  54 %        be computed
  55 %
  56 % output:
  57 %   Yh - [m, 1]-matrix of predicted labels (real number, sign
  58 %        indicates class.
  59 %
  60 % Note: one for-loop is allowed.
  61 function Yh = knn(K, X, Y, XE)
  62 % ...
  63 
  64 % 2. loss - compute the 0-1 loss. Sign of entries of Y and Yh indicate
  65 % class.
  66 function E = loss(Y, Yh)
  67 % ...
  68 
  69 % 3. plotgrid - plot knn predictions on a grid
  70 %
  71 % inputs:
  72 %   K, X, Y - as inputs to knn
  73 %   XMIN, XMAX - minimal and maximal value of X
  74 %   YMIN, YMAX - minimal and maximal value of Y
  75 %
  76 % Hint: use meshgrid, contour
  77 function plotgrid(K, X, Y, XMIN, XMAX, YMIN, YMAX)
  78 % ...