A fundamental problem in machine learning and data analytics is to partition or classify objects in...

 

Transcribed Image Text:

A fundamental problem in machine learning and data analytics is to partition or classify objects in a 'natural' way based on their 'distances' to each other. In this question, you are given an integer N, and n points x₁, X2X₁ in a horizontal line. We want to partition the n points into N groups so that intuitively within each group the points are 'close' together. The following is an example of what may be a good way of partitioning the following n=8 points into N=3 groups, and what may be a bad way: 12 13 Good! H More precisely, each point x is a number on the x-axis. To measure how 'good' a partitioning is, we define the error of a group of points Xp, Xp+1,...,xqto be (xp-H)²+ (Xp+1-H)² ++ (x₂ - μ)² where μ = (Xp, Xp+1,xq)/(q-p+1) is the average of the points. Our objective is to find the optimal way of partitioning the points into N groups so that the sum of errors of all groups is minimized. Bad? For example, the 'bad' way of partitioning for the above example gives an error of: Group 1: average = (1+2)/2 = 1.5, error = (1-1.5)²+(2-1.5)² = 0.5 Group 2: average = (3+6+8+12) /4 = 7.25, error = (3-7.25)² + (6-7.25)² + (8-7.25)²+(12-7.25)² = 42.75 Group 3: average = (13+15)/2 = 14, error = (13-14)² + (15 – 14)² = 2 Total error = 0.5+ 42.75 +2 = 45.25. We divide the points in such a way that only consecutive points (along the line) may fall into the same group. Design an efficient algorithm for this problem. You should: (the following is described in terms of the design of a dynamic programming algorithm, since you almost certainly should use it) • In plain English or using some mathematical notation, give a recursive formulation of the problem. (Hint: one possible approach is to define F(i, k) to be the error of the optimal partition of the first i points x₁, ..., X¡ into k groups, where in and k≤ N. The value of F(i, k) can be found recursively: consider all possible locations where the last (k-th) group can begin.) • Write a program in C++ of the algorithm that is based on this formulation (Pseudocode may be accepted however some points will be lost). A fundamental problem in machine learning and data analytics is to partition or classify objects in a 'natural' way based on their 'distances' to each other. In this question, you are given an integer N, and n points x₁, X2X₁ in a horizontal line. We want to partition the n points into N groups so that intuitively within each group the points are 'close' together. The following is an example of what may be a good way of partitioning the following n=8 points into N=3 groups, and what may be a bad way: 12 13 Good! H More precisely, each point x is a number on the x-axis. To measure how 'good' a partitioning is, we define the error of a group of points Xp, Xp+1,...,xqto be (xp-H)²+ (Xp+1-H)² ++ (x₂ - μ)² where μ = (Xp, Xp+1,xq)/(q-p+1) is the average of the points. Our objective is to find the optimal way of partitioning the points into N groups so that the sum of errors of all groups is minimized. Bad? For example, the 'bad' way of partitioning for the above example gives an error of: Group 1: average = (1+2)/2 = 1.5, error = (1-1.5)²+(2-1.5)² = 0.5 Group 2: average = (3+6+8+12) /4 = 7.25, error = (3-7.25)² + (6-7.25)² + (8-7.25)²+(12-7.25)² = 42.75 Group 3: average = (13+15)/2 = 14, error = (13-14)² + (15 – 14)² = 2 Total error = 0.5+ 42.75 +2 = 45.25. We divide the points in such a way that only consecutive points (along the line) may fall into the same group. Design an efficient algorithm for this problem. You should: (the following is described in terms of the design of a dynamic programming algorithm, since you almost certainly should use it) • In plain English or using some mathematical notation, give a recursive formulation of the problem. (Hint: one possible approach is to define F(i, k) to be the error of the optimal partition of the first i points x₁, ..., X¡ into k groups, where in and k≤ N. The value of F(i, k) can be found recursively: consider all possible locations where the last (k-th) group can begin.) • Write a program in C++ of the algorithm that is based on this formulation (Pseudocode may be accepted however some points will be lost).

Answer rating: 100% (QA)

Sure Heres an efficient algorithm based on dynamic programming for the problem you described The pro... View the full answer