# Stock Market Prediction Using Microblogging Sentiment Analysis and Machine Learning
## 2 Background
### Classification Algorithms  
Classification algorithms are predictive computations that recognize, comprehend, and categorize data [24, 25]. A list of such methods utilized in this work is compiled here. K-nearest Neighbors (KNN) is a lazy and non-parametric algorithm. It computes the distance employing the most popular distance function, the Euclidean distance \(d\), which determines the difference or similarity (or else the shortest distance) between two instances/points \((x_{1},y_{1})\) and \((x_{2},y_{2})\), according to (1). \[d((x_{1},y_{1}),(x_{2},y_{2}))=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}} \tag{1}\]  
For a particular value of \(K\), the method will determine the K-Nearest Neighbors of the data point and then assign the class to the data point based on the class with the most data points among the K-Neighbors [26]. Following the calculation of the distance, the input \(x\) is allocated to the class with the highest probability according to (2). \[P(y=j|X=x)=\frac{1}{K}\sum\limits_{i\in A}I(y^{(i)}=j) \tag{2}\]  
Support Vector Machine (SVM) is a classification method that solves binary problems by searching for an optimal hyperplane in high-dimensional space, isolating the points with the greatest margin. If two categories of points are differentiated, then there is a hyperplane that splits them. The purpose of this classification is to calculate a decent separating hyperplane between two outcomes. This is achieved by locating the hyperplane that optimizes the margin in between categories or classes [27]. In more detail, given training vectors \(x_{i}\in\mathbb{R}^{p}\), \(i=1,\ldots,n\), in two classes, and a vector \(y\in\{1,-1\}^{n}\), the main goal is to find \(w\in\mathbb{R}^{p}\) and \(b\in\mathbb{R}\) such that the prediction given by \(\text{sign}(w^{T}\phi(x)+b)\) is correct for most of the samples. The SVM solves the problem (3):  
\[ \begin{array}{c}\min\limits_{w,b,\xi}\frac{1}{2}w^{T}w+C\sum\limits_{i=1}^{n }\zeta_{i}\\ \text{subject to}\quad y_{i}(w^{T}\phi(x_{i})+b)\geq 1-\zeta_{i},\\ \quad\quad\quad\quad\quad\quad\quad\zeta_{i}\geq 0,i=1,\ldots,n\end{array}  \tag{3}\]  
Therefore, the aim is to minimize \(||w||^{2}=w^{T}w\), while applying a penalty when a sample is not correctly classified. Preferably, the value \(y_{i}(w^{T}\phi(x_{i})+b)\) would be \(\geq\)1 for all of the samples indicating a perfect prediction. Nonetheless, problems are not always perfectly separable with a hyperplane allowing some samples to be at a distance \(\zeta_{i}\) from their ideal margin boundaries. Logistic Regression (LR) is classification technique estimating the likelihood that an observation belongs to one of two classes (1 or 0). LR employs a complicated function (sigmoid), which transfers predicted values to their corresponding distributions of likelihoods. The logistic function is a sigmoid function given by (4) and pushes the values from \((-n,n)\) to (0, 1) [28]. \[F(x)=\frac{1}{1+e^{-x}}=\frac{e^{x}}{e^{x}+1} \tag{4}\]  
Naive Bayes (NB) is a classification technique that may be used for binary and multi-class classification. NB techniques are a type of supervised learning algorithms that use Bayes' theorem with the 'naive' assumption of conditional independence between every pair of features given a class variable \(y\) and a dependent feature vector from \(x_{1}\) to \(x_{n}\), as stated in (5). When compared to numerical variables, NB performs well with categorical input data. It is helpful for anticipating data and creating predictions based on past findings [29]. \[P(y\mid x_{1},\ldots,x_{n})=\frac{P(y)P(x_{1},\ldots,x_{n}\mid y)}{P(x_{1},\ldots, x_{n})} \tag{5}\]  
Decision Tree (DT) is a classification method that uses decision rules to predict the class of the target variable. For the purpose of creating a tree, the 'divide and conquer' strategy can be used. The parameter utilized for the root node is chosen because it has a high p-value, and then the tree is partitioned into sub trees. The sub trees are further divided, employing the same technique until they get to the leaf node.