34:["$","title",null,{"children":"Workshop Notebook: Machine Learning (iJS 3) | Philipp Burckhardt | Observable"}] 3c:T41e,md`> Naive Bayes is a classification algorithm that allows us to estimate the conditional probability that an observation belongs to a certain class given a set of features **x**. When used for modeling text documents, their words are usually used as features, but this is by no means a requirement. The model derives its name from the use of [Bayes' Rule](https://en.wikipedia.org/wiki/Bayes%27_theorem) and the fact that is based on the "naive" assumption that the presence of any feature does not influence the probabilities of observing any other feature, i.e. the probability of observing an observation's features given class *c*, ${tex`P(\mathbf{x}|c)`}, can be factorized as the product over all the individual feature probabilities. In our case, we may write this as ${tex`P(\mathbf{x}|c) = \prod_w P(w|c)`}, where the product is taken over all words in the respective document. [Bayes' Rule](https://en.wikipedia.org/wiki/Bayes%27_theorem) lets us then switch the conditioning and calculate the class probabilities given the observed features:`3d:T5b6,plotKDE = { var x1 = stdlib.linspace( stdlib.base.min.apply(null,xobs)-7, stdlib.base.max.apply(null,xobs)+7, 100 ); var n = xobs.length; var nh = n * h; var y1 = x1.map( x => fhat( x, xobs, K, h ) ); var x2 = stdlib.linspace( xobs[0]-8, xobs[0]+8, 100 ); var y2 = x2.map( x => K( (x-xobs[0])/h ) / nh ); var x3 = stdlib.linspace( xobs[1]-8, xobs[1]+8, 100 ); var y3 = x3.map( x => K( (x-xobs[1])/h ) / nh ); var x4 = stdlib.linspace( xobs[2]-8, xobs[2]+8, 100 ); var y4 = x4.map( x => K( (x-xobs[2])/h ) / nh ); var x5 = stdlib.linspace( xobs[3]-8, xobs[3]+8, 100 ); var y5 = x5.map( x => K( (x-xobs[3])/h ) / nh ); var x6 = stdlib.linspace( xobs[4]-8, xobs[4]+8, 100 ); var y6 = x6.map( x => K( (x-xobs[4])/h ) / nh ); var x7 = [ xobs[0], xobs[0] ]; var y7 = [ 0, 0.01 ]; var x8 = [ xobs[1], xobs[1] ]; var y8 = [ 0, 0.01 ]; var x9 = [ xobs[2], xobs[2] ]; var y9 = [ 0, 0.01 ]; var x10 = [ xobs[3], xobs[3] ]; var y10 = [ 0, 0.01 ]; var x11 = [ xobs[4], xobs[4] ]; var y11 = [ 0, 0.01 ]; var plt = new stdlib.Plot( [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11], [y1,y2,y3,y4,y5,y6,y7,y8,y9,y10,y11] ); plt.colors = [ 'blue', 'red', 'red', 'red', 'red', 'red', 'black', 'black', 'black', 'black', 'black' ]; plt.lineStyle = [ '-', '--', '--', '--', '--', '--', '-', '-', '-', '-', '-' ]; plt.yLabel = 'Density'; plt.xLabel = 'Value'; plt.width = 600; return plt; }3e:T63c,md`Cluster analysis subsumes unsupervised learning methods that are concerned with the task of grouping observations together in a way that observations assigned to a common group are similar to each other but distinct from observations assigned to the other groups (called *clusters*). One of the most popular clustering algorithms is [k-means clustering](https://en.wikipedia.org/wiki/K-means_clustering), which is in large part due to its computational efficiency. However, one downside of [k-means clustering](https://en.wikipedia.org/wiki/K-means_clustering) is that one has to specify the number of clusters that one wishes to retrieve beforehand. We are now going to explore a less known clustring technique, which does not suffer from this shortcoming. As we can see, the distribution has two modes, one at the value \`2\` and the other at the value \`9\`. We would expect observations generated from this distribution to roughly form two clusters. A clustering algorithm that can uncover these two clusters, without us having to tell the method that there are two groups, is mode clustering. Based on the nonparametric kernel density estimate of the distribution, *mode clustering* proceeds by finding the modes of the distribution via the so-called mean-shift algorithm. Besides estimating the modes of the distribution, the algorithm performs clustering since it reveals what mode each point is attracted to. To perform mode clustering, we have to choose only one tuning parameter, the bandwidth of the underlying kernel density estimator. The mean-shift algorithm works as follows:`3f:[] 38:{"id":"94f7743ed9ca0b80","slug":"workshop-notebook-machine-learning-ijs-3","title":"Workshop Notebook: Machine Learning (iJS 3)","thumbnail":"c5b2a1c0303643e7915f1fd737e8f69774bac7fb7f74ee2684f5c918778e0a94","access_level":"public","create_time":"$D2018-04-12T16:01:43.477Z","update_time":"$D2018-07-12T07:24:35.248Z","view_time":null,"first_public_time":"$D2018-04-12T19:52:50.854Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"0079603d1a1150ec","login":"planeshifter","name":"Philipp Burckhardt","avatar_url":"https://avatars-next.observableusercontent.com/8456e6044dafd635770ffd6fc90d200a75eacd1bcedd4826ccce11ae14179985","tier":"starter_2024","bio":"Statistics & Data Science. Ascetic-ecstatic Node.js hacker.","followed_by_you":false,"follows_you":false},"version":780,"publish_version":780,"role":null,"authored":false,"authors":[{"type":"individual","id":"935ee8ecd82e8cf3","login":"planeshifter","name":"Philipp Burckhardt","avatar_url":"https://avatars-next.observableusercontent.com/8456e6044dafd635770ffd6fc90d200a75eacd1bcedd4826ccce11ae14179985","tier":null,"bio":"Statistics & Data Science. Ascetic-ecstatic Node.js hacker.","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"935ee8ecd82e8cf3","login":"planeshifter","name":"Philipp Burckhardt","avatar_url":"https://avatars-next.observableusercontent.com/8456e6044dafd635770ffd6fc90d200a75eacd1bcedd4826ccce11ae14179985","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":16,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Workshop Notebook: Machine Learning (iJS 3)","cells":[{"id":0,"value":"md`# Workshop Notebook: Machine Learning (iJS 3)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"md`In this workshop notebook, we will explore several statistical machine learning algorithms.`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"md `## Spam Classifier`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":228,"value":"md`We are all plagued by the spam emails that arrive in our mailboxes each day. Flagging emails as spam is what we call a classification task, since it consists of assigning an observation into one of several categories (spam/no spam). In this notebook, we will explore building our own spam classifier using a simple but well-performing statistical technique called Naive Bayes.\n\nFor this purpose, we will make use of the \\`SPAM_ASSASSIN\\` data set that ships with stdlib. We can load a copy of it and assign it to the variable *spam* as follows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":270,"value":"spam = datasets( 'SPAM_ASSASSIN' )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":231,"value":"md`Take a few minutes to familiarize yourself with the data set (you might also want to read its documentation).\n\nFor this notebook, the emails from the \\`easy-ham-1\\` and \\`spam-2\\` batches will serve as our training set, from which we will build a model that can then predict whether a new email should be classified as spam. To evaluate the performance of a statistical model, it is common practice to set aside a test set of observations for which we know the true class, but which we hold out and do not use while building our model. This ensures that we get an unbiased estimate of how well the model will generalize once we evaluate it on our test set. Here, the emails from \\`spam-1\\`, \\`hard-ham-1\\`, and \\`easy-ham-2\\` will constitute our test set.\n\nLet's store all observations belonging to the training set in a new array, as follows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"training = {\n var arr = [] \n for ( var i = 0; i < spam.length; i++ ) {\n if ( spam[i].group === 'easy-ham-1' || spam[i].group === 'spam-2' ) {\n arr.push( spam[i] );\n }\n }\n return arr;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"md`**Exercise 1:** Analogously to \\`training\\`, create an array of test cases, which should include the emails from \\`spam-1\\`,\\`hard-ham-1\\`, and \\`easy-ham-2\\`. Assign the array to a cell with the name \\`test\\`.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":686,"value":"''","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"md`When you looked at some of the emails, you will have noticed that these always include meta-information of the emails before the actual content. The following function helps us to strip off this part and also removes other unwanted character sequences from the emails:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"function extractBody( email ) {\n // Remove the meta-information before two initial line breaks:\n var LINE_BREAK_REGEXP = /[\\r\\n]{2}([\\s\\S]*)$/;\n var text = email.match( LINE_BREAK_REGEXP )[ 1 ];\n \n // Remove numbers and other special characters:\n text = text.replace( /[0-9\\-\\+]/g, '' );\n \n // Remove common words such as \"the\" or \"and\":\n text = stdlib.removeWords( text, STOPWORDS );\n return text;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"md`Before we are able to call this function, we need to load the list of stopwords that will be removed. Since our texts are in English, we will load a list of commonly used English words, but [stdlib](https://github.com/stdlib-js/stdlib) comes with stopword lists for many other languages as well.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"STOPWORDS = datasets( 'STOPWORDS_EN' )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":273,"value":"md`> **Note:** Very common words that do not carry significant informational value are often removed when building a bag-of-words representation. These are referred to as stop words. This practice was more common in the past, where memory considerations played a larger role, but the results of quite a few statistical models also benefit from the removal of such common words.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":278,"value":"md`**Exercise 2:** Call \\`extractBody()\\` on a few of the spam texts and inspect them.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":670,"value":"''","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":648,"value":"md`**Exercise 3:** Amend the \\`extractBody\\` function to \n- turn the text to lowercase such that a word is treated the same no matter its case\n- expand contractions, e.g. don't => do not\n- remove interpunctuation\n> **Hint:** The [\\`lowercase\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/string/lowercase), [\\`expandContractions\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/nlp/expand-contractions), and [\\`removeInterpunctuation\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/string/remove-punctuation) functions may be used`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":680,"value":"md `**Challenge 1:** Build a widget for displaying the extracted messages. As a minimum, there should be an input field to select the message to be displayed. In addition, you could let users allow to specify which text processing steps \\`extractBody\\` should carry out. Study the effects of the different text processing techniques.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":282,"value":"\nmd`Our *Naive Bayes* model relies on a so-called [bag-of-words](https://en.wikipedia.org/wiki/Bag-of-words_model) representation of the documents in our data set. A large part of building a statistical model is the selection of variables that are useful in predicting the outcome of interest. In our case, we will just use the words appearing in the texts, but observe that we may throw away useful information by doing so. For example, we might speculate that spam mails contain more capitalized or uppercased words in order to grab the attention of the recipients.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":290,"value":"md`> **Note:** In natural language processing, a bag-of-words model is a simplifying representation of a text document, which disregards word order and grammar, only keeping count of how often a word appears in the respective document.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":306,"value":"md`**Exercise 4:** To generate a bag-of-words representation, we will tokenize our texts, i.e. split them up into pieces (the so-called tokens). We can use the [\\`tokenize\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/nlp/tokenize) function for this task. Let us now extract the tokens for the texts in our training set, using [\\`inmap()\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/inmap) to perform an in-place map operation.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"// WARNING: Operation will take some time to complete...\n\nstdlib.inmap( training, function( x ) {\n // Extract body and attach it as `body` property to `x`:\n \n // Tokenize the body of the email and save the tokens inside of the `tokens` property of `x`:\n \n return x;\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":318,"value":"md`* * *\n> ### Mathematical Formulation of the Naive Bayes Model`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":321,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":323,"value":"tex.block`P(c|\\mathbf{x}) = \\frac{P(\\mathbf{x}|c) P(c)}{P(\\mathbf{x})}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":325,"value":"md`> Our decision rule of whether an email should be classified as spam is then quite simple: We can drop the denominator and calculate ${tex`P(\\mathbf{x}|c) P(c) = \\prod_w P(w|c) P(c)`} for each class, assigning the observation to the class for which the conditional probability is larger. How do we obtain these probabilities? We estimate them by their empirical frequencies: We replace ${tex`P(c)`} by the percentage of documents from the respective class in our data corpus, and ${tex`P(w|c)`} by its relative frequency, i.e. the number of times the word appeared in documents of class *c* divided by the overall number of tokens in that class.\n* * *`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"md`Before building our model, let us explore the frequency differences for the tokens in both the spam and non-spam groups and find which ones help in discriminating between the two classes. For this purpose, we will divide our training data into two parts, and then lump the tokens from all their documents together into a single array, which we can then count to obtain the frequencies of the tokens in each group. We can use the [\\`groupBy\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/group-by) function to group our training data into the two groups as follows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":331,"value":"grouped = stdlib.groupBy( training, function( x ) {\n if ( x.group === 'spam-2' ) {\n return 'spam';\n }\n return 'nospam';\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":411,"value":"md`**Exercise 5:** We can now lump all tokens from texts belonging to either group together. Change the following code to return **all** tokens that appear in the spam and non-spam texts, respectively.`\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":414,"value":"tokens = {\n return {\n 'spam': [],\n 'nospam': []\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":719,"value":"md`> **Hint:** You may use [\\`pluck\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/pluck) as in \\`stdlib.pluck( grouped.spam, 'tokens' )\\` to extract the token arrays from the objects in \\`grouped.spam\\`. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":722,"value":"md`> **Hint:** [\\`flattenArray\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/flatten-array) can be used to convert an array-of-arrays to a single array with the elements of all individual arrays.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":421,"value":"md`**Exercise 6:** Create frequency object called \\`freqs\\` holding the token frequencies for both the spam and non-spam texts.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":728,"value":"md`\n> **Hint:** You may use the [\\`countBy\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/count-by) function to calculate the frequencies.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":738,"value":"md`> **Hint:** Supply the [\\`identity\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/identity) function as the second argument to [\\`countBy\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/utils/count-by) to group the array elements by their actual values.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":423,"value":"freqs = {\n return {\n 'spam': {},\n 'nospam': {}\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":742,"value":"md`**Exercise 7:** With this convenient representation in hand, we can explore the absolute frequencies of the tokens in the two groups. Think of a few words that you would expect to show up much more frequently in spam mails, and check whether the frequencies support this hypothesis.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":745,"value":"''","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":427,"value":"md`However, notice that the absolute frequencies might be misleading since the groups are not equally represented in our training set, with \\`spam-2\\` containing \\`1396\\` and \\`easy-ham-1\\` containing \\`2500\\` observations. Hence, it makes more sense to look at relative frequencies, which take the different group sizes into account. For future reference, let us first store the relative group frequencies in an \\`object\\`:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":429,"value":"groupProbs = {\n return {\n 'spam': 1396 / ( 1396 + 2500 ),\n 'nospam': 2500 / ( 1396 + 2500 )\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":379,"value":"md`To turn the token counts into relative frequencies, we have to divide them by the total number of tokens in the respective group. Let us define two functions for this purpose:`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"function wordSpamProb( word ) {\n var nk = freqs.spam[ word ] || 0;\n return ( nk ) / ( tokens.nospam.length );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":367,"value":"function wordNospamProb( word ) {\n var nk = freqs.nospam[ word ] || 0;\n return ( nk ) / ( tokens.nospam.length );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":371,"value":"md`Invoke the functions for the words you have looked at before. Now think about what would happen if we were to call either function for a word that did not occur in the respective group? For our classifier to work for documents which contain words unknown to our corpus, we will have to change how we estimate the different word probabilities. We will make use of a technique called Laplace Smoothing, which, in its simplest form, consists of adding a count of one to all words, even those which do not appear in documents of a given class.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":343,"value":"md`* * *\n> ### Laplace Smoothing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"md`> Estimating the word probabilities ${tex`P(w|c)`} by the empirical frequencies is problematic because it would mean that, for any word not appearing in any of the documents of the respective class, we would estimate it as zero. However, this would imply that, when classifying a new document containing a word not present in the documents of a given class, it would get assigned a probability of zero, even though the text may otherwise look a lot like the documents from said class. To deal with this issue, one could simply drop words that are unknown to the training corpus, but a better approach is *Laplace Smoothing*, in which a non-zero probability is assigned to every word beforehand. This is achieved by adding a value ${tex`\\alpha`} to any count, so that the probability estimates change from`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":353,"value":"tex.block`\\hat P(w|c) = \\frac{count(w,c)}{\\sum_{w \\text{ in } V} count(w,c) } = \\frac{count(w,c)}{N_c}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":357,"value":"md`> to`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":359,"value":"tex.block`\\hat P(w|c) = \\frac{count(w,c)}{\\sum_{w \\text{ in } V} count(w,c) }= \\frac{count(w,c) + \\alpha}{N_c+\\alpha|V|}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":361,"value":"md`> where ${tex`count(w,c)`} is the number of times word *w* appears in the documents of class *c*, ${tex`N_c`} is the total number of tokens of the respective class, and ${tex`|V|`} is the overall size of the vocabulary. Often, ${tex`\\alpha`} is chosen to be one. *Laplace Smoothing* is preferable compared to simply discarding unknown tokens because these should decrease the probability of belonging to the respective class; they should just not turn it to zero.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":350,"value":"md`*** \n\n**Exercise 8:** With the number of unique tokens in our training data set being equal to 76,709 (saved as variable *vocabSize*), change the definitons of \\`wordSpamProb\\` and \\`wordNoSpamProb\\` above functions to use Laplace Smoothing.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":383,"value":"vocabSize = 76709\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":340,"value":"md`Our workhorse function to classify new emails can now be implemented in a relatively straightforward manner. Instead of directly evaluating ${tex`\\prod_w P(w|c)`}, which is prone to underflow issues since many of the probabilities will be small, we will take the natural logarithm and calculate the sum ${tex`\\sum_w \\ln P(w|c)`} instead. Taking the logarithm is a monotonic transformation, which does not change the rank order of the untransformed values. Therefore, predictions made from the model are not affected by this choice.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":337,"value":"function classifyEmail( text ) {\n var body = extractBody( text );\n var tokens = stdlib.tokenize( body );\n var spamScore = stdlib.base.ln( groupProbs[ \"spam\" ] );\n for ( let i = 0; i < tokens.length; i++ ) {\n spamScore += stdlib.base.ln( wordSpamProb( tokens[i] ) );\n }\n var nospamScore = stdlib.base.ln( groupProbs[ \"nospam\" ] );\n for ( let i = 0; i < tokens.length; i++ ) {\n nospamScore += stdlib.base.ln( wordNospamProb( tokens[i] ) );\n }\n return spamScore > nospamScore ? 'spam' : 'nospam';\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"md`Test the function out on a few of the emails from \\`test\\`. Do we make the correct predictions?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"md`**Challenge 2:** Let us assess the performance of our model by creating a table of the percentages of emails that are correctly classified in each of the groups (from both the training and test sets). What do you observe?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":622,"value":"''","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":619,"value":"md`**Challenge 3:** Can you think of some other features besides the words that could discriminate between the classes? Think about stuff like the number of capitalized words or $ signs. Check whether your assumption is correct and there is a difference in their frequency among the spam and non-spam mails. The process of identifying and creating new variables that are predictive of the outcome is often called feature engineering. Notice that the Naive Bayes classifier is not restricted to words, but could use all these other features as well!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":626,"value":"''","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"md `## KDEs and Clustering`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"md`### Kernel Density Estimation (KDE)`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"md`Over the course of this workshop, we got to know several known statistical distributions and how to work with them. Now imagine that you have observations from an unknown distribution and would like to estimate the distribution they are drawn from; for example, as part of a machine learning algorithm. If you can make some distributional assumption, e.g. that the data are generated from a normal distribution, then the problem reduces to estimating the parameters of the distribution, which is usually done via the [maximum likelihood](https://en.wikipedia.org/wiki/Maximum_likelihood_estimation) method.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"md` To estimate distributions without making any strong parametric assumptions, one can use a class of models called kernel density estimators (KDEs). In contrast to a parametric model, where we encode all information on the distribution in their parameters, KDEs are non-parametric and use all data points to form an estimate for a given input value. Since they can learn the shape of the density from the data automatically, they are very flexible and can even learn complicated distributions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"md`To see how this works, let us imagine we have data drawn from the displayed distribution. The density function for the plotted distribution is displayed below the plot`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"pltTruePDF = {\n var x = stdlib.linspace( 0, 30, 200 );\n var y = x.map( function( x ) { return truePDF( x ) } );\n var plt = stdlib.plot([ x ], [ y ], {\n 'xLabel': 'Value',\n 'yLabel': 'Density',\n 'width': 600,\n 'xMax': 15,\n 'xMin': 0\n })\n return plt;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"html`${pltTruePDF.render('html')}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"function truePDF( x ) {\n return weight * stdlib.base.dists.normal.pdf( x, 2, 1 ) + (1-weight) * stdlib.base.dists.normal.pdf( x, 9, 2 );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":" weight = 0.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":213,"value":"md`Such a distribution is called a mixture distribution. In this case, we have a mixture of two normal distributions, one with mean two and standard deviation one and another one with mean nine and standard deviation two. The density function is a weighted sum of the individual PDFs with non-negative weights that sum to one.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":570,"value":"md`**Exercise 9:** Instead of hardcoding the weight, turn the cell into a slider input. Vary the weights to investigate the effect of different *mixture weights*. How does the *mixture distribution* change?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":408,"value":"md`The kernel density estimator for an unknown [density](https://en.wikipedia.org/wiki/Probability_density_function) is defined as`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":84,"value":"tex.block`\\displaystyle {\\hat {f}}_{h}(x)={\\frac {1}{nh}}\\sum _{i=1}^{n}K{\\Big (}{\\frac {x-x_{i}}{h}}{\\Big )},`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"md`where ${tex`n`} is the number observations, ${tex`K`} is a so-called [kernel function][1] and ${tex`h`} the bandwidth.\n\n[1]: https://en.wikipedia.org/wiki/Kernel_(statistics)`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"md`We can implement the kernel density estimator as follows:`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"function fhat( x, xs, K, h ) {\n var out = 0;\n var n = xs.length;\n for ( var i = 0; i < n; i++ ) {\n out += K( ( x - xs[i] ) / h );\n }\n return out / ( n*h );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":474,"value":"md`To gain some intuition into how KDEs work, let us assume that we have observed the following data points:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":477,"value":"xobs = [ 1, 3, 4, 9, 13 ] ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"md`The next figure shows a kernel density constructed from the five data points located at the black rugs. The KDE works by smoothing each of these observations into a bump (displayed as the dashed red lines), whose shape is determined by the chosen kernel function.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":511,"value":"md`For the kernel function, we use the Gaussian kernel, i.e. a [standard normal density](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/stats/base/dists/normal/pdf) (you will later explore different options!).`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":458,"value":"html`${plotKDE.render('html')}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"md` These bumps are then summed together to obtain the KDE, displayed in above plot as the solid blue line. In regions with many data points, the KDE will thus return large values since many bumps were summed together, whereas the KDE will return smaller values for regions with only few observations.\n\nChoosing an appropriate bandwidth is a delicate problem. Many solutions have been proposed, but there is no clear best one. For the sake of simplicity, we will employ a rule of thumb by Silverman that is often used in practice. For the data set above, the rule chooses the value ${tex`h \\approx ${stdlib.base.roundn(h,-3)}`}. Let us store this in a variable of said name:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"h = guessBandwidth( xobs )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":664,"value":"md`**Exercise 10:** Change the values of the points and/or the number of points in \\`xobs\\` and observe how the kernel density estimate changes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":573,"value":"md`**Exercise 11:** Instead of using a rule of thumb to change the bandwidth, set it manually and try out different values. What is the effect of increasing/decreasing the bandwidth? Observe how the results change. One case should correspond to what is called *undersmoothing*, the other one *oversmoothing*. Can you see why?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":577,"value":"md`**Exercise 12:** So far, we have been using the Gaussian kernel, but there are many other available [kernel functions][1]. You can use any kernel function with KDE, but different chocies will lead to estimates with different characteristics. The linked Wikipedia article contains a table with a long list of them. Pick one, implement it, and and override the K cell to use your new kernel function. The plots should automatically update and reflect your new choice.\n\n[1]: https://en.wikipedia.org/wiki/Kernel_(statistics)\n\n[1]:https://en.wikipedia.org/wiki/Kernel_(statistics)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":628,"value":"// Set K to `stdlib.base.dists.normal.pdf.factory( 0.0, 1.0 )` to restore default\nK = stdlib.base.dists.normal.pdf.factory( 0.0, 1.0 )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"md`**Silverman's Rule**\n> A commonly used rule of thumb for choosing the bandwidth is Silverman's reference bandwidth, which is defined as follows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"md` > ${tex.block`h \\approx 0.9 A n^{-1/5}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":547,"value":"function guessBandwidth( x ) {\n var A = stdlib.base.min( stdev( x ), iqr( x ) );\n return 0.9 * A * stdlib.base.pow( x.length, -1/5 );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"\nmd`> where ${tex`A = \\min( \\hat \\sigma, IQR )`} is the minimum of the sample standard deviation and the interquartile range. A previous rule of thumb by Silverman uses the value 1.06 in place of 0.9, but this choice of bandwidth is prone to miss bimodality.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":588,"value":"md`**Exercise 13**: Generate a sample of size 100 from the mixture distribition displayed in \\`pltTruePDF\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"md`> **Hint:** You can sample from a mixture by first drawing an indicator variable for the mixture component and then drawing from the chosen distribution.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"''","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":137,"value":"md`**Exercise 14:** We have now everything in place to run generate a kernel density estimate for the data set created in exercise 4 and compare it with the true underlying distribution.\tFirst, create a linearly spaced array of values between 0 and 14 using [\\`linspace\\`](https://github.com/stdlib-js/stdlib/tree/a5fc046e1a13d5938d45b8cb70b45fe14fbbe5ed/lib/node_modules/%40stdlib/math/utils/linspace) at whose values we will evaluate the true density as well as our estimator. Then, create a plot and overlay both the true density function \\`truePDF\\` as well as our estimate \\`fhat\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":140,"value":"plt14 = {\n // Edit me!\n var plt = stdlib.plot( [], [] );\n plt.colors = [ 'red', 'blue' ];\n plt.width = 600;\n return plt;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"html`${plt14.render('html')}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"md`### Clustering using KDEs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":153,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"md`### Mean-Shift Algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"md`1. Input: A KDE and data points ${tex`x_1,\\ldots,x_n`}\n2. For each point ${tex`x_j`}, set ${tex`a_j^{(0)} = x_j`} and iterate the following until convergence is achieved:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"tex.block`a_j^{(s+1)} = \\frac{\\sum_{i=1}^n x_i K\\left( \\tfrac{a_j^{(s)}-x_i}{h} \\right)}{ \\sum_{i=1}^n K\\left( \\tfrac{a_j^{(s)}-x_i}{h} \\right)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"md `**Exercises 15:** Implement the mean-shift algorithm and obtain the cluster assignments for the generated data.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"function meanShift( xs, K, h ) {\n var a = stdlib.copy( xs );\n for ( var j = 0; j < a.length; j++ ) {\n // Code comes here...\n }\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"md`> **Hint:** Instead of checking for convergence at each iteration, in a first pass it might be easier to just run the algorithm for a sufficiently large number of iterations (say a few hundred).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`\n* * *\n\n## Notes\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"md`\n- This notebook uses [stdlib](https://github.com/stdlib-js/stdlib), a standard library for JavaScript and Node.js, with an emphasis on numerical and scientific computing applications. [stdlib](https://github.com/stdlib-js/stdlib) contains over 2,000 functions for mathematics, statistics, data processing, streams, and more. For more information, see the GitHub [repository](https://github.com/stdlib-js/stdlib).\n- This notebook is part of a series of notebooks used as part of a workshop on data science in JavaScript held at the [International JavaScript Conference](https://javascript-conference.com/) (iJS), held in London, UK, 11-13 April 2018.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"md`\n* * *\n\n## Appendix\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"md`\nAn appendix containing functionality used in running this notebook.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"stdlib = require( \"https://unpkg.com/@stdlib/stdlib@0.0.43/dist/stdlib-flat.min.js\" )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"datasets = {\n var pkg = await require( \"https://unpkg.com/@stdlib/stdlib@0.0.34/dist/stdlib-datasets-tree.min.js\" );\n return pkg.datasets;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":537,"value":"function stdev( arr ) {\n var delta;\n var mean;\n var len;\n var M2;\n var i;\n var x;\n delta = 0.0;\n mean = 0.0;\n M2 = 0.0;\n len = arr.length;\n for ( i = 0; i < len; i++ ) {\n x = arr[ i ];\n delta = x - mean;\n mean += delta / (i+1);\n M2 += delta * ( x - mean );\n }\n return stdlib.base.sqrt( M2 / ( i - 1 ) );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":540,"value":"function quantile( arr, p ) {\n var len = arr.length;\n var id;\n var h;\n h = ( len - 1.0 ) * p + 1.0;\n id = stdlib.base.floor( h ) - 1;\n return arr[ id ] + ( h - stdlib.base.floor( h ) ) * ( arr[ id + 1 ] - arr[ id ] );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":544,"value":"function iqr( arr ) {\n // Copy and sort data:\n arr = arr.slice();\n arr.sort( (a,b) => a-b );\n return quantile( arr, 0.75 ) - quantile( arr, 0.25 );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`\n* * *\n\n## License\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"md`\nCopyright (c) 2018 The Stdlib Authors.\n\nLicensed under the Apache License, Version 2.0 (the \"License\");\nyou may not use this file except in compliance with the License.\nYou may obtain a copy of the License at\n\n http://www.apache.org/licenses/LICENSE-2.0\n\nUnless required by applicable law or agreed to in writing, software\ndistributed under the License is distributed on an \"AS IS\" BASIS,\nWITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\nSee the License for the specific language governing permissions and\nlimitations under the License.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3f","stdlib":"1"}} 33:null