A fundamental problem in machine learning and data analytics is to partition or classify objects in...
Fantastic news! We've Found the answer you've been seeking!
Question:
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).
Expert Answer:
Answer rating: 100% (QA)
Sure Heres an efficient algorithm based on dynamic programming for the problem you described The pro... View the full answer
Related Book For
Posted Date:
Students also viewed these accounting questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
In this question assume that p and q are atomic formulae. (a) Compare and contrast path formulae and state formulae in temporal logic. [4 marks] (b) Describe and contrast the meanings of F(G p) and...
-
Remove left recursion in the following grammar. Show each step. Hint: First remove direct left recursion. Then the indirect left recursion. A AB | Aab | BA| a Bb | | b
-
The Carnegie Classification of Institutes of Higher Education categorizes colleges and universities on the basis of their research and degree-granting activities. Universities that grant doctoral...
-
Write out the first eight terms of each series to show how the series starts. Then find the sum of the series or show that it diverges. 4n n=2
-
Assume the same information as in question 4. Also assume that beginning work in process had \($6,000\) in conversion cost and that \($84,000\) in conversion is added during this period. What is the...
-
Recognition of Profit and Balance Sheet Amounts for Long-Term Contracts Yanmei Construction Company began operations January 1, 2010. During the year, Yanmei Construction entered into a contract with...
-
Prove that f(xx, yy) = (i=1 (yy) (1/2) x) (i-1 (yy)(1/2)x}) where 1 and 2 refer to periods 1 and 2 respectively; satisfies the condition that: fk(ykx,ykk) = for all k=1,...K then f(yx,y)=\
-
The Carolina Cougars is a major league baseball expansion team beginning its third year of operation. The team had losing records in each of its first 2 years and finished near the bottom of its...
-
Jillian Corporation has a $375 petty cash fund. At the end of each month, Jillian's petty cash custodian presents the records of the petty cash transactions. On August 31, there was $33 cash...
-
Evaluate amazon's website in terms of usability, organization, ease of use, convenience to buy, and sales experience. Is the company's website mobile friendly? Does the company utilize a mobile app...
-
For this journal, begin putting together your ideas for your portfolio, which will be submitted at the end of this course. Once you have reviewed the assignment details and instructions, post your...
-
You company purchases a specialized vehicle for your project costing $40,000. The company policy is to use the Declining Balance Method to depreciate assets. If the useful life of the vehicle is 8...
-
Lions' Den is a television program wherein start-up companies pitch their business to well-known businesspeople, who decide whether or not to make an offer on the business venture. Right now, Hello...
-
Washington Investments needs $50,000 to replace their building's roof in 10 years time. They can earn an interest rate of 10% compounded annually. What amount will they need to invest at the end of...
-
Ultravision Inc. anticipates sales of $290,000 from January through April. Materials will represent 50 percent of sales, and because of level production, material purchases will be equal for each...
-
What does non-recourse financing mean?
-
The market for flu shots during late fall is shown in the following table: Suppose the community derives a positive externality of $10 for every flu shot administered. What is the extent of market...
-
At the core of the externalities issue is the lack of clarity concerning property rights. Discuss.
-
How does the problem of double counting arise in calculating GDP, and how is it corrected?
-
State whether you think a business would recognise the following as an expense. When would it be recognised? a Depreciation $350 b Wages to be paid in the next month $1200 c Electricity bill due to...
-
What is the difference between operating expenses and non-operating expenses. Give examples of each.
-
What is the link between the income statement and the statement of owners equity?
Study smarter with the SolutionInn App