COMP20008 1 Element of Data processing-期末班 4 Echo Machine Learning Discretization 1. 利用 domain knowledge 来处理 Car speed: 0-40: slow 40-60: medium >60: high 2. Equal-length bin 每一个 bin之间的长度都是相等的 Divide the range of the continuous feature into equal length intervals (bins). If speed ranges from 0-100, then the 10 bins are [0,10), [10,20), [20,30), …[90,100] 3. Equal frequency bin 每一个 bin中所含数据的数量是相等的 Divide range of continuous feature into equal frequency intervals (bins). Sort the values and divide so that each bin has same number of objects COMP20008 2 Regression (Simple Linear Regression Model) Dependent variable: 需要被预测的值，the variable we wish to predict or explain（y） Independent variable: 用来预测的值 the variable used to explain the dependent variable（X） Regression的作用： 根据一个 independent variable变化的值来预测 dependent variable的变化 Predict the value of a dependent variable based on the value of at least one independent variable。 解释 dependent variable变化对 independent variable的影响 Explain the impact of changes in an independent variable on the dependent variable Regression vs Correlation Correlation Regression Indicate the relationship between independent variable and dependent variable Describes how an independent variable is numerically related to the dependent variable X and Y Y and X0 X1 X2 Describe current data Predict future data Necessarily imply causality Imply causality Correlation analysis is used to measure strength/ direction of the relationship between two variables Predict future data, find relationship Simple Linear Regression Model 只有一个 independent variable X，Only one independent variable, X X和 Y之间是线性关系。Relationship between and Y is described by a linear function Assume Y是由于 X改变而改变。Changes in Y are assumed to be caused by changes in X（两者之间有 correlation） COMP20008 3 Model i： 第 i条 instance Dependent Variable Yi: 我们需要预测的值 Intercept b0：constant，当 x为 0时，y的值是多少。estimated average value of Y when the value of X is zero(intercept) Slope coefficient b1：代表 regression line 的 slope，每增长一个单位的 b1，y会因此改变 多少。b1 is the estimated change in the average value of Y as a result of a one-unit change in X(slope) Independent variable Xi: feature Error term: 估算值与实际值的差。Error term越小则说明 estimate的 y越接近实际值。 COMP20008 4 Least Squares Method 这里我们使用 Least Squares的方法来找出最合适的 b0和 b1 将 error term最小化。（计算不涉及） Interpolation vs. Extrapolation Regression模型的另外一个局限就是只能预测 Relevant range for interpolation。 只能预测所给范围内的数据，而超出范围的数据无法保证。 Evaluate Regression Model COMP20008 5 1. SST = total sum of squares Measures the variation of the Yi values around their mean Y 所有 response variable的 total variation 2. SSR = regression sum of squares Explained variation attributable to the relationship between X and Y 可以被模型解释出来的 variation 3. SSE = error sum of squares Variation attributable to factors other than the relationship between X and Y 无法被模型解析出来的 variation Coefficient of Determination 2 2 (r-squared) = SSR/ SST , 0 < 2 ≤ 1 代表模型解析出来的 variation占全部 variation的比例. 当2越接近 1，说明我们的模型把 variation解析得越完整。 SSE = 0，all points perfectly fit to our model. 让2越小，则说明我们的模型可以解释出的 variation越小。 Assumptions of Linear Regression 1. Linearity: The underlying relationship between X and Y is linear 假设 x 和 y之间的关系是 linear relationship COMP20008 6 2. Independence of residuals: Residual values (also known as fitting errors) are statistically sound and sum to zero (residual 之间需要 independent，有 sum to zero来判断) 3. Examine for constant variance for all levels of X 检查所有的 variance 是不是都是 constant variance Residual是每一个 predict value 和 observed value之间的差。 通过 residual的 visualization我们可以 check linear regression的三个 assumption 如果 linear regression模型表现不好需要考虑一下是不是 dataset 不满足 assumption COMP20008 7 COMP20008 8 COMP20008 9 Classification Regression VS Classification y: target variable is continuous (key difference to classification) classification：用来预测 class label Regression：用来预测一个 continuous value Decision Trees Decision Tree 决策树，树形结构分类器。 Tree Structure (A flow-chart-like tree structure) 根据 feature的不同选择，同一个 dataset可以建造出无数个不同的决策树。 COMP20008 10 如何决定 split nod 和如何评判 best split DT适合 discrete data， 如果 continuous data需要做额外的 Discretization 对于 DT我们更加倾向于 node结果为 homogeneous class 的节点。
在这门课里我们用 entropy来计算节点的纯度，用 Information Gain来评判 best split。 Gain越大，则说明 split越好。注意，这门课里 information gain和 Mutual information的 计算方法是一样的。 DT Advantages 简单易懂 Easy to interpret Tree的 data structure在 construct的时候非常有效率。 做 test set时 traversal tree速度很快。 DT Disadvantages 在面对复杂的 data structure/data set的时候这种简单的方法可能并不适用。可能会建造出 来一个非常复杂难以得出结果的 tree。 需要自己决定 Depth COMP20008 11 COMP20008 12 COMP20008 13 COMP20008 14 KNN K Nearest Neighbors Classifier, 顾名思义是寻找和 instance最为相近的 instance进行分 类。 Algorithm： 1. 计算每个点与每个点之间的距离，并且记录。Compute distance to other training records 2.为每个点找出与之最接近的 k个邻居。Identify k nearest neighbors 3.利用 k个邻居的 class label来判断当前 data应该属于哪个 class。（本门课采用majority voting的方法来 break the tie。）Use class labels of nearest neighbors to determine the class label of unknown record (e.g., by taking a majority vote) Knn不像 DT，它没有一个真实的模型，相反它全部的 instance就是他的模型。 用 KNN时，我们每次拿到一个新的 test set时，就要将他和全部 instance进行距离计算， 找到最近的 n个 instance并进行分类。因此每次都需要重新计算，花费时间很大。 K的选取 K的选取也很重要，通常情况我们倾向于使用一个奇数作为 k。 如果 K太大，则很容易收到 noisy point的影响 如果 K太大，容易把其他 class的 instance也包含进来。（极端情况：0R） 在遇到 tie的情况时采用Majority vote或者Weight the vote的方法 COMP20008 15 COMP20008 16 COMP20008 17 Clustering K-means The best-known clustering method Algorithm分为四个 step 1. Randomly select k seed points as the initial cluster centroids，随机选择初始点作为 centroids 2. Assign each object to the cluster with the nearest centroid 通过计算公式计算每一个点 和每一个 centroid之间的距离，确认出每一个点应该属于那个 centroid所在从 cluster 3. Compute the centroids of the clusters of the current partitioning (the centroid is the center, i.e., mean point, of the cluster) 算出每一个 cluster的新的 centroid， 4. Go back to Step 2, stop when the assignment does not change。重复 step2，直到 centroid的位置不再更新，每个点的 cluster也不再改变。 注意： 由于我们每次选择的初始点为随机选择，无法保证每次 clustering的结果都是一样的。 默认选择使用 Euclidean distance，也可以选择其他距离公式 一定会 converge 到 local optimum。 Cluster-based outlier detection 思路: An outlier is expected to be far away from any groups of normal objects，outlier应当 是距离每一个 group 都很远。我们这里将每一个 point与其 cluster centroid的距离用源泉 的大小来表示，圆圈越大代表距离 centroid越远。 COMP20008 18 Visual Assessment of Clustering Tendency (VAT) 用 Heat map 通过 (dis)similarity matrix 来做 cluster的 visualization 通常情况下，dissimilarity matrix是乱序的，我们无法从这样的 heat map中找到对应的 clusters，因为 reorder显得格外重要。 VAT algorithm 在面对 complex shaped datasets (either significant overlap or irregular geometries between different clusters), 表现欠佳。 这也是很多 clustering method 都面临的问题，肉眼可以算出的分类机器却不能。 COMP20008 19 COMP20008 20 COMP20008 21 Hierarchical Clustering Agglomerative(聚集) hierarchical clustering method从单个点开始，每一步找到 与之最接近的 pair进行 merge 在每次选择 closest cluster的时候我们有两种方法 1. single linkage： minimum distance between the clusters, 2. complete linkage： maximum distance between the clusters, Strength of MIN: Single linkage: can handle non-similar shapes Limitations of MIN: Single linkage: sensitive to noise and outliers COMP20008 22 Strength of MAX: Complete linkage: Less susceptible to noise and outliers Limitations of Max: Complete linkage: Tends to break large clusters Divisive（分裂） 从全部 instance开始，持续不停地分出 cluster直到每个 cluster只含有一个点 Start with one, all-inclusive cluster At each step, split a cluster until each cluster contains a point (or there are k clusters) Evaluation 一组好的 Clusters应该满足，Cluster内 datapoint的距离很小，而 Clusters之间的距离很 大。这里我们用 sse来进行 evaluation。 COMP20008 23 SSE (sum of squared errors). is the sum of distances of objects from their cluster centroids SSE-elbow method COMP20008 24 COMP20008 25 COMP20008 26 COMP20008 27