K-Nearest Neighbor — Transcript

Full transcript

1. 0:00in this video we'll be talking about a
2. 0:02type of machine learning algorithm
3. 0:04called K nearest neighbor one of the
4. 0:06reasons I love K nearest neighbor is
5. 0:08because it's really easy to see visually
6. 0:10and pretty easy to understand so let's
7. 0:13get into it
8. 0:14we'll be using the same example as we
9. 0:16have in several of our other machine
10. 0:17learning videos about trying to classify
11. 0:19a mystery fish as a salmon or a tuna
12. 0:22based on some properties about it here
13. 0:25we'll be using the properties of weight
14. 0:26and length so on this grid right here
15. 0:29you see that I have lengths on the
16. 0:31x-axis and weights on the y-axis and you
17. 0:33see that I have these red circles
18. 0:34representing tunas and these orange
19. 0:37triangles representing salmon we already
20. 0:39see some natural clustering right it
21. 0:41seems like the tunas have a low length
22. 0:44and a high weight and the salmon have a
23. 0:45high length and a low weight in general
24. 0:48of course there's some that are kind of
25. 0:49on the border not sure about but that's
26. 0:51the general trend here with K nearest
27. 0:55neighbor basically how it works let me
28. 0:56show you visually first before we go
29. 0:58into the math because that really helps
30. 1:00to solidify things if we have a mystery
31. 1:02fish right so I'm gonna represent that
32. 1:05with I'm gonna use grey good color for
33. 1:07mystery I'm gonna use this great X to
34. 1:10represent a mystery fish if I said
35. 1:12here's a mystery fish with that length
36. 1:13and that way would you probably say it's
37. 1:16a tuna or a salmon you'd probably say
38. 1:18it's a tuna right because it's literally
39. 1:20close to other tuna its neighbors we're
40. 1:23using that word neighbor its neighbors
41. 1:25are other tunas and it has more distant
42. 1:28neighbors that are other sentient so I'd
43. 1:29say it's a tuna now a more ambiguous
44. 1:33case would be something like if I put a
45. 1:34grey X here it seems like it's kind of
46. 1:36on the border but maybe leaning towards
47. 1:38salmon because these two triangles these
48. 1:40two salmon are really close whereas
49. 1:42there's only one tuna kind of close to
50. 1:44it so a little bit more ambiguous there
51. 1:46let's assign some mathematical
52. 1:48formulation to it to help us make these
53. 1:50ideas a little more rigorous all right
54. 1:53so given a mystery fish at sub high it
55. 1:57only has two things about it it has a
56. 1:59weight W sub I and a length L sub I now
57. 2:02how do we give a mathematical notion of
58. 2:05a similarity between this mystery fish
59. 2:08and some other fish F sub J which maybe
60. 2:11we do have data for
61. 2:13for example if we have this guy this X
62. 2:15is our mystery fish how do we use data
63. 2:17about this tuna to help us make a
64. 2:19decision so how we're gonna do that
65. 2:22there's not a set way to do it that's
66. 2:24one of the reasons I like K nearest
67. 2:25neighbor is because you can really make
68. 2:27up whatever distance function you want
69. 2:28but we're gonna be using the literal
70. 2:30distance function in the grid that is
71. 2:32what's the Euclidean distance or
72. 2:34literally the distance between that X
73. 2:36and some other fish we do know details
74. 2:38about so remember that is given by our
75. 2:41distance formula which let me write out
76. 2:43here square root of we take the
77. 2:46difference between there X variables or
78. 2:49the lengths so L sub I minus L sub J we
79. 2:53square it and we add that the difference
80. 2:56between their weights W sub I minus W
81. 2:59sub J and we square it it's on a square
82. 3:01root so that's basically your Euclidean
83. 3:04distance between two points in the plane
84. 3:06and we're using the same idea in this
85. 3:08example so that's gonna be our
86. 3:11similarity between mystery fish I and
87. 3:15known fish J so if we calculate that
88. 3:18distance between mystery fish here and
89. 3:21this guy we're gonna find that distance
90. 3:22is really small we find this distance is
91. 3:24really small we find this distance is
92. 3:25really small we can find that distance
93. 3:27for every single other fish in here
94. 3:30including all these salmon here and
95. 3:32basically ask who are your three or five
96. 3:36closest neighbors if we use the three
97. 3:38closest neighbors we find out it's this
98. 3:41guy this guy and this guy probably right
99. 3:44so since of your three closest neighbors
100. 3:47we figure out how many our salmon and
101. 3:48how many our tuna in this case they're
102. 3:50all tuna so we assign you as a tuna as
103. 3:53well that's a very logical way to go
104. 3:54about it right it basically says the
105. 3:57idea of you are very similar to people
106. 4:00who have similar characteristics to you
107. 4:02right you have a similar outcome for
108. 4:04example so that's basically how it works
109. 4:07one caveat notice I said things like set
110. 4:10your number of neighbors k equal to 3 or
111. 4:12set it equal to 5 why did I pick odd
112. 4:14numbers well if I picked 4 there's
113. 4:16always the chance you're gonna have two
114. 4:18salmon and 2 tuna and then you're kind
115. 4:19of stuck in the water again so it's it's
116. 4:23nice to pick an odd number so there's
117. 4:24never a tie of course if you have
118. 4:26multiple
119. 4:26classes not just to then it gets a
120. 4:29little bit more tricky but with two
121. 4:30classes it's better to pick an odd
122. 4:31number I believe okay so yeah as we have
123. 4:35written in blue here you pick your K
124. 4:37closest neighbors and you pick the
125. 4:43majority okay so that becomes a little
126. 4:47more interesting when we consider this X
127. 4:49right here this mystery fish let me
128. 4:50switch colors so that's not overlapping
129. 4:54everything if I have this mystery fish
130. 4:56here and I pick K equals three who are
131. 4:58your three closest neighbors seems like
132. 5:00it's this salmon this salmon and this
133. 5:01tuna so in this case we have a majority
134. 5:03ruling in terms of salmon so we assign
135. 5:06this guy as a salmon okay
136. 5:08that's how can your neighbor works
137. 5:10before closing out this video I do want
138. 5:12to talk about some possible obstacles
139. 5:14you have here I didn't do this in a very
140. 5:18careful way because the weight could be
141. 5:20in any type of units right it could be
142. 5:22in pounds for example length could be in
143. 5:25any units it could be in inches or
144. 5:26millimeters or feet or whatever so if
145. 5:29weight is in pounds and lengths is in
146. 5:31inches and all I'm doing is just this
147. 5:34subtraction right here of lengths and
148. 5:35subtraction of weights I'm basically
149. 5:37implicitly
150. 5:38saying that a one unit different
151. 5:41difference in lengths is the same thing
152. 5:43as a one unit different in weight but a
153. 5:46one pound difference may not be as
154. 5:48drastic or could be more drastic than a
155. 5:50one inch difference or a one foot
156. 5:52difference so what you really want to do
157. 5:55before you carry out this process is to
158. 5:58kind of normalize these variables in
159. 6:01some way for example if I have my
160. 6:03distribution of weights of all of my
161. 6:05known fish then what I can do for a new
162. 6:09way is so I have weight sub I is my new
163. 6:13weight and I want to normalize it so let
164. 6:15me just say prime it's going to be equal
165. 6:18to the true value of that way minus the
166. 6:21average this is a bar so average of all
167. 6:23the weights I have so far
168. 6:24divided by the standard deviation of the
169. 6:27weights you're going to notice this is
170. 6:28just a z-score or a normalization
171. 6:33subtracting the mean and taking the
172. 6:35standard dividing my standard deviation
173. 6:36okay you can of course do different
174. 6:39kinds of standardization on
175. 6:40in max normalization if you want but the
176. 6:43point is you want to somehow get all
177. 6:44your variables on the same scale
178. 6:46speaking of your variables here I just
179. 6:48have two but you might have several more
180. 6:50you can go ahead and just include those
181. 6:52more terms in your Euclidean norm or
182. 6:55whatever norm you want to use as your
183. 6:57similarity distance maybe metric okay so
184. 7:01that's a quick introduction to K nearest
185. 7:04neighbor visual representation of how it
186. 7:06works
187. 7:06so we'll do some more videos about it in
188. 7:08the future with some more considerations
189. 7:10until next time