#include <light_lof.hpp>

Inheritance diagram for jubatus::core::anomaly::light_lof:

Collaboration diagram for jubatus::core::anomaly::light_lof:

Classes
struct	config

struct	parameter

Public Member Functions
float	calc_anomaly_score (const common::sfv_t &query) const

float	calc_anomaly_score (const std::string &id) const

void	clear ()

void	clear_row (const std::string &id)

void	get_all_row_ids (std::vector< std::string > &ids) const

std::vector< framework::mixable * >	get_mixables () const

bool	is_updatable () const

	light_lof (const config &config, const std::string &id, jubatus::util::lang::shared_ptr< nearest_neighbor::nearest_neighbor_base > nearest_neighbor_engine)

	light_lof (const config &config, const std::string &id, jubatus::util::lang::shared_ptr< nearest_neighbor::nearest_neighbor_base > nearest_neighbor_engine, jubatus::util::lang::shared_ptr< unlearner::unlearner_base > unlearner)

void	pack (framework::packer &packer) const

void	set_row (const std::string &id, const common::sfv_t &sfv)

std::string	type () const

void	unpack (msgpack::object o)

void	update_row (const std::string &id, const sfv_diff_t &diff)

virtual	~light_lof ()

Public Member Functions inherited from jubatus::core::anomaly::anomaly_base
	anomaly_base ()

uint64_t	find_max_int_id () const

virtual	~anomaly_base ()

Public Member Functions inherited from jubatus::core::framework::model
virtual	~model ()

Private Member Functions
float	collect_lrds (const common::sfv_t &query, std::vector< float > &neighbor_lrds) const

float	collect_lrds (const std::string &query, std::vector< float > &neighbor_lrds) const

float	collect_lrds_from_neighbors (const std::vector< std::pair< std::string, float > > &neighbors, std::vector< float > &neighbor_lrd) const

void	collect_neighbors (const std::string &query, jubatus::util::data::unordered_set< std::string > &neighbors) const

parameter	get_row_parameter (const std::string &row) const

void	touch (const std::string &id)

void	unlearn (const std::string &id)

void	update_entries (const jubatus::util::data::unordered_set< std::string > &neighbors)

Private Attributes
config	config_

jubatus::util::lang::shared_ptr< framework::mixable_versioned_table >	mixable_nearest_neighbor_

jubatus::util::lang::shared_ptr< framework::mixable_versioned_table >	mixable_scores_

std::string	my_id_

jubatus::util::lang::shared_ptr< nearest_neighbor::nearest_neighbor_base >	nearest_neighbor_engine_

jubatus::util::lang::shared_ptr< unlearner::unlearner_base >	unlearner_

Detailed Description

Definition at line 45 of file light_lof.hpp.

Constructor & Destructor Documentation

jubatus::core::anomaly::light_lof::light_lof	(	const config &	config,
		const std::string &	id,
		jubatus::util::lang::shared_ptr< nearest_neighbor::nearest_neighbor_base >	nearest_neighbor_engine
	)

jubatus::core::anomaly::light_lof::light_lof	(	const config &	config,
		const std::string &	id,
		jubatus::util::lang::shared_ptr< nearest_neighbor::nearest_neighbor_base >	nearest_neighbor_engine,
		jubatus::util::lang::shared_ptr< unlearner::unlearner_base >	unlearner
	)

jubatus::core::anomaly::light_lof::~light_lof ( )

virtual

Definition at line 128 of file light_lof.cpp.

128 {

129 }

Member Function Documentation

float jubatus::core::anomaly::light_lof::calc_anomaly_score ( const common::sfv_t & query ) const

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 131 of file light_lof.cpp.

References collect_lrds().

                                                                   {
   std::vector<float> neighbor_lrds;
   const float lrd = collect_lrds(query, neighbor_lrds);
 
   return calculate_lof(lrd, neighbor_lrds);
 }

Here is the call graph for this function:

float jubatus::core::anomaly::light_lof::calc_anomaly_score ( const std::string & id ) const

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 138 of file light_lof.cpp.

References collect_lrds().

                                                              {
   std::vector<float> neighbor_lrds;
   const float lrd = collect_lrds(id, neighbor_lrds);
 
   return calculate_lof(lrd, neighbor_lrds);
 }

Here is the call graph for this function:

void jubatus::core::anomaly::light_lof::clear ( )

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 145 of file light_lof.cpp.

References mixable_scores_, nearest_neighbor_engine_, and unlearner_.

Referenced by unpack().

                       {
   nearest_neighbor_engine_->clear();
   mixable_scores_->get_model()->clear();
   if (unlearner_) {
     unlearner_->clear();
   }
 }

Here is the caller graph for this function:

void jubatus::core::anomaly::light_lof::clear_row ( const std::string & id )

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 153 of file light_lof.cpp.

References JUBATUS_EXCEPTION.

                                              {
   throw JUBATUS_EXCEPTION(common::unsupported_method(__func__));
 }

float jubatus::core::anomaly::light_lof::collect_lrds	(	const common::sfv_t &	query,
		std::vector< float > &	neighbor_lrds
	)		const

private

Definition at line 226 of file light_lof.cpp.

References collect_lrds_from_neighbors(), config_, nearest_neighbor_engine_, and jubatus::core::anomaly::light_lof::config::nearest_neighbor_num.

Referenced by calc_anomaly_score().

                                            {
   std::vector<std::pair<std::string, float> > neighbors;
   nearest_neighbor_engine_->neighbor_row(
       query, neighbors, config_.nearest_neighbor_num);
 
   return collect_lrds_from_neighbors(neighbors, neighbor_lrds);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

float jubatus::core::anomaly::light_lof::collect_lrds	(	const std::string &	query,
		std::vector< float > &	neighbor_lrds
	)		const

private

Definition at line 236 of file light_lof.cpp.

References collect_lrds_from_neighbors(), config_, nearest_neighbor_engine_, jubatus::core::anomaly::light_lof::config::nearest_neighbor_num, and jubatus::core::clustering::swap().

                                            {
   std::vector<std::pair<std::string, float> > neighbors;
   nearest_neighbor_engine_->neighbor_row(
       id, neighbors, config_.nearest_neighbor_num + 1);
 
   // neighbors may contain given id. We ignore it.
   for (size_t i = 0; i < neighbors.size(); ++i) {
     if (neighbors[i].first == id) {
       std::swap(neighbors[i], neighbors.back());
       neighbors.pop_back();
       break;
     }
   }
   if (neighbors.size() > static_cast<size_t>(config_.nearest_neighbor_num)) {
     neighbors.resize(config_.nearest_neighbor_num);
   }
 
   return collect_lrds_from_neighbors(neighbors, neighbor_lrds);
 }

Here is the call graph for this function:

float jubatus::core::anomaly::light_lof::collect_lrds_from_neighbors	(	const std::vector< std::pair< std::string, float > > &	neighbors,
		std::vector< float > &	neighbor_lrd
	)		const

private

Definition at line 258 of file light_lof.cpp.

References get_row_parameter().

Referenced by collect_lrds().

                                            {
   neighbor_lrds.resize(neighbors.size());
   if (neighbors.empty()) {
     return std::numeric_limits<float>::infinity();
   }
 
   // Collect parameters of given neighbors.
   std::vector<parameter> parameters(neighbors.size());
   for (size_t i = 0; i < neighbors.size(); ++i) {
     parameters[i] = get_row_parameter(neighbors[i].first);
     neighbor_lrds[i] = parameters[i].lrd;
   }
 
   // Calculate LRD value of the query.
   float sum_reachability = 0;
   for (size_t i = 0; i < neighbors.size(); ++i) {
     // Accumulate the reachability distance of the query and the i-th neighbor.
     sum_reachability += std::max(neighbors[i].second, parameters[i].kdist);
   }
 
   if (sum_reachability == 0) {
     // All k-nearest neighbors are at the same point with given query.
     return std::numeric_limits<float>::infinity();
   }
 
   // LRD is an inverse of mean of reachability distances between the query and
   // its k-nearest neighbors.
   return neighbors.size() / sum_reachability;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::anomaly::light_lof::collect_neighbors	(	const std::string &	query,
		jubatus::util::data::unordered_set< std::string > &	neighbors
	)		const

private

Definition at line 290 of file light_lof.cpp.

References config_, nearest_neighbor_engine_, and jubatus::core::anomaly::light_lof::config::reverse_nearest_neighbor_num.

Referenced by set_row(), and unlearn().

                                                {
   std::vector<std::pair<std::string, float> > nn_result;
   nearest_neighbor_engine_->neighbor_row(
       query, nn_result, config_.reverse_nearest_neighbor_num);
 
   for (size_t i = 0; i < nn_result.size(); ++i) {
     neighbors.insert(nn_result[i].first);
   }
 }

Here is the caller graph for this function:

void jubatus::core::anomaly::light_lof::get_all_row_ids ( std::vector< std::string > & ids ) const

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 180 of file light_lof.cpp.

References nearest_neighbor_engine_.

                                                                {
   nearest_neighbor_engine_->get_all_row_ids(ids);
 }

std::vector< framework::mixable * > jubatus::core::anomaly::light_lof::get_mixables ( ) const

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 188 of file light_lof.cpp.

References mixable_scores_, and nearest_neighbor_engine_.

                                                            {
   std::vector<framework::mixable*> mixables;
   mixables.push_back(nearest_neighbor_engine_->get_mixable());
   mixables.push_back(mixable_scores_.get());
   return mixables;
 }

light_lof::parameter jubatus::core::anomaly::light_lof::get_row_parameter ( const std::string & row ) const

private

Definition at line 368 of file light_lof.cpp.

References JUBATUS_EXCEPTION, jubatus::core::anomaly::light_lof::parameter::kdist, jubatus::core::anomaly::light_lof::parameter::lrd, and mixable_scores_.

Referenced by collect_lrds_from_neighbors().

           {
   shared_ptr<column_table> table = mixable_scores_->get_model();
   std::pair<bool, uint64_t> hit = table->exact_match(row);
   if (!hit.first) {
     throw JUBATUS_EXCEPTION(common::exception::runtime_error(
         "row \"" + row + "\" not found in light_lof table"));
   }
   parameter param;
   param.kdist = table->get_float_column(KDIST_COLUMN_INDEX)[hit.second];
   param.lrd = table->get_float_column(LRD_COLUMN_INDEX)[hit.second];
   return param;
 }

Here is the caller graph for this function:

bool jubatus::core::anomaly::light_lof::is_updatable ( ) const

inlinevirtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 95 of file light_lof.hpp.

                             {
     return false;
   }

void jubatus::core::anomaly::light_lof::pack ( framework::packer & packer ) const

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 382 of file light_lof.cpp.

References mixable_scores_, and nearest_neighbor_engine_.

                                                   {
   packer.pack_array(2);
   nearest_neighbor_engine_->pack(packer);
   mixable_scores_->get_model()->pack(packer);
 }

void jubatus::core::anomaly::light_lof::set_row	(	const std::string &	id,
		const common::sfv_t &	sfv
	)

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 161 of file light_lof.cpp.

References collect_neighbors(), mixable_scores_, my_id_, nearest_neighbor_engine_, touch(), and update_entries().

                                                                    {
   unordered_set<std::string> update_set;
 
   shared_ptr<column_table> table = mixable_scores_->get_model();
   if (table->exact_match(id).first) {
     collect_neighbors(id, update_set);
   }
 
   touch(id);
   nearest_neighbor_engine_->set_row(id, sfv);
   collect_neighbors(id, update_set);
 
   // Primarily add id to lof table with dummy parameters.
   // update_entries() below overwrites this row.
   table->add(id, storage::owner(my_id_), -1.f, -1.f);
   update_set.insert(id);
   update_entries(update_set);
 }

Here is the call graph for this function:

void jubatus::core::anomaly::light_lof::touch ( const std::string & id )

private

Definition at line 197 of file light_lof.cpp.

References JUBATUS_EXCEPTION, and unlearner_.

Referenced by set_row().

                                          {
   if (unlearner_) {
     if (!unlearner_->touch(id)) {
       throw JUBATUS_EXCEPTION(common::exception::runtime_error(
           "no more space available to add new ID: " + id));
     }
   }
 }

Here is the caller graph for this function:

std::string jubatus::core::anomaly::light_lof::type ( ) const

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 184 of file light_lof.cpp.

                                 {
   return "light_lof";
 }

void jubatus::core::anomaly::light_lof::unlearn ( const std::string & id )

private

Definition at line 215 of file light_lof.cpp.

References collect_neighbors(), mixable_nearest_neighbor_, mixable_scores_, and update_entries().

                                             {
   unordered_set<std::string> reverse_knn;
   collect_neighbors(key, reverse_knn);
   reverse_knn.erase(key);
 
   mixable_nearest_neighbor_->get_model()->delete_row(key);
   mixable_scores_->get_model()->delete_row(key);
 
   update_entries(reverse_knn);
 }

Here is the call graph for this function:

void jubatus::core::anomaly::light_lof::unpack ( msgpack::object o )

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 388 of file light_lof.cpp.

References clear(), mixable_scores_, and nearest_neighbor_engine_.

                                       {
   if (o.type != msgpack::type::ARRAY || o.via.array.size != 2) {
     throw msgpack::type_error();
   }
 
   // clear before load
   clear();
 
   nearest_neighbor_engine_->unpack(o.via.array.ptr[0]);
   mixable_scores_->get_model()->unpack(o.via.array.ptr[1]);
 }

Here is the call graph for this function:

void jubatus::core::anomaly::light_lof::update_entries ( const jubatus::util::data::unordered_set< std::string > & neighbors )

private

Definition at line 302 of file light_lof.cpp.

References config_, mixable_scores_, my_id_, nearest_neighbor_engine_, jubatus::core::anomaly::light_lof::config::nearest_neighbor_num, and jubatus::core::storage::typed_column< T >::push_back().

Referenced by set_row(), and unlearn().

                                                                         {
   shared_ptr<column_table> table = mixable_scores_->get_model();
   storage::float_column& kdist_column =
       table->get_float_column(KDIST_COLUMN_INDEX);
   storage::float_column& lrd_column = table->get_float_column(LRD_COLUMN_INDEX);
 
   std::vector<uint64_t> ids;
   ids.reserve(neighbors.size());
   for (unordered_set<std::string>::const_iterator it = neighbors.begin();
        it != neighbors.end(); ++it) {
     const std::pair<bool, uint64_t> hit = table->exact_match(*it);
     if (hit.first) {
       ids.push_back(hit.second);
     }
   }
 
   unordered_map<uint64_t, std::vector<std::pair<uint64_t, float> > >
       nested_neighbors;
 
   // Gather k-nearest neighbors of each member of neighbors and update their
   // k-dists.
   std::vector<std::pair<std::string, float> > nn_result;
   for (std::vector<uint64_t>::const_iterator it = ids.begin();
        it != ids.end(); ++it) {
     nearest_neighbor_engine_->neighbor_row(
         table->get_key(*it), nn_result, config_.nearest_neighbor_num);
     std::vector<std::pair<uint64_t, float> >& nn_indexes =
         nested_neighbors[*it];
 
     nn_indexes.reserve(nn_result.size());
     for (size_t i = 0; i < nn_result.size(); ++i) {
       const std::pair<bool, uint64_t> hit =
           table->exact_match(nn_result[i].first);
       if (hit.first) {
         nn_indexes.push_back(std::make_pair(hit.second, nn_result[i].second));
       }
     }
 
     kdist_column[*it] = nn_result.back().second;
   }
 
   // Calculate LRDs of neighbors.
   const storage::owner owner(my_id_);
   for (std::vector<uint64_t>::const_iterator it = ids.begin();
        it != ids.end(); ++it) {
     const std::vector<std::pair<uint64_t, float> >& nn = nested_neighbors[*it];
     float lrd = 1;
     if (!nn.empty()) {
       const size_t length = std::min(
           nn.size(), static_cast<size_t>(config_.nearest_neighbor_num));
       float sum_reachability = 0;
       for (size_t i = 0; i < length; ++i) {
         sum_reachability += std::max(nn[i].second, kdist_column[nn[i].first]);
       }
 
       if (sum_reachability == 0) {
         lrd = std::numeric_limits<float>::infinity();
       } else {
         lrd = length / sum_reachability;
       }
     }
     lrd_column[*it] = lrd;
     table->update_clock(*it, owner);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::anomaly::light_lof::update_row	(	const std::string &	id,
		const sfv_diff_t &	diff
	)

virtual

Implements jubatus::core::anomaly::anomaly_base.

Definition at line 157 of file light_lof.cpp.

References JUBATUS_EXCEPTION.

                                                                       {
   throw JUBATUS_EXCEPTION(common::unsupported_method(__func__));
 }

Member Data Documentation

config jubatus::core::anomaly::light_lof::config_

private

Definition at line 140 of file light_lof.hpp.

Referenced by collect_lrds(), collect_neighbors(), and update_entries().

jubatus::util::lang::shared_ptr<framework::mixable_versioned_table> jubatus::core::anomaly::light_lof::mixable_nearest_neighbor_

private

Definition at line 135 of file light_lof.hpp.

Referenced by unlearn().

jubatus::util::lang::shared_ptr<framework::mixable_versioned_table> jubatus::core::anomaly::light_lof::mixable_scores_

private

Definition at line 138 of file light_lof.hpp.

Referenced by clear(), get_mixables(), get_row_parameter(), pack(), set_row(), unlearn(), unpack(), and update_entries().

std::string jubatus::core::anomaly::light_lof::my_id_

private

Definition at line 141 of file light_lof.hpp.

Referenced by set_row(), and update_entries().

jubatus::util::lang::shared_ptr<nearest_neighbor::nearest_neighbor_base> jubatus::core::anomaly::light_lof::nearest_neighbor_engine_

private

Definition at line 130 of file light_lof.hpp.

Referenced by clear(), collect_lrds(), collect_neighbors(), get_all_row_ids(), get_mixables(), pack(), set_row(), unpack(), and update_entries().

jubatus::util::lang::shared_ptr<unlearner::unlearner_base> jubatus::core::anomaly::light_lof::unlearner_

private

Definition at line 131 of file light_lof.hpp.

Referenced by clear(), and touch().

The documentation for this class was generated from the following files:

jubatus/core/anomaly/light_lof.hpp
jubatus/core/anomaly/light_lof.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation