Day 9: Multiple Linear Regression HackerRank Solution

Day 9: Multiple Linear Regression HackerRank Solution
Source : https://www.hackerrank.com/challenges/s10-multiple-linear-regression

Objective
In this challenge, we practice using multiple linear regression. Check out the Tutorial tab for learning materials!

Task
Andrea has a simple equation:

for real constants (, , , , ). We can say that the value of depends on features. Andrea studies this equation for different feature sets and records each respective value of . If she has new feature sets, can you help Andrea find the value of for each of the sets?

Note: You are not expected to account for bias and variance trade-offs.

Input Format

The first line contains space-separated integers, (the number of observed features) and (the number of feature sets Andrea studied), respectively.
Each of the subsequent lines contain space-separated decimals; the first elements are features , and the last element is the value of for the line's feature set.
The next line contains a single integer, , denoting the number of feature sets Andrea wants to query for.
Each of the subsequent lines contains space-separated decimals describing the feature sets.

Constraints

Scoring
For each feature set in one test case, we will compute the following:

• . We will permit up to a margin of error.

The normalized score for each test case will be: . If the challenge is worth points, then your score will be .

Output Format

For each of the feature sets, print the value of on a new line (i.e., you must print a total of lines).

Sample Input

2 7
0.18 0.89 109.85
1.0 0.26 155.72
0.92 0.11 137.66
0.07 0.37 76.17
0.85 0.16 139.75
0.99 0.41 162.6
0.87 0.47 151.77
4
0.49 0.18
0.57 0.83
0.56 0.64
0.76 0.18

Sample Output

105.22142.68132.94129.71

Explanation

We're given , so . We're also given , so we determine that Andrea studied the following feature sets:

We use the information above to find the values of , , and . Then, we find the value of for each of the feature sets.

Source : https://www.hackerrank.com/challenges/s10-multiple-linear-regression

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.Arrays;
	public class Solution {
	public static void main(String[] args) {
	/* Read input: Create and fill X,Y arrays */
	Scanner scan = new Scanner(System.in);
	int m = scan.nextInt();
	int n = scan.nextInt();
	double [][] X = new double[n][m + 1];
	double [][] Y = new double[n][1];
	for (int row = 0; row < n; row++) {
	X[row][0] = 1;
	for (int col = 1; col <= m; col++) {
	X[row][col] = scan.nextDouble();
	}
	Y[row][0] = scan.nextDouble();
	}
	/* Calculate B */
	double [][] xtx = multiply(transpose(X),X);
	double [][] xtxInv = invert(xtx);
	double [][] xty = multiply(transpose(X), Y);
	double [][] B = multiply(xtxInv, xty);
	int sizeB = B.length;
	/* Calculate and print values for the "q" feature sets */
	int q = scan.nextInt();
	for (int i = 0; i < q; i++) {
	double result = B[0][0];
	for (int row = 1; row < sizeB; row++) {
	result += scan.nextDouble() * B[row][0];
	}
	System.out.println(result);
	}
	scan.close();
	}
	/* Multiplies 2 matrices in O(n^3) time */
	public static double[][] multiply(double [][] A, double [][] B) {
	int aRows = A.length;
	int aCols = A[0].length;
	int bRows = B.length;
	int bCols = B[0].length;
	double [][] C = new double[aRows][bCols];
	int cRows = C.length;
	int cCols = C[0].length;
	for (int row = 0; row < cRows; row++) {
	for (int col = 0; col < cCols; col++) {
	for (int k = 0; k < aCols; k++) {
	C[row][col] += A[row][k] * B[k][col];
	}
	}
	}
	return C;
	}
	public static double[][] transpose(double [][] matrix) {
	/* Create new array with switched dimensions */
	int originalRows = matrix.length;
	int originalCols = matrix[0].length;
	int rows = originalCols;
	int cols = originalRows;
	double [][] result = new double[rows][cols];
	/* Fill our new 2D array */
	for (int row = 0; row < originalRows; row++) {
	for (int col = 0; col < originalCols; col++) {
	result[col][row] = matrix[row][col];
	}
	}
	return result;
	}
	/******************************************************************/
	/* Matrix Inversion code (the 2 functions below) are from: */
	/* http://www.sanfoundry.com/java-program-find-inverse-matrix/ */
	/******************************************************************/
	public static double[][] invert(double a[][])
	{
	int n = a.length;
	double x[][] = new double[n][n];
	double b[][] = new double[n][n];
	int index[] = new int[n];
	for (int i=0; i<n; ++i)
	b[i][i] = 1;
	// Transform the matrix into an upper triangle
	gaussian(a, index);
	// Update the matrix b[i][j] with the ratios stored
	for (int i=0; i<n-1; ++i)
	for (int j=i+1; j<n; ++j)
	for (int k=0; k<n; ++k)
	b[index[j]][k]
	-= a[index[j]][i]*b[index[i]][k];
	// Perform backward substitutions
	for (int i=0; i<n; ++i)
	{
	x[n-1][i] = b[index[n-1]][i]/a[index[n-1]][n-1];
	for (int j=n-2; j>=0; --j)
	{
	x[j][i] = b[index[j]][i];
	for (int k=j+1; k<n; ++k)
	{
	x[j][i] -= a[index[j]][k]*x[k][i];
	}
	x[j][i] /= a[index[j]][j];
	}
	}
	return x;
	}
	// Method to carry out the partial-pivoting Gaussian
	// elimination. Here index[] stores pivoting order.
	public static void gaussian(double a[][], int index[])
	{
	int n = index.length;
	double c[] = new double[n];
	// Initialize the index
	for (int i=0; i<n; ++i)
	index[i] = i;
	// Find the rescaling factors, one from each row
	for (int i=0; i<n; ++i)
	{
	double c1 = 0;
	for (int j=0; j<n; ++j)
	{
	double c0 = Math.abs(a[i][j]);
	if (c0 > c1) c1 = c0;
	}
	c[i] = c1;
	}
	// Search the pivoting element from each column
	int k = 0;
	for (int j=0; j<n-1; ++j)
	{
	double pi1 = 0;
	for (int i=j; i<n; ++i)
	{
	double pi0 = Math.abs(a[index[i]][j]);
	pi0 /= c[index[i]];
	if (pi0 > pi1)
	{
	pi1 = pi0;
	k = i;
	}
	}
	// Interchange rows according to the pivoting order
	int itmp = index[j];
	index[j] = index[k];
	index[k] = itmp;
	for (int i=j+1; i<n; ++i)
	{
	double pj = a[index[i]][j]/a[index[j]][j];
	// Record pivoting ratios below the diagonal
	a[index[i]][j] = pj;
	// Modify other elements accordingly
	for (int l=j+1; l<n; ++l)
	a[index[i]][l] -= pj*a[index[j]][l];
	}
	}
	}
	}