edegan.com - User contributions [en]

Enclosing Circle Algorithm (Rework)

2017-08-04T18:31:10Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\Users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d 
an example: "C:\\Users\\Name\\Documents\\CityYearAreas.txt"
3. To plot just the circles do the following:
a. go to command prompt and type in cd /d E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
b. type in python plot_wrapper2.py
c. follow the prompts
d. file should pop up in the same directory
*the data must have column headers 'latitude' and 'longitude'*

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Enclosing Circle Algorithm (Rework)

2017-08-04T18:29:00Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\Users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d 
an example: "C:\\Users\\Name\\Documents\\CityYearAreas.txt"
3. To plot just the circles do the following:
a. go to command prompt and type in cd /d E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
b. type in python plot_wrapper2.py
c. follow the prompts
d. file should pop up in the same directory

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Abhijit Brahme (Work Log)

2017-08-04T16:51:50Z

AbhiB: /* 8/3/2017 */

[[Abhijit Brahme]] [[Work Logs]]
[[Abhijit Brahme (Work Log) | (log page)]]

==6/5/2017==
Downloaded Atom IDE along with Juno, a Julia specific console. 
Began looking at MATLAB code for the Entrepreneurship Matching Project and trying to understand it 
Began translating enclosing circle algorithm from python to julia 

==6/6/2017==
Looked through MATLAB code for Entrepreneurshp Matching with James, Ed in-depth 
Understood the general idea of the code; Going to call original author for more details. 
Worked through the Julia implementation of Brute Force Enclosing Circle. (had to install "Combinatorics") 
There are small errors with the number of valid circles; still need to implement plotting circles on map.

==6/7/2017==
FIXED the errors involved with translating Python to Julia for Enclosing Circle (Brute Force) 
Implemented the plots in Julia using PyPlot and Plots (need to Pkg.add("Plots") and Pkg.add("PyPlot")) 
Run time in the Julia implementation is actually 2x as slow for the small test set ( 1.12 s for Julia, .55 for Python) 
Need to look into vectorizing some of the code 
Steps Forward:
1) The code might not be optimized for Julia, so try doing that
2) The code for Julia for overhead might be great so it might be slower on a smaller set; try on a bigger set of test points
3) Come up with a better algorithm
Code Location:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle

==6/8/2017==
Ran the "bigexample" for Julia and Python Brute Force.... still running. 
Only got through about 7 combinations in about 8 hours...not very promising. 
Quit the program. It started taking up about 50% memory 
Began working on enclosing circle algorithm. Found promising information regarding a constrained K-means algorithm 
working on implementing the constrained K-means with the smallest enclosing circle to solve the Enclosing Circle Problem 
Code Location for New Enclosing Circle:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==6/9/2017==
Wrote up the code for the new algorithm. It runs blazing fast. 
We are worried about the optimality of the solution. I don't take into account border points. 
These are points that could be shared by circles. An idea is to add border points into both clusters, then run the smallest enclosing circle on those sets of points. 
I'll include a full Algorithm write-up on Monday once I have all the kinks worked out.

==6/12/2017==
Solved the issue of points not being shared by iterating through all possible splits (ie k = 1:floor(numpoints/n)) 
Algorithm runs much slower due to iterating through all K, but it is still faster than others 
I tried a version where I don't keep "K" constant throughout the loop. This converged to a better solution 
I ended up changing K to 2 after the first split. (first split points into 10 points then split those ten points into 2, etc) 

==6/13/2017==
Will run previous algorithm (Peter and Christy's) and compare to mine 
If not the same, will update [[Enclosing Circle Algorithm]] page with my algorithm 

==6/14/2017==
Ran Christy and Peter's algorithm on a small data sample. It worked faster than mine, and achieved the correct answer. 
Currently running their algorithm on a much larger data sample. It is still running, and exhibits slower run time than mine. 
Will leave it running to see what it converges to.

== 6/15/2017==
Built a html scraper in Python to scrape Accelerator data from [http://gan.co/members]
The code and resulting tab-separated text file is located in:
E:\McNair\Projects\Accelerators\Web Scraping for Accelerators

== 6/16/2017 ==
Attempted to try and plot the circles for Houston to Google Maps. 
Succeeded in plotting the points themselves but not the circles 
This is a bit strange considering I reused code from the previous project.
==6/19/2017==
Succeeded in plotting the circles for Houston on Google Maps 
Algorithm is faster than previous algorithm. 
Made new page for the project .

==6/20/2017==
Created a script in python to concatenate 162 excel files
The file is located in the following location:
"E:\McNair\Projects\SBIR\Aggregate SBIR"
It is titled "concat_excel.py" 
The text file is in the folder, titled "SBIR" 

==6/23/2017==
fixed some bugs in the k-means based enclosing circle algorithm 
updated [[Enclosing Circle Algorithm (Rework)]] 
started running the algorithm on list of houston city coords 

==6/26/2017==
For a total of 41 coordinate sets, the algorithm completed the plots in about 32 hours. 
Average run time at a little over an hour per coordinate set 
Added functionality that would save the area of the total circles to a text file 
Running this now and will be completed end of the day tomorrow. 
Worked through the MATLAB code for the monte carlo 
Stripped the code for MSM,Monte Data, Industry 4, and Genetic Algorithm 
Will run tomorrow and adjust the data locations to try and debug 

==6/27/2017==
Identified some key errors in the stripped code for the Monte
1. The genetic algorithm is not returning a scalar value
2. The problem is the objective function is returning an empty vector, instead of a scalar
Made a plotter for Diana so she can visualize Houston Start-Up Data
==6/28/2017==
Fixed the bug. It was because we didn't have a global variable in the master script. 
James helped figure this out. 

==6/29/2017==
Figured out there was another bug in the code. After the optimization finished, there is a problem of mismatched dimensions. 
The code itself still takes a very long time to run. 

==6/30/2017==
Fixed the mismatched dimensions problem, but the code is still running. 
Went over a few methods to speed up the code:
1. Use gurobi for the solver
2. run the sampling on a bunch of clusters
Downloaded gurobi:
password: amount
Updated the plotter to include heatmaps. 
The geocode might be erroneous.

==7/10/2017==
Ran the MATLAB code for the monte carlo after fixing the bugs. 
Installed the MATLAB interface for Gurobi 
Worked on finishing some test cases for the enclosing circle. 

==7/11/2017==
The code ran and worked just fine. 
Now I need to figure out how to replace the optimization in the code with a Gurobi optimization. 
Finished the code for test cases on the enclosing circle. 

==7/12/2017==
Ran the enclosing circle and plotted run time vs. number of points 
Received an exponential graph. 
Finished deriving the areas for the test vc data using enclosing circle 
Worked on modularizing the google plotting functions 
Need to make the code a command line tool 

==7/13/2017==
Ran enclosing circle and saw that it used 2.6% of the CPU and ~200 MB of memory. 
Talked to Oliver about parallelizing the code in C++ or Java. 
Talked about using the highest K, with the lowest error to run the algorithm. 
Made an interactive command line tool for plotting the google maps circles 

==7/14/2017==
Started running the enclosing circle for the PhD students. 
Made an interactive command line tool for using the enclosing circle algorithm. 
Started looking at how to attack the MATLAB monte carlo problem using Gurobi. 

==7/17/2017==
Looked at the optimization function for the Monte. 
It is called readme.pdf 
It seems that the output of msmf_corr_coeff.m contains the appropriate objective function. 
It seems that nonlinearcons_msm.m outputs the appropriate constraints. 
Need to look at how to implement this in Gurobi for Matlab.

==7/18/2017==
Helped Diana learn how to implement the circle plotter for startup locations. 
Read up more about the genetic algorithm function in matlab. 

==7/19/2017==
Created a separate script for gmm_2stage_estimation which is used to implement gurobi. 
Was able to implement the lower bound,upper bound of the variables using gurobi. 
Am finding it difficult to describe the objective function in terms of the variables themselves. 
If I could do that, this would be a whole lot easier. 
The objective function does not match the readme.pdf the author has provided. 
Tried running the same program with the altered objective function. 

==7/20/2017==
Currently timing each of the functions involved with this script. 
Matlab encountered an error which forced the closing of the script. 
Will re-run

==7/21/2017==
Ran the monte and timed the functions. 
[[File:monteruntime.png]]

==7/24/2017==
Since the code actually runs now, thought about ways to add more info to what we know about the code. 
Still don't know how the function fed into the genetic algorithm actually relates to the documentation. 
Some ideas for tomorrow:
1. use the actual generations and values from the original script and time it

==7/25/2017==
Did as suggested above. 
Here are the results. 
[[File:runtime2.png]] 

When comparing the two, it seems like changing the generation size just makes the function take longer to run, but even after one generation the fitness function does not improve its value. 
I don't understand why you'd need more than one generation.

==7/28/2017==
Fixed the monte with James' help and utilized integer linear programming inside the genetic algorithm. 
Previously, the author was using a linear program and rounding the results (not advisable). 
We figure there must be some error in the monte because the genetic algorithm does not update. 

==7/31/2017==
The value passed into the genetic algorithm is either 0 or .1642. 
Here are the values of the key variables that determine the input of the genetic algorithm:
1. mm: either .1111 or .2462
2. M0: always .1111
3. W: either 1 or .0240
4. L: always 9
James seems to think the "trueval" is already set close enough to the optimal. 
This seems correct. 

==8/1/2017==
I changed trueval to be a larger margin to see if the genetic algorithm changes. 
And it didn't do anything. The function value always remains at 0 and the variables retain their values. 
We changed the market size, etc and now the function seems to change its values. 

==8/2/2017==
Got the function to work and produce a different outcome. 
Seems to be a problem with the strip_mkt_resample. 
Got a lot of resulting "NaN" values, traced it to stderr. 
We changed a value to an outer product in stderr and ran the code. 

==8/3/2017==
Here is the output when incorporating the outer product instead. 
[[File:monte_using_outer_product.png]]

==8/4/2017==
All the master files will run appropriately with the proper "task". 
These files are located here:
1. E:\McNair\Projects\MatchingEntrepsToVC\AdjustedCode
You literally open up the master.m file and press run.
[[Category: Work Log]]

Abhijit Brahme (Work Log)

2017-08-03T15:48:37Z

AbhiB: /* 8/2/2017 */

File:Monte using outer product.png

2017-08-03T15:47:51Z

AbhiB:

Abhijit Brahme (Work Log)

2017-08-03T15:47:25Z

AbhiB: /* 8/3/2017 */

[[Abhijit Brahme]] [[Work Logs]]
[[Abhijit Brahme (Work Log) | (log page)]]

==6/5/2017==
Downloaded Atom IDE along with Juno, a Julia specific console. 
Began looking at MATLAB code for the Entrepreneurship Matching Project and trying to understand it 
Began translating enclosing circle algorithm from python to julia 

==6/6/2017==
Looked through MATLAB code for Entrepreneurshp Matching with James, Ed in-depth 
Understood the general idea of the code; Going to call original author for more details. 
Worked through the Julia implementation of Brute Force Enclosing Circle. (had to install "Combinatorics") 
There are small errors with the number of valid circles; still need to implement plotting circles on map.

==6/7/2017==
FIXED the errors involved with translating Python to Julia for Enclosing Circle (Brute Force) 
Implemented the plots in Julia using PyPlot and Plots (need to Pkg.add("Plots") and Pkg.add("PyPlot")) 
Run time in the Julia implementation is actually 2x as slow for the small test set ( 1.12 s for Julia, .55 for Python) 
Need to look into vectorizing some of the code 
Steps Forward:
1) The code might not be optimized for Julia, so try doing that
2) The code for Julia for overhead might be great so it might be slower on a smaller set; try on a bigger set of test points
3) Come up with a better algorithm
Code Location:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle

==6/8/2017==
Ran the "bigexample" for Julia and Python Brute Force.... still running. 
Only got through about 7 combinations in about 8 hours...not very promising. 
Quit the program. It started taking up about 50% memory 
Began working on enclosing circle algorithm. Found promising information regarding a constrained K-means algorithm 
working on implementing the constrained K-means with the smallest enclosing circle to solve the Enclosing Circle Problem 
Code Location for New Enclosing Circle:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==6/9/2017==
Wrote up the code for the new algorithm. It runs blazing fast. 
We are worried about the optimality of the solution. I don't take into account border points. 
These are points that could be shared by circles. An idea is to add border points into both clusters, then run the smallest enclosing circle on those sets of points. 
I'll include a full Algorithm write-up on Monday once I have all the kinks worked out.

==6/12/2017==
Solved the issue of points not being shared by iterating through all possible splits (ie k = 1:floor(numpoints/n)) 
Algorithm runs much slower due to iterating through all K, but it is still faster than others 
I tried a version where I don't keep "K" constant throughout the loop. This converged to a better solution 
I ended up changing K to 2 after the first split. (first split points into 10 points then split those ten points into 2, etc) 

==6/13/2017==
Will run previous algorithm (Peter and Christy's) and compare to mine 
If not the same, will update [[Enclosing Circle Algorithm]] page with my algorithm 

==6/14/2017==
Ran Christy and Peter's algorithm on a small data sample. It worked faster than mine, and achieved the correct answer. 
Currently running their algorithm on a much larger data sample. It is still running, and exhibits slower run time than mine. 
Will leave it running to see what it converges to.

== 6/15/2017==
Built a html scraper in Python to scrape Accelerator data from [http://gan.co/members]
The code and resulting tab-separated text file is located in:
E:\McNair\Projects\Accelerators\Web Scraping for Accelerators

== 6/16/2017 ==
Attempted to try and plot the circles for Houston to Google Maps. 
Succeeded in plotting the points themselves but not the circles 
This is a bit strange considering I reused code from the previous project.
==6/19/2017==
Succeeded in plotting the circles for Houston on Google Maps 
Algorithm is faster than previous algorithm. 
Made new page for the project .

==6/20/2017==
Created a script in python to concatenate 162 excel files
The file is located in the following location:
"E:\McNair\Projects\SBIR\Aggregate SBIR"
It is titled "concat_excel.py" 
The text file is in the folder, titled "SBIR" 

==6/23/2017==
fixed some bugs in the k-means based enclosing circle algorithm 
updated [[Enclosing Circle Algorithm (Rework)]] 
started running the algorithm on list of houston city coords 

==6/26/2017==
For a total of 41 coordinate sets, the algorithm completed the plots in about 32 hours. 
Average run time at a little over an hour per coordinate set 
Added functionality that would save the area of the total circles to a text file 
Running this now and will be completed end of the day tomorrow. 
Worked through the MATLAB code for the monte carlo 
Stripped the code for MSM,Monte Data, Industry 4, and Genetic Algorithm 
Will run tomorrow and adjust the data locations to try and debug 

==6/27/2017==
Identified some key errors in the stripped code for the Monte
1. The genetic algorithm is not returning a scalar value
2. The problem is the objective function is returning an empty vector, instead of a scalar
Made a plotter for Diana so she can visualize Houston Start-Up Data
==6/28/2017==
Fixed the bug. It was because we didn't have a global variable in the master script. 
James helped figure this out. 

==6/29/2017==
Figured out there was another bug in the code. After the optimization finished, there is a problem of mismatched dimensions. 
The code itself still takes a very long time to run. 

==6/30/2017==
Fixed the mismatched dimensions problem, but the code is still running. 
Went over a few methods to speed up the code:
1. Use gurobi for the solver
2. run the sampling on a bunch of clusters
Downloaded gurobi:
password: amount
Updated the plotter to include heatmaps. 
The geocode might be erroneous.

==7/10/2017==
Ran the MATLAB code for the monte carlo after fixing the bugs. 
Installed the MATLAB interface for Gurobi 
Worked on finishing some test cases for the enclosing circle. 

==7/11/2017==
The code ran and worked just fine. 
Now I need to figure out how to replace the optimization in the code with a Gurobi optimization. 
Finished the code for test cases on the enclosing circle. 

==7/12/2017==
Ran the enclosing circle and plotted run time vs. number of points 
Received an exponential graph. 
Finished deriving the areas for the test vc data using enclosing circle 
Worked on modularizing the google plotting functions 
Need to make the code a command line tool 

==7/13/2017==
Ran enclosing circle and saw that it used 2.6% of the CPU and ~200 MB of memory. 
Talked to Oliver about parallelizing the code in C++ or Java. 
Talked about using the highest K, with the lowest error to run the algorithm. 
Made an interactive command line tool for plotting the google maps circles 

==7/14/2017==
Started running the enclosing circle for the PhD students. 
Made an interactive command line tool for using the enclosing circle algorithm. 
Started looking at how to attack the MATLAB monte carlo problem using Gurobi. 

==7/17/2017==
Looked at the optimization function for the Monte. 
It is called readme.pdf 
It seems that the output of msmf_corr_coeff.m contains the appropriate objective function. 
It seems that nonlinearcons_msm.m outputs the appropriate constraints. 
Need to look at how to implement this in Gurobi for Matlab.

==7/18/2017==
Helped Diana learn how to implement the circle plotter for startup locations. 
Read up more about the genetic algorithm function in matlab. 

==7/19/2017==
Created a separate script for gmm_2stage_estimation which is used to implement gurobi. 
Was able to implement the lower bound,upper bound of the variables using gurobi. 
Am finding it difficult to describe the objective function in terms of the variables themselves. 
If I could do that, this would be a whole lot easier. 
The objective function does not match the readme.pdf the author has provided. 
Tried running the same program with the altered objective function. 

==7/20/2017==
Currently timing each of the functions involved with this script. 
Matlab encountered an error which forced the closing of the script. 
Will re-run

==7/21/2017==
Ran the monte and timed the functions. 
[[File:monteruntime.png]]

==7/24/2017==
Since the code actually runs now, thought about ways to add more info to what we know about the code. 
Still don't know how the function fed into the genetic algorithm actually relates to the documentation. 
Some ideas for tomorrow:
1. use the actual generations and values from the original script and time it

==7/25/2017==
Did as suggested above. 
Here are the results. 
[[File:runtime2.png]] 

When comparing the two, it seems like changing the generation size just makes the function take longer to run, but even after one generation the fitness function does not improve its value. 
I don't understand why you'd need more than one generation.

==7/28/2017==
Fixed the monte with James' help and utilized integer linear programming inside the genetic algorithm. 
Previously, the author was using a linear program and rounding the results (not advisable). 
We figure there must be some error in the monte because the genetic algorithm does not update. 

==7/31/2017==
The value passed into the genetic algorithm is either 0 or .1642. 
Here are the values of the key variables that determine the input of the genetic algorithm:
1. mm: either .1111 or .2462
2. M0: always .1111
3. W: either 1 or .0240
4. L: always 9
James seems to think the "trueval" is already set close enough to the optimal. 
This seems correct. 

==8/1/2017==
I changed trueval to be a larger margin to see if the genetic algorithm changes. 
And it didn't do anything. The function value always remains at 0 and the variables retain their values. 
We changed the market size, etc and now the function seems to change its values. 

==8/2/2017==
Got the function to work and produce a different outcome. 
Seems to be a problem with the strip_mkt_resample. 
We changed a value to an outer product in stderr and ran the code. 
==8/3/2017==
Here is the output when incorporating the outer product instead. 
[[File:monte_using_outer_product.png]]
[[Category: Work Log]]

File:"monte using outer product.png".png

2017-08-03T15:46:17Z

AbhiB:

Abhijit Brahme (Work Log)

2017-08-03T15:45:16Z

AbhiB: /* 8/2/2017 */

[[Abhijit Brahme]] [[Work Logs]]
[[Abhijit Brahme (Work Log) | (log page)]]

==6/5/2017==
Downloaded Atom IDE along with Juno, a Julia specific console. 
Began looking at MATLAB code for the Entrepreneurship Matching Project and trying to understand it 
Began translating enclosing circle algorithm from python to julia 

==6/6/2017==
Looked through MATLAB code for Entrepreneurshp Matching with James, Ed in-depth 
Understood the general idea of the code; Going to call original author for more details. 
Worked through the Julia implementation of Brute Force Enclosing Circle. (had to install "Combinatorics") 
There are small errors with the number of valid circles; still need to implement plotting circles on map.

==6/7/2017==
FIXED the errors involved with translating Python to Julia for Enclosing Circle (Brute Force) 
Implemented the plots in Julia using PyPlot and Plots (need to Pkg.add("Plots") and Pkg.add("PyPlot")) 
Run time in the Julia implementation is actually 2x as slow for the small test set ( 1.12 s for Julia, .55 for Python) 
Need to look into vectorizing some of the code 
Steps Forward:
1) The code might not be optimized for Julia, so try doing that
2) The code for Julia for overhead might be great so it might be slower on a smaller set; try on a bigger set of test points
3) Come up with a better algorithm
Code Location:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle

==6/8/2017==
Ran the "bigexample" for Julia and Python Brute Force.... still running. 
Only got through about 7 combinations in about 8 hours...not very promising. 
Quit the program. It started taking up about 50% memory 
Began working on enclosing circle algorithm. Found promising information regarding a constrained K-means algorithm 
working on implementing the constrained K-means with the smallest enclosing circle to solve the Enclosing Circle Problem 
Code Location for New Enclosing Circle:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==6/9/2017==
Wrote up the code for the new algorithm. It runs blazing fast. 
We are worried about the optimality of the solution. I don't take into account border points. 
These are points that could be shared by circles. An idea is to add border points into both clusters, then run the smallest enclosing circle on those sets of points. 
I'll include a full Algorithm write-up on Monday once I have all the kinks worked out.

==6/12/2017==
Solved the issue of points not being shared by iterating through all possible splits (ie k = 1:floor(numpoints/n)) 
Algorithm runs much slower due to iterating through all K, but it is still faster than others 
I tried a version where I don't keep "K" constant throughout the loop. This converged to a better solution 
I ended up changing K to 2 after the first split. (first split points into 10 points then split those ten points into 2, etc) 

==6/13/2017==
Will run previous algorithm (Peter and Christy's) and compare to mine 
If not the same, will update [[Enclosing Circle Algorithm]] page with my algorithm 

==6/14/2017==
Ran Christy and Peter's algorithm on a small data sample. It worked faster than mine, and achieved the correct answer. 
Currently running their algorithm on a much larger data sample. It is still running, and exhibits slower run time than mine. 
Will leave it running to see what it converges to.

== 6/15/2017==
Built a html scraper in Python to scrape Accelerator data from [http://gan.co/members]
The code and resulting tab-separated text file is located in:
E:\McNair\Projects\Accelerators\Web Scraping for Accelerators

== 6/16/2017 ==
Attempted to try and plot the circles for Houston to Google Maps. 
Succeeded in plotting the points themselves but not the circles 
This is a bit strange considering I reused code from the previous project.
==6/19/2017==
Succeeded in plotting the circles for Houston on Google Maps 
Algorithm is faster than previous algorithm. 
Made new page for the project .

==6/20/2017==
Created a script in python to concatenate 162 excel files
The file is located in the following location:
"E:\McNair\Projects\SBIR\Aggregate SBIR"
It is titled "concat_excel.py" 
The text file is in the folder, titled "SBIR" 

==6/23/2017==
fixed some bugs in the k-means based enclosing circle algorithm 
updated [[Enclosing Circle Algorithm (Rework)]] 
started running the algorithm on list of houston city coords 

==6/26/2017==
For a total of 41 coordinate sets, the algorithm completed the plots in about 32 hours. 
Average run time at a little over an hour per coordinate set 
Added functionality that would save the area of the total circles to a text file 
Running this now and will be completed end of the day tomorrow. 
Worked through the MATLAB code for the monte carlo 
Stripped the code for MSM,Monte Data, Industry 4, and Genetic Algorithm 
Will run tomorrow and adjust the data locations to try and debug 

==6/27/2017==
Identified some key errors in the stripped code for the Monte
1. The genetic algorithm is not returning a scalar value
2. The problem is the objective function is returning an empty vector, instead of a scalar
Made a plotter for Diana so she can visualize Houston Start-Up Data
==6/28/2017==
Fixed the bug. It was because we didn't have a global variable in the master script. 
James helped figure this out. 

==6/29/2017==
Figured out there was another bug in the code. After the optimization finished, there is a problem of mismatched dimensions. 
The code itself still takes a very long time to run. 

==6/30/2017==
Fixed the mismatched dimensions problem, but the code is still running. 
Went over a few methods to speed up the code:
1. Use gurobi for the solver
2. run the sampling on a bunch of clusters
Downloaded gurobi:
password: amount
Updated the plotter to include heatmaps. 
The geocode might be erroneous.

==7/10/2017==
Ran the MATLAB code for the monte carlo after fixing the bugs. 
Installed the MATLAB interface for Gurobi 
Worked on finishing some test cases for the enclosing circle. 

==7/11/2017==
The code ran and worked just fine. 
Now I need to figure out how to replace the optimization in the code with a Gurobi optimization. 
Finished the code for test cases on the enclosing circle. 

==7/12/2017==
Ran the enclosing circle and plotted run time vs. number of points 
Received an exponential graph. 
Finished deriving the areas for the test vc data using enclosing circle 
Worked on modularizing the google plotting functions 
Need to make the code a command line tool 

==7/13/2017==
Ran enclosing circle and saw that it used 2.6% of the CPU and ~200 MB of memory. 
Talked to Oliver about parallelizing the code in C++ or Java. 
Talked about using the highest K, with the lowest error to run the algorithm. 
Made an interactive command line tool for plotting the google maps circles 

==7/14/2017==
Started running the enclosing circle for the PhD students. 
Made an interactive command line tool for using the enclosing circle algorithm. 
Started looking at how to attack the MATLAB monte carlo problem using Gurobi. 

==7/17/2017==
Looked at the optimization function for the Monte. 
It is called readme.pdf 
It seems that the output of msmf_corr_coeff.m contains the appropriate objective function. 
It seems that nonlinearcons_msm.m outputs the appropriate constraints. 
Need to look at how to implement this in Gurobi for Matlab.

==7/18/2017==
Helped Diana learn how to implement the circle plotter for startup locations. 
Read up more about the genetic algorithm function in matlab. 

==7/19/2017==
Created a separate script for gmm_2stage_estimation which is used to implement gurobi. 
Was able to implement the lower bound,upper bound of the variables using gurobi. 
Am finding it difficult to describe the objective function in terms of the variables themselves. 
If I could do that, this would be a whole lot easier. 
The objective function does not match the readme.pdf the author has provided. 
Tried running the same program with the altered objective function. 

==7/20/2017==
Currently timing each of the functions involved with this script. 
Matlab encountered an error which forced the closing of the script. 
Will re-run

==7/21/2017==
Ran the monte and timed the functions. 
[[File:monteruntime.png]]

==7/24/2017==
Since the code actually runs now, thought about ways to add more info to what we know about the code. 
Still don't know how the function fed into the genetic algorithm actually relates to the documentation. 
Some ideas for tomorrow:
1. use the actual generations and values from the original script and time it

==7/25/2017==
Did as suggested above. 
Here are the results. 
[[File:runtime2.png]] 

When comparing the two, it seems like changing the generation size just makes the function take longer to run, but even after one generation the fitness function does not improve its value. 
I don't understand why you'd need more than one generation.

==7/28/2017==
Fixed the monte with James' help and utilized integer linear programming inside the genetic algorithm. 
Previously, the author was using a linear program and rounding the results (not advisable). 
We figure there must be some error in the monte because the genetic algorithm does not update. 

==7/31/2017==
The value passed into the genetic algorithm is either 0 or .1642. 
Here are the values of the key variables that determine the input of the genetic algorithm:
1. mm: either .1111 or .2462
2. M0: always .1111
3. W: either 1 or .0240
4. L: always 9
James seems to think the "trueval" is already set close enough to the optimal. 
This seems correct. 

==8/1/2017==
I changed trueval to be a larger margin to see if the genetic algorithm changes. 
And it didn't do anything. The function value always remains at 0 and the variables retain their values. 
We changed the market size, etc and now the function seems to change its values. 

==8/2/2017==
Got the function to work and produce a different outcome. 
Seems to be a problem with the strip_mkt_resample. 
We changed a value to an outer product in stderr and ran the code. 
==8/3/2017==
Here is the output when incorporating the outer product instead. 
[[File:"monte using outer product.png"]]
[[Category: Work Log]]

Abhijit Brahme (Work Log)

2017-08-02T16:32:10Z

AbhiB: /* 8/1/2017 */

Abhijit Brahme (Work Log)

2017-08-01T20:18:12Z

AbhiB: /* 8/1/2017 */

Abhijit Brahme (Work Log)

2017-08-01T18:06:39Z

AbhiB: /* 8/1/2017 */

Abhijit Brahme (Work Log)

2017-08-01T18:04:49Z

AbhiB: /* 8/1/2017 */

Abhijit Brahme (Work Log)

2017-08-01T14:48:03Z

AbhiB: /* 7/31/2017 */

Abhijit Brahme (Work Log)

2017-07-31T19:31:08Z

AbhiB: /* 7/31/2017 */

Abhijit Brahme (Work Log)

2017-07-31T18:51:59Z

AbhiB: /* 7/31/2017 */

Abhijit Brahme (Work Log)

2017-07-31T17:27:03Z

AbhiB: /* 7/32/2017 */

Abhijit Brahme (Work Log)

2017-07-31T15:10:27Z

AbhiB: /* 7/32/2017 */

[[Abhijit Brahme]] [[Work Logs]]
[[Abhijit Brahme (Work Log) | (log page)]]

==6/5/2017==
Downloaded Atom IDE along with Juno, a Julia specific console. 
Began looking at MATLAB code for the Entrepreneurship Matching Project and trying to understand it 
Began translating enclosing circle algorithm from python to julia 

==6/6/2017==
Looked through MATLAB code for Entrepreneurshp Matching with James, Ed in-depth 
Understood the general idea of the code; Going to call original author for more details. 
Worked through the Julia implementation of Brute Force Enclosing Circle. (had to install "Combinatorics") 
There are small errors with the number of valid circles; still need to implement plotting circles on map.

==6/7/2017==
FIXED the errors involved with translating Python to Julia for Enclosing Circle (Brute Force) 
Implemented the plots in Julia using PyPlot and Plots (need to Pkg.add("Plots") and Pkg.add("PyPlot")) 
Run time in the Julia implementation is actually 2x as slow for the small test set ( 1.12 s for Julia, .55 for Python) 
Need to look into vectorizing some of the code 
Steps Forward:
1) The code might not be optimized for Julia, so try doing that
2) The code for Julia for overhead might be great so it might be slower on a smaller set; try on a bigger set of test points
3) Come up with a better algorithm
Code Location:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle

==6/8/2017==
Ran the "bigexample" for Julia and Python Brute Force.... still running. 
Only got through about 7 combinations in about 8 hours...not very promising. 
Quit the program. It started taking up about 50% memory 
Began working on enclosing circle algorithm. Found promising information regarding a constrained K-means algorithm 
working on implementing the constrained K-means with the smallest enclosing circle to solve the Enclosing Circle Problem 
Code Location for New Enclosing Circle:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==6/9/2017==
Wrote up the code for the new algorithm. It runs blazing fast. 
We are worried about the optimality of the solution. I don't take into account border points. 
These are points that could be shared by circles. An idea is to add border points into both clusters, then run the smallest enclosing circle on those sets of points. 
I'll include a full Algorithm write-up on Monday once I have all the kinks worked out.

==6/12/2017==
Solved the issue of points not being shared by iterating through all possible splits (ie k = 1:floor(numpoints/n)) 
Algorithm runs much slower due to iterating through all K, but it is still faster than others 
I tried a version where I don't keep "K" constant throughout the loop. This converged to a better solution 
I ended up changing K to 2 after the first split. (first split points into 10 points then split those ten points into 2, etc) 

==6/13/2017==
Will run previous algorithm (Peter and Christy's) and compare to mine 
If not the same, will update [[Enclosing Circle Algorithm]] page with my algorithm 

==6/14/2017==
Ran Christy and Peter's algorithm on a small data sample. It worked faster than mine, and achieved the correct answer. 
Currently running their algorithm on a much larger data sample. It is still running, and exhibits slower run time than mine. 
Will leave it running to see what it converges to.

== 6/15/2017==
Built a html scraper in Python to scrape Accelerator data from [http://gan.co/members]
The code and resulting tab-separated text file is located in:
E:\McNair\Projects\Accelerators\Web Scraping for Accelerators

== 6/16/2017 ==
Attempted to try and plot the circles for Houston to Google Maps. 
Succeeded in plotting the points themselves but not the circles 
This is a bit strange considering I reused code from the previous project.
==6/19/2017==
Succeeded in plotting the circles for Houston on Google Maps 
Algorithm is faster than previous algorithm. 
Made new page for the project .

==6/20/2017==
Created a script in python to concatenate 162 excel files
The file is located in the following location:
"E:\McNair\Projects\SBIR\Aggregate SBIR"
It is titled "concat_excel.py" 
The text file is in the folder, titled "SBIR" 

==6/23/2017==
fixed some bugs in the k-means based enclosing circle algorithm 
updated [[Enclosing Circle Algorithm (Rework)]] 
started running the algorithm on list of houston city coords 

==6/26/2017==
For a total of 41 coordinate sets, the algorithm completed the plots in about 32 hours. 
Average run time at a little over an hour per coordinate set 
Added functionality that would save the area of the total circles to a text file 
Running this now and will be completed end of the day tomorrow. 
Worked through the MATLAB code for the monte carlo 
Stripped the code for MSM,Monte Data, Industry 4, and Genetic Algorithm 
Will run tomorrow and adjust the data locations to try and debug 

==6/27/2017==
Identified some key errors in the stripped code for the Monte
1. The genetic algorithm is not returning a scalar value
2. The problem is the objective function is returning an empty vector, instead of a scalar
Made a plotter for Diana so she can visualize Houston Start-Up Data
==6/28/2017==
Fixed the bug. It was because we didn't have a global variable in the master script. 
James helped figure this out. 

==6/29/2017==
Figured out there was another bug in the code. After the optimization finished, there is a problem of mismatched dimensions. 
The code itself still takes a very long time to run. 

==6/30/2017==
Fixed the mismatched dimensions problem, but the code is still running. 
Went over a few methods to speed up the code:
1. Use gurobi for the solver
2. run the sampling on a bunch of clusters
Downloaded gurobi:
password: amount
Updated the plotter to include heatmaps. 
The geocode might be erroneous.

==7/10/2017==
Ran the MATLAB code for the monte carlo after fixing the bugs. 
Installed the MATLAB interface for Gurobi 
Worked on finishing some test cases for the enclosing circle. 

==7/11/2017==
The code ran and worked just fine. 
Now I need to figure out how to replace the optimization in the code with a Gurobi optimization. 
Finished the code for test cases on the enclosing circle. 

==7/12/2017==
Ran the enclosing circle and plotted run time vs. number of points 
Received an exponential graph. 
Finished deriving the areas for the test vc data using enclosing circle 
Worked on modularizing the google plotting functions 
Need to make the code a command line tool 

==7/13/2017==
Ran enclosing circle and saw that it used 2.6% of the CPU and ~200 MB of memory. 
Talked to Oliver about parallelizing the code in C++ or Java. 
Talked about using the highest K, with the lowest error to run the algorithm. 
Made an interactive command line tool for plotting the google maps circles 

==7/14/2017==
Started running the enclosing circle for the PhD students. 
Made an interactive command line tool for using the enclosing circle algorithm. 
Started looking at how to attack the MATLAB monte carlo problem using Gurobi. 

==7/17/2017==
Looked at the optimization function for the Monte. 
It is called readme.pdf 
It seems that the output of msmf_corr_coeff.m contains the appropriate objective function. 
It seems that nonlinearcons_msm.m outputs the appropriate constraints. 
Need to look at how to implement this in Gurobi for Matlab.

==7/18/2017==
Helped Diana learn how to implement the circle plotter for startup locations. 
Read up more about the genetic algorithm function in matlab. 

==7/19/2017==
Created a separate script for gmm_2stage_estimation which is used to implement gurobi. 
Was able to implement the lower bound,upper bound of the variables using gurobi. 
Am finding it difficult to describe the objective function in terms of the variables themselves. 
If I could do that, this would be a whole lot easier. 
The objective function does not match the readme.pdf the author has provided. 
Tried running the same program with the altered objective function. 

==7/20/2017==
Currently timing each of the functions involved with this script. 
Matlab encountered an error which forced the closing of the script. 
Will re-run

==7/21/2017==
Ran the monte and timed the functions. 
[[File:monteruntime.png]]

==7/24/2017==
Since the code actually runs now, thought about ways to add more info to what we know about the code. 
Still don't know how the function fed into the genetic algorithm actually relates to the documentation. 
Some ideas for tomorrow:
1. use the actual generations and values from the original script and time it

==7/25/2017==
Did as suggested above. 
Here are the results. 
[[File:runtime2.png]] 

When comparing the two, it seems like changing the generation size just makes the function take longer to run, but even after one generation the fitness function does not improve its value. 
I don't understand why you'd need more than one generation.

==7/28/2017==
Fixed the monte with James' help and utilized integer linear programming inside the genetic algorithm. 
Previously, the author was using a linear program and rounding the results (not advisable). 
We figure there must be some error in the monte because the genetic algorithm does not update. 

==7/32/2017==
The value passed into the genetic algorithm is either 0 or .1642. 
Here are the values of the key variables that determine the input of the genetic algorithm:
1. mm: either .1111 or .2462
2. M0: always .1111
3. W: always 1
4. L: always 9

[[Category: Work Log]]

Abhijit Brahme (Work Log)

2017-07-31T15:06:57Z

AbhiB: /* 7/28/2017 */

[[Abhijit Brahme]] [[Work Logs]]
[[Abhijit Brahme (Work Log) | (log page)]]

==6/5/2017==
Downloaded Atom IDE along with Juno, a Julia specific console. 
Began looking at MATLAB code for the Entrepreneurship Matching Project and trying to understand it 
Began translating enclosing circle algorithm from python to julia 

==6/6/2017==
Looked through MATLAB code for Entrepreneurshp Matching with James, Ed in-depth 
Understood the general idea of the code; Going to call original author for more details. 
Worked through the Julia implementation of Brute Force Enclosing Circle. (had to install "Combinatorics") 
There are small errors with the number of valid circles; still need to implement plotting circles on map.

==6/7/2017==
FIXED the errors involved with translating Python to Julia for Enclosing Circle (Brute Force) 
Implemented the plots in Julia using PyPlot and Plots (need to Pkg.add("Plots") and Pkg.add("PyPlot")) 
Run time in the Julia implementation is actually 2x as slow for the small test set ( 1.12 s for Julia, .55 for Python) 
Need to look into vectorizing some of the code 
Steps Forward:
1) The code might not be optimized for Julia, so try doing that
2) The code for Julia for overhead might be great so it might be slower on a smaller set; try on a bigger set of test points
3) Come up with a better algorithm
Code Location:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle

==6/8/2017==
Ran the "bigexample" for Julia and Python Brute Force.... still running. 
Only got through about 7 combinations in about 8 hours...not very promising. 
Quit the program. It started taking up about 50% memory 
Began working on enclosing circle algorithm. Found promising information regarding a constrained K-means algorithm 
working on implementing the constrained K-means with the smallest enclosing circle to solve the Enclosing Circle Problem 
Code Location for New Enclosing Circle:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==6/9/2017==
Wrote up the code for the new algorithm. It runs blazing fast. 
We are worried about the optimality of the solution. I don't take into account border points. 
These are points that could be shared by circles. An idea is to add border points into both clusters, then run the smallest enclosing circle on those sets of points. 
I'll include a full Algorithm write-up on Monday once I have all the kinks worked out.

==6/12/2017==
Solved the issue of points not being shared by iterating through all possible splits (ie k = 1:floor(numpoints/n)) 
Algorithm runs much slower due to iterating through all K, but it is still faster than others 
I tried a version where I don't keep "K" constant throughout the loop. This converged to a better solution 
I ended up changing K to 2 after the first split. (first split points into 10 points then split those ten points into 2, etc) 

==6/13/2017==
Will run previous algorithm (Peter and Christy's) and compare to mine 
If not the same, will update [[Enclosing Circle Algorithm]] page with my algorithm 

==6/14/2017==
Ran Christy and Peter's algorithm on a small data sample. It worked faster than mine, and achieved the correct answer. 
Currently running their algorithm on a much larger data sample. It is still running, and exhibits slower run time than mine. 
Will leave it running to see what it converges to.

== 6/15/2017==
Built a html scraper in Python to scrape Accelerator data from [http://gan.co/members]
The code and resulting tab-separated text file is located in:
E:\McNair\Projects\Accelerators\Web Scraping for Accelerators

== 6/16/2017 ==
Attempted to try and plot the circles for Houston to Google Maps. 
Succeeded in plotting the points themselves but not the circles 
This is a bit strange considering I reused code from the previous project.
==6/19/2017==
Succeeded in plotting the circles for Houston on Google Maps 
Algorithm is faster than previous algorithm. 
Made new page for the project .

==6/20/2017==
Created a script in python to concatenate 162 excel files
The file is located in the following location:
"E:\McNair\Projects\SBIR\Aggregate SBIR"
It is titled "concat_excel.py" 
The text file is in the folder, titled "SBIR" 

==6/23/2017==
fixed some bugs in the k-means based enclosing circle algorithm 
updated [[Enclosing Circle Algorithm (Rework)]] 
started running the algorithm on list of houston city coords 

==6/26/2017==
For a total of 41 coordinate sets, the algorithm completed the plots in about 32 hours. 
Average run time at a little over an hour per coordinate set 
Added functionality that would save the area of the total circles to a text file 
Running this now and will be completed end of the day tomorrow. 
Worked through the MATLAB code for the monte carlo 
Stripped the code for MSM,Monte Data, Industry 4, and Genetic Algorithm 
Will run tomorrow and adjust the data locations to try and debug 

==6/27/2017==
Identified some key errors in the stripped code for the Monte
1. The genetic algorithm is not returning a scalar value
2. The problem is the objective function is returning an empty vector, instead of a scalar
Made a plotter for Diana so she can visualize Houston Start-Up Data
==6/28/2017==
Fixed the bug. It was because we didn't have a global variable in the master script. 
James helped figure this out. 

==6/29/2017==
Figured out there was another bug in the code. After the optimization finished, there is a problem of mismatched dimensions. 
The code itself still takes a very long time to run. 

==6/30/2017==
Fixed the mismatched dimensions problem, but the code is still running. 
Went over a few methods to speed up the code:
1. Use gurobi for the solver
2. run the sampling on a bunch of clusters
Downloaded gurobi:
password: amount
Updated the plotter to include heatmaps. 
The geocode might be erroneous.

==7/10/2017==
Ran the MATLAB code for the monte carlo after fixing the bugs. 
Installed the MATLAB interface for Gurobi 
Worked on finishing some test cases for the enclosing circle. 

==7/11/2017==
The code ran and worked just fine. 
Now I need to figure out how to replace the optimization in the code with a Gurobi optimization. 
Finished the code for test cases on the enclosing circle. 

==7/12/2017==
Ran the enclosing circle and plotted run time vs. number of points 
Received an exponential graph. 
Finished deriving the areas for the test vc data using enclosing circle 
Worked on modularizing the google plotting functions 
Need to make the code a command line tool 

==7/13/2017==
Ran enclosing circle and saw that it used 2.6% of the CPU and ~200 MB of memory. 
Talked to Oliver about parallelizing the code in C++ or Java. 
Talked about using the highest K, with the lowest error to run the algorithm. 
Made an interactive command line tool for plotting the google maps circles 

==7/14/2017==
Started running the enclosing circle for the PhD students. 
Made an interactive command line tool for using the enclosing circle algorithm. 
Started looking at how to attack the MATLAB monte carlo problem using Gurobi. 

==7/17/2017==
Looked at the optimization function for the Monte. 
It is called readme.pdf 
It seems that the output of msmf_corr_coeff.m contains the appropriate objective function. 
It seems that nonlinearcons_msm.m outputs the appropriate constraints. 
Need to look at how to implement this in Gurobi for Matlab.

==7/18/2017==
Helped Diana learn how to implement the circle plotter for startup locations. 
Read up more about the genetic algorithm function in matlab. 

==7/19/2017==
Created a separate script for gmm_2stage_estimation which is used to implement gurobi. 
Was able to implement the lower bound,upper bound of the variables using gurobi. 
Am finding it difficult to describe the objective function in terms of the variables themselves. 
If I could do that, this would be a whole lot easier. 
The objective function does not match the readme.pdf the author has provided. 
Tried running the same program with the altered objective function. 

==7/20/2017==
Currently timing each of the functions involved with this script. 
Matlab encountered an error which forced the closing of the script. 
Will re-run

==7/21/2017==
Ran the monte and timed the functions. 
[[File:monteruntime.png]]

==7/24/2017==
Since the code actually runs now, thought about ways to add more info to what we know about the code. 
Still don't know how the function fed into the genetic algorithm actually relates to the documentation. 
Some ideas for tomorrow:
1. use the actual generations and values from the original script and time it

==7/25/2017==
Did as suggested above. 
Here are the results. 
[[File:runtime2.png]] 

When comparing the two, it seems like changing the generation size just makes the function take longer to run, but even after one generation the fitness function does not improve its value. 
I don't understand why you'd need more than one generation.

==7/28/2017==
Fixed the monte with James' help and utilized integer linear programming inside the genetic algorithm. 
Previously, the author was using a linear program and rounding the results (not advisable). 
We figure there must be some error in the monte because the genetic algorithm does not update. 

==7/32/2017==
The value passed into the genetic algorithm is either 0 or .1642

[[Category: Work Log]]

Abhijit Brahme (Work Log)

2017-07-31T15:00:45Z

AbhiB: /* 7/25/2017 */

Abhijit Brahme (Work Log)

2017-07-26T13:54:43Z

AbhiB: /* 7/25/2017 */

Abhijit Brahme (Work Log)

2017-07-26T13:51:13Z

AbhiB: /* 7/25/2017 */

File:Runtime2.png

2017-07-26T13:50:21Z

AbhiB: AbhiB uploaded a new version of File:Runtime2.png

Abhijit Brahme (Work Log)

2017-07-26T13:49:40Z

AbhiB: /* 7/25/2017 */

File:Runtime2.png

2017-07-26T13:48:33Z

AbhiB: AbhiB uploaded a new version of File:Runtime2.png

Abhijit Brahme (Work Log)

2017-07-26T13:47:55Z

AbhiB: /* 7/25/2017 */

File:Runtime2.png

2017-07-26T13:47:13Z

AbhiB:

Abhijit Brahme (Work Log)

2017-07-26T13:46:59Z

AbhiB: /* 7/24/2017 */

Abhijit Brahme (Work Log)

2017-07-25T14:37:01Z

AbhiB: /* 7/21/2017 */

File:Monteruntime.png

2017-07-24T15:14:43Z

AbhiB:

Abhijit Brahme (Work Log)

2017-07-24T15:14:23Z

AbhiB: /* 7/21/2017 */

Abhijit Brahme (Work Log)

2017-07-24T15:12:19Z

AbhiB: /* 7/21/2017 */

Abhijit Brahme (Work Log)

2017-07-21T13:12:57Z

AbhiB: /* 7/20/2017 */

Abhijit Brahme (Work Log)

2017-07-20T14:43:24Z

AbhiB: /* 7/19/2017 */

Abhijit Brahme (Work Log)

2017-07-19T14:55:45Z

AbhiB: /* 7/19/2017 */

Abhijit Brahme (Work Log)

2017-07-19T14:43:34Z

AbhiB: /* 7/18/2017 */

Abhijit Brahme (Work Log)

2017-07-19T14:14:05Z

AbhiB: /* 7/17/2017 */

Enclosing Circle Algorithm (Rework)

2017-07-18T20:59:37Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\Users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d 
an example: "C:\\Users\\Name\\Documents\\CityYearAreas.txt"
3. To plot just the circles do the following:
a. go to command prompt and type in cd /d E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
b. type in python plot_wrapper.py
c. follow the prompts

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Enclosing Circle Algorithm (Rework)

2017-07-18T20:46:14Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\Users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d 
an example: "C:\\Users\\Name\\Documents\\CityYearAreas.txt"
3. To plot just the circles do the following:
a. go to command prompt and type in cd /d E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)
b. type in python-plot_wrapper

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Abhijit Brahme (Work Log)

2017-07-17T16:20:49Z

AbhiB: /* 7/13/2017 */

Abhijit Brahme (Work Log)

2017-07-14T14:46:40Z

AbhiB: /* 7/12/2017 */

Abhijit Brahme (Work Log)

2017-07-13T16:12:19Z

AbhiB: /* 7/11/2017 */

Enclosing Circle Algorithm (Rework)

2017-07-12T20:39:56Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\Users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d 
an example: "C:\\Users\\Name\\Documents\\CityYearAreas.txt"

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Enclosing Circle Algorithm (Rework)

2017-07-12T20:33:46Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\Users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
"C:\\Users\\Name\\Documents\\CityYear.txt"
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Enclosing Circle Algorithm (Rework)

2017-07-12T20:32:39Z

AbhiB: /* Step By Step Use */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
1. The file "vc_circles.py" contains the main script, "master_circles", which takes in the following
a. "textfile", which is the filepath of the text data to read in. It must have fields "lattitude',"longitude","city","datefirstinv"
b. "n", which is the number of points to include in each circle
c. "iterations", the number of iterations to try and find a local optimum. Large numbers will slow the run time.
d. "basefn", the base file path of where to store the circles and points for each city,year pair 
an example: "C:\\users\\Name\\Documents" 
the function will add on the city,year to this base file name and save it to this file directory 
e. "outputfn", the full file path of where to output the area of the circles for a given city,year 
2. To plot the circles,points for a given year onto google maps, use the function "googleplotter.py"
a. This function takes in the filename used in 1d

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

File:Runtime.png

2017-07-12T20:10:29Z

AbhiB:

Enclosing Circle Algorithm (Rework)

2017-07-12T20:10:03Z

AbhiB: /* Explanation */

=K-Means Based Algorithm=
==Location==
The script and associated modules are located in:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

==Explanation==
The algorithm relies on an object oriented implementation of a "cluster". 
Each "cluster" has the following associated with it: 
1. area of minimum circle enclosing points in the cluster
2. points associated with the cluster
3. minimum circle associated with the cluster (x-coord,y-coord,radius)
4. "parent" cluster
5. "children" cluster(s)
'''Inputs:'''
1. n, the minimum number of points to include in a circle
2. k, the amount of clusters to split the points into
3. valid_nodes, an empty list to store the possible clusters to explore
4. explored_nodes, an empty list to store the explored clusters
5. cur_node, initialized to an object with all values set to none
6. end_nodes, initialized to an empty list used to store the clusters which cannot be split further
'''Algorithm:'''
1. Calculate the area of the minimum circle enclosing the total set of points
2. Split initial points into "k" clusters of at least "n" points using Constrained-K-Means Algorithm
3. construct minimum circles of "k" clusters and compute their total area
4. if this area <= area of the area of the first circle
5. Add all "k" clusters to "valid_nodes"
6. for node in valid_nodes, add node to explored_nodes, change cur_node to node, and update respective areas, parents, children, circle, points
7. run this algorithm again, change k = 2
8. if the cur_node cannot be split into 2, or the cur_node cannot be split into 2 circles with smaller areas than its parent, add cur_node to end_nodes and resume algorithm with next valid_node not in
explored_node as the cur_node
9. if all the valid_nodes are in explored_nodes, return end_nodes
10. repeat the above algorithm for all k from 2 to int(#number of total points/n) and take the end_nodes with the lowest total area
'''Runtime:'''
The runtime of the minimum enclosing circle is O(n), and the runtime of constrained k-means depends on k itself. Here, the value of k is proportional to the total number of points. 
We would expect the algorithm to slow as the number of points increase. For reference, a set of 80 points with n =3, took about 30 minutes, with number of iterations at 100. 
Further improvements could implement an early-stopping method to converge to a local optima. 

[[File:runtime.png]]

==Visualization ==
The K-Means based algorithm returns the optimal solution (left), and faster. 
[[File:houstonk.png]] [[File:houstonp.png]]
== Step By Step Use==
The input filepath should be a tab delimited text file with the entries as follows: year, startup locations 
The location information should be formatted as such: [(lat1,lon1),(lat2,lon2),.....)] 
The file is located:"E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)"
1. Open up the file "googleplotter.py"
2. where it says with open("C:\....") replace the filepath in the parentheses with your filepath enclosed in quotes.
3. Replace the city name in the "circles" function with the appropriate city name
4. Press ctrl+s to save the file
5. open up the command line
6. type: python googleplotter.py
7. your resulting text file and html google plots will be outputted to:
E:\McNair\Software\CodeBase\New Implement of Enclosing Circle (Constrained K Means, Smallest Circle)

== Benefits ==
Is faster than both Brute Force and Logical Enclosing Circle. 
Is more accurate than Logical Enclosing Circle. 
Can plot to google maps. 
Will return a tab delim text file of the following fields: city,year,total area 
Good for a large number of points 

==Drawbacks==
Is not the optimal solution as number of points increases, but an approximation

=Logical Enclosing Circle=
==Location==
The python script is located in :
E:\McNair\Projects\Accelerators\Enclosing_Circle\Enclosing_Circle\EnclosingCircleRemake2.py
==Explanation==
The rationale is to take the furthest point, draw a circle with its nearest n-1 points. 
Take the furthest point from the initial point, draw a circle with its nearest n-1 points. 
Repeat until all points are enclosed. 
==Benefits==
Can plot to google maps 
Is faster than brute force 
Returns city, circles, year to a tab delimited text file 

==Drawbacks==
Really slow for large number of points 
Offers an approximate solution that is worse than the Clustering based version 

=Brute Force=
==Location==
The Julia Script is located in:
E:\McNair\Software\CodeBase\Julia Code for enclosing circle
The Python Script is located in:
E:\McNair\Projects\Accelerators\Enclosing_Circle\enclosing_circle_brute_force.py

==Explanation==
1) Find all combinations of two points in the total data set.

2) For each of these combinations, draw a circle and figure out what other points are contained in a circle around those two points. If the circle contains at least n points, add it to a set of valid circles. There are Number of Points choose 2 possible circles.

3) Combine the valid circles in all possible ways and see if the resulting scheme contains all of the points. If it does, add it to a set of valid schemes. I believe that the number of ways to do this is the sum from i = 1 to i = number of valid circles Number of Circles choose i.

4) Iterate through the valid schemes and calculate the areas of the schemes.

5) Return the scheme with the minimum area.

==Benefits==
Always gives you the correct answer. 

==Drawbacks==
For a small number of points (i.e., <7), this is OKAY to use. 
However, it becomes extremely slow as the number of points increases. 
The Julia/Python code does not have the capability to plot to google maps, but will plot to a normal figure. 
(will work on adding this implementation, if the need arises)

Abhijit Brahme (Work Log)

2017-07-11T16:18:17Z

AbhiB: /* 6/30/2017 */

Abhijit Brahme (Work Log)

2017-06-30T20:56:59Z

AbhiB: /* 6/30/2017 */

Abhijit Brahme (Work Log)

2017-06-30T20:50:40Z

AbhiB: /* 6/20/2017 */

Abhijit Brahme (Work Log)

2017-06-30T20:50:22Z

AbhiB: /* 6/20/2017 */