<div><div dir="auto">Thanks Dr. Varoquax, it’s awesome you’re on this list, I’m a fan of your work!</div><div dir="auto"><br></div><div dir="auto">Will look into this strategy.</div><div dir="auto"><br></div><div dir="auto">Best,</div><div dir="auto"><br></div><div dir="auto">Randy </div><br><div class="gmail_quote"><div>On Tue, Apr 3, 2018 at 8:57 AM Gael Varoquaux <<a href="mailto:gael.varoquaux@normalesup.org">gael.varoquaux@normalesup.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Matching to minimize a cost is known as the linear assignment problem,<br>
can be solved in n^3 cost, and is implemented in scikit-learn in<br>
sklearn.utils.linear_assignment_.linear_assignment or in recent versions<br>
of scipy as scipy.optimize.linear_sum_assignment<br>
<br>
Of course, this problem will require much more coding (you need to build<br>
your pairwise cost matrix) and much more computing cost (n^3 instead of<br>
n^2) than a standard nearest-neighbor.<br>
<br>
Gaël<br>
<br>
On Mon, Apr 02, 2018 at 01:47:51PM -0400, Randy Ellis wrote:<br>
> Hi Jake,<br>
<br>
> Thanks for the reply. Yes, trying this out resulted from looking for ways in<br>
> python to implement propensity score matching. I found a package, pscore_match<br>
> (<a href="http://www.kellieottoboni.com/pscore_match/" rel="noreferrer" target="_blank">http://www.kellieottoboni.com/pscore_match/</a>), but the matching was really<br>
> terrible. Specifically, I'm matching based on age, race, gender, HIV status,<br>
> hepatitis C status, and sickle-cell disease status. Using NearestNeighbors for<br>
> matching performed WAY better, I was so surprised at how well every factor was<br>
> matched for. The only issue is that it uses replacement. <br>
<br>
> Here's what I'm currently testing. I need each case to match to 20 controls, so<br>
> since NearestNeighbors uses replacement, I'm matching each case to many<br>
> controls (15000), taking all of the distances for all of the pairs, and<br>
> retaining only the smallest distances for each control. Since many controls are<br>
> re-used (since the algorithm uses replacement), the hope is that enough<br>
> controls are matched to many different cases so that each case ends up being<br>
> matched to 20 unique controls. Does this method make sense??<br>
<br>
> Best,<br>
<br>
> Randy  <br>
<br>
> On Sun, Apr 1, 2018 at 10:13 PM, Jacob Vanderplas <<a href="mailto:jakevdp@cs.washington.edu" target="_blank">jakevdp@cs.washington.edu</a>><br>
> wrote:<br>
<br>
>     On Sun, Apr 1, 2018 at 6:36 PM, Randy Ellis <<a href="mailto:randalljellis@gmail.com" target="_blank">randalljellis@gmail.com</a>><br>
>     wrote:<br>
<br>
>         Hello to the Scikit-learn community!<br>
<br>
>         I am doing case-control matching for an electronic health records<br>
>         study. My question is, is it possible to run Sklearn's NearestNeighbors<br>
>         function without replacement? As in, match the treated group to the<br>
>         untreated group without re-using any of the untreated group data<br>
>         points? If so, how? By default, it uses replacement. I know this<br>
>         because I tested it on some data of mine.<br>
<br>
>         The code I used is in the confirmed answer here: https://<br>
>         <a href="http://stats.stackexchange.com/questions/206832/matched-pai" rel="noreferrer" target="_blank">stats.stackexchange.com/questions/206832/matched-pai</a><br>
>         rs-in-python-propensity-score-matching<br>
<br>
>         Thanks so much in advance,<br>
<br>
<br>
>     No, pairwise matching without replacement is not implemented within<br>
>     scikit-learn's nearest neighbors routines.<br>
<br>
>     It seems like an algorithm you would have to think carefully about because<br>
>     the number of potential pairs grows exponentially with the number of<br>
>     points, and I don't think it's true that choosing the nearest available<br>
>     neighbor of points in sequence will guarantee you to find the optimal<br>
>     configuration. You'd also have to carefully define what you mean by<br>
>     "optimal"... are you seeking to minimize the sum of all distances? The sum<br>
>     of squared distances? The maximum distance? The results would change<br>
>     depending on the metric you define. And you'd probably have to figure out<br>
>     some way to reduce the exponential search space in order to calculate the<br>
>     result in a reasonable amount of time for your data.<br>
<br>
>     You might look into the literature on propensity score matching; I think<br>
>     that's one area where this kind of neighbors-without-replacement algorithm<br>
>     is often used.<br>
<br>
>     Best,<br>
>        Jake<br>
>      <br>
--<br>
    Gael Varoquaux<br>
    Senior Researcher, INRIA Parietal<br>
    NeuroSpin/CEA Saclay , Bat 145, 91191 Gif-sur-Yvette France<br>
    Phone:  ++ 33-1-69-08-79-68<br>
    <a href="http://gael-varoquaux.info" rel="noreferrer" target="_blank">http://gael-varoquaux.info</a>            <a href="http://twitter.com/GaelVaroquaux" rel="noreferrer" target="_blank">http://twitter.com/GaelVaroquaux</a><br>
_______________________________________________<br>
scikit-learn mailing list<br>
<a href="mailto:scikit-learn@python.org" target="_blank">scikit-learn@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/scikit-learn" rel="noreferrer" target="_blank">https://mail.python.org/mailman/listinfo/scikit-learn</a><br>
</blockquote></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div style="color:rgb(0,0,0);font-family:Tahoma;font-size:13px"><div style="font-family:arial,sans-serif"><font face="arial, helvetica, sans-serif"><span style="font-size:13.3333px"><b>Randall J. Ellis, B.S.</b></span></font></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><font style="color:rgb(0,0,0);font-size:13px">PhD Student, Biomedical Science, Mount Sinai<br style="font-size:13.3333px"></font><span style="color:rgb(0,0,0);font-size:13.3333px">Special Volunteer, </span><font color="#000000"><span style="font-size:13.3333px"><a href="http://www.michaelideslab.org/" target="_blank">http://www.michaelideslab.org/</a>, NIDA IRP</span></font></font></div><div style="font-family:arial,sans-serif"><span style="font-size:13.3333px"><font face="arial, helvetica, sans-serif">Cell: (954)-260-9891</font></span></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>