Re: [boost] [Accumulators] k-nearest neighbor

From: Eric Niebler (eric_at_[hidden])
Date: 2007-01-11 11:44:19

Niitsuma Hirotaka wrote:
> I made k-nearest neighbor program based on Boost.Accumulators
> plz see attached file.

Nice!

> 
> usage
> 
> 
>     ublas::vector<double> v1(3),v2(3),v3(3), v0(3);
> 
>         v1(0)=3; v1(1)=1; v1(2)=2;
>         v2(0)=1; v2(1)=20; v2(2)=0;
>         v3(0)=1; v3(1)=1; v3(2)=3;
>         v0=ublas::zero_vector<double>(3);
> 
> 
> 
>     struct norm_2_diff_functor
>     {
>         double
>         operator ()(const boost::numeric::ublas::vector<double> &e1 , const
> boost::numeric::ublas::vector<double> &e2)
>         {
>             return(boost::numeric::ublas::norm_2(e1-e2) );
>         }
>     };
> 
> 
>     accumulators::accumulator_set<
>         ublas::vector<double>
>         , accumulators::stats<
>             accumulators::tag::k_nearest_neighbor           
>         >
>    > acc(
>         accumulators::k_nearest_neighbor_distance = norm_2_diff_functor()
>         ,accumulators::sample =v0
>     );
>         acc(v1);
>         acc(v2);
>         acc(v3);
> 
> 
>         typedef ublas::vector<double> float_type;
>         typedef double distance_type;
>         typedef std::vector<float_type> array_type;       
>         typedef boost::iterator_range<typename array_type::iterator>
> array_range_type;
>         typedef std::pair<distance_type, typename array_type::iterator> 
> dist_it_type;
>         typedef std::vector< dist_it_type > dist_it_array_type;
>         typedef boost::iterator_range<typename 
> dist_it_array_type::iterator>
> dist_it_array_range_type;
>         typedef std::pair< dist_it_array_range_type , array_range_type > 
> result_type;
> 
>         result_type result;

Whoa, that's a lot of unnecessary work to get the result_type of an 
accumulator. Given the type of an accumulator_set and the feature tag 
type, you can get the result_type as follows:

     mpl::apply< AccumulatorSetType, FeatureTag >::type::result_type

In you case, the FeatureTag is accumulators::tag::k_nearest_neighbor. 
The result of apply<>::type is the type of the accumulator that 
implements the requested feature, and all accumulators have a nested 
result_type typedef.

> 
> 
>     result =accumulators::k_nearest_neighbor(
>         acc
>          ,accumulators::k_nearest_neighbor_k=1
>          ,accumulators::k_nearest_neighbor_target=v0
>         );
> 
>     std::cout << result.first[0].first << " " <<  *result.first[0].second
> << std::endl;
> 
> 
> 
>     result =accumulators::k_nearest_neighbor(
>         acc
>          ,accumulators::k_nearest_neighbor_k=3
>          ,accumulators::k_nearest_neighbor_target=v0
>         );
> 
>     std::cout << result.first[0].first << " " <<  result.first[1].first
> << " " <<  result.first[2].first;
> 

Looks cool, thanks!

Incidentally, did you ever see my feedback about your patch to add 
support for ublas::vector<>? I thought there were some issues -- would 
be great if you could comment.

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com