Collects evaluated subsets to eventually provide Dependency-Aware Feature Ranking coefficients. More...

#include <result_tracker_feature_stats.hpp>

Inheritance diagram for FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >:

Classes
struct	FeatureStat
	Structure to gather feature occurrence statistics over probe subset evaluations. More...
struct	SubSizeStat
	Structure to gather probe subset cardinality statistics. More...
struct	PairStat
	Structure to hold pairwise feature statistics (2x2 presence-cell contrasts over probe subset evaluations). More...

Public Types
typedef Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >	parent
	the base tracker: dupless probe storage sorted descending by criterion value; this class adds DAF post-processing over it
typedef Clonable_Impl< Result_Tracker_Feature_Stats, parent, CLONE_INHERIT, CLONE_INHERIT, CLONE_DEEP >	parent_impl
	implements stateless_clone(); clone()/sharing_clone() throw in Result_Tracker
typedef parent::ResultRec	ResultRec
	[subset,criterion value] result record, see Result_Tracker::ResultRec
typedef ResultRec *	PResultRec
	raw pointer to a ResultRec, as used by the inherited get_first()/get_next() iteration
typedef std::shared_ptr< SUBSET >	PSubset
Public Types inherited from FST::Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >
typedef Result_Tracker< RETURNTYPE, SUBSET >	parent
	the abstract Result_Tracker interface this class implements
typedef Clonable_Impl< Result_Tracker_Dupless, parent, CLONE_INHERIT, CLONE_INHERIT, CLONE_DEEP >	parent_impl
	implements stateless_clone() via the copy-constructor (CLONE_DEEP); clone()/sharing_clone() are inherited from Result_Tracker, which throws for both
typedef parent::ResultRec	ResultRec
	see Result_Tracker::ResultRec
typedef parent::PResultRec	PResultRec
	see Result_Tracker::PResultRec
typedef std::shared_ptr< SUBSET >	PSubset
typedef std::list< ResultRec >::const_iterator	CONSTRESULTSITER
	read-only iterator over results, for use by subclasses/friends inspecting the collected results
typedef std::list< ResultRec >::iterator	RESULTSITER
	mutable iterator over results, as returned by begin()/end()
Public Types inherited from FST::Result_Tracker< RETURNTYPE, SUBSET >
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a tracked feature subset
typedef ResultRec *	PResultRec
	raw pointer to a ResultRec, as used by get_first()/get_next() iteration

Public Member Functions
	Result_Tracker_Feature_Stats (const IDXTYPE capacity_limit=0)
	Result_Tracker_Feature_Stats (const Result_Tracker_Feature_Stats &rtfs)
	the stateless_clone() copy: replicates configuration (capacity limit, margin) via the parent copy-constructor but starts with an empty probe list and no computed statistics – compute_stats()/compute_pair_stats() must be rerun on the clone
bool	compute_stats (std::ostream &os=std::cout)
	Aggregates DAF ranking statistics (DAF0/DAF1/DAF2) from all probe subsets recorded so far.
bool	print_stats (std::ostream &os=std::cout)
bool	getFirstDAF (RETURNTYPE &value, DIMTYPE &feature, const unsigned int DAFidx=0) const
	Starts an iteration (descending by value) over the feature ordering built by compute_stats() for the given DAF variant.
bool	getNextDAF (RETURNTYPE &value, DIMTYPE &feature, const unsigned int DAFidx=0) const
bool	compute_pair_stats (const DIMTYPE top_k, std::ostream &os=std::cout)
	Computes pairwise (group) DAF statistics: 2x2 presence-cell contrasts over all pairs of the top `top_k` DAF0-ranked features.
bool	print_pair_stats (std::ostream &os=std::cout, const std::size_t top_pairs=0)
bool	getFirstPairDAF (RETURNTYPE &daf0, RETURNTYPE &daf1, bool &daf1_valid, RETURNTYPE &synergy, DIMTYPE &f1, DIMTYPE &f2) const
	Starts an iteration (decreasing pair-DAF0) over the pairwise statistics built by compute_pair_stats().
bool	getNextPairDAF (RETURNTYPE &daf0, RETURNTYPE &daf1, bool &daf1_valid, RETURNTYPE &synergy, DIMTYPE &f1, DIMTYPE &f2) const
virtual std::ostream &	print (std::ostream &os) const override
	writes a human-readable identification of the object; base default writes nothing
Public Member Functions inherited from FST::Clonable_Impl< Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >, Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >, CLONE_INHERIT, CLONE_INHERIT, CLONE_DEEP >
Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET > *	clone () const override
	dispatches to the DEEP_KIND mechanism (default CLONE_DEEP: Derived's copy-constructor)
Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET > *	sharing_clone () const override
	dispatches to the SHARING_KIND mechanism (default CLONE_INHERIT: defers to Base, which throws by family convention)
Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET > *	stateless_clone () const override
	dispatches to the STATELESS_KIND mechanism (default CLONE_INHERIT: defers to Base, which throws by family convention)
Public Member Functions inherited from FST::Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >
	Result_Tracker_Dupless (const IDXTYPE capacity_limit=0)
	Result_Tracker_Dupless (const Result_Tracker_Dupless &rtd)
	copies the configuration (margin, cardinality restriction, capacity limit) only; the `results` list is NOT copied (starts empty) – this constructor backs stateless_clone() (CLONE_DEEP), which by contract does not replicate exact object state
virtual bool	add (const RETURNTYPE value, const PSubset sub) override
	Offers one (value, subset) result for inclusion; `sub` is copied, the caller keeps ownership of its own object.
virtual void	clear () override
	discards all recorded results
virtual std::size_t	size () const override
	number of results currently held (std::size_t rather than 'long': on LLP64 platforms 'long' is 32 bits and would narrow the container's own size type)
virtual std::size_t	size (const RETURNTYPE margin) const
	number of currently held results whose value is within `margin` of the best (first, highest-value) held result
virtual bool	get_first (PResultRec &r) override
	starts iteration at the best held result; false if nothing is held. The returned pointer refers into this tracker's own storage and is invalidated by add(), join() and clear()
virtual bool	get_next (PResultRec &r) override
	hands out the next result in descending-value order; false when the iteration is exhausted. There is one shared cursor per tracker, so nested or concurrent iterations of the same tracker interfere
virtual void	join (Result_Tracker< RETURNTYPE, SUBSET > &src) override
	merges the results held by `src` into this tracker, keeping the ordering and skipping duplicates exactly as add() does, then re-applies the capacity limit and the margin to the merged list. Consumes `src's` iteration cursor; `src` itself is left unchanged
void	set_inclusion_margin (const RETURNTYPE margin=0)
	restrict adding to only subsets with criterion value within given distance (margin) from best known
void	set_inclusion_cardinality_restriction (const DIMTYPE d)
	for d>0 restricts adding only to subsets of size d, for d=0 subset size restriction is removed
RESULTSITER	begin ()
	iterator to the best (first) held result
RESULTSITER	end ()
	iterator past the last held result
Public Member Functions inherited from FST::Result_Tracker< RETURNTYPE, SUBSET >
	Result_Tracker (const Result_Tracker &rt)
	copies the output-detail setting only – concrete trackers copy their own collected results separately
Result_Tracker *	clone () const override
Result_Tracker *	sharing_clone () const override
void	set_output_detail (OutputDetail detail)
	sets the amount of information that is logged to output stream throughout the course of search
OutputDetail	get_output_detail () const
	the currently configured output detail level
bool	output_normal () const
	true unless output detail is SILENT
bool	output_detailed () const
	true only at the DETAILED output level
Public Member Functions inherited from FST::Clonable
bool	is_clone () const
bool	is_sharing () const
	true if this instance is a sharing_clone() result (referencing, not owning, the source's structures)
bool	is_sharing_clone () const
	true if this instance is BOTH a clone and sharing – i.e. specifically a sharing_clone() result, not a clone()/stateless_clone() one

Protected Types
typedef std::vector< DIMTYPE >	ORDERTYPE
	feature-index ordering vector, as built per DAF variant by compute_stats()

Static Protected Member Functions
static std::size_t	pair_index (const std::size_t a, const std::size_t b, const std::size_t k)
	Upper-triangle linearization of pair (a,b), a<b<k, into a flat index over PairStat storage (k = the top-k feature-set size).

Protected Attributes
DIMTYPE	_n
std::vector< FeatureStat >	_stats
	one entry per feature (index 0.._n-1), aggregated over all recorded probes; filled by compute_stats()
std::vector< SubSizeStat >	_dstat
	one entry per subset size 1.._n (index 0 unused); filled by compute_stats()
ORDERTYPE	_order [3]
	per DAF variant (0=DAF0, 1=DAF1, 2=DAF2): feature indices with a valid DAF value, sorted descending by that value; built by compute_stats()
DIMTYPE	_itersize [3]
	per DAF variant: getFirstDAF()/getNextDAF() cursor position (index into _order[DAFidx]); 0 = iteration not started
std::mutex	_itersize_mutex
	serializes access to the iteration cursors _itersize AND _pair_itersize across concurrent getFirst/getNext calls (threaded builds only)
std::vector< PairStat >	_pair_stats
	upper-triangle linearization (via pair_index()) over the top-k feature set; filled by compute_pair_stats()
std::vector< DIMTYPE >	_pair_features
	the top-k DAF0-ranked (global) feature indices the pairs are drawn from
std::vector< std::size_t >	_pair_order
	indices into _pair_stats, valid pairs only, sorted decreasing pair-DAF0
std::size_t	_pair_itersize
Protected Attributes inherited from FST::Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >
std::list< ResultRec >	results
	held results, sorted descending by value (ties broken toward the smaller subset); see add() for the exact insertion/dedup/trim rule
RETURNTYPE	_margin
	set via set_inclusion_margin(); 0 = no margin restriction
DIMTYPE	_restrict_to_d
	set via set_inclusion_cardinality_restriction(); 0 = no subset-size restriction
const IDXTYPE	_capacity_limit
	set by the constructor; 0 = unlimited
Protected Attributes inherited from FST::Result_Tracker< RETURNTYPE, SUBSET >
OutputDetail	_detail
	the output detail level set via set_output_detail(); read by output_normal()/output_detailed()

Additional Inherited Members
Protected Member Functions inherited from FST::Clonable
void	set_cloned (const bool cloned=true)
	marks/unmarks this instance as a clone; call from clone()/stateless_clone() overrides (Clonable_Impl does this automatically)
void	set_sharing (const bool sharing=true)
	marks/unmarks this instance as sharing (see is_sharing())
void	set_sharing_cloned (const bool cloned=true, const bool sharing=true)
	sets both flags at once; call from sharing_clone() overrides (Clonable_Impl does this automatically)

Detailed Description

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>
class FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >

Collects evaluated subsets to eventually provide Dependency-Aware Feature Ranking coefficients.

Dependency-Aware Feature ranking (DAF) is a new type of ranking method especially suitable for very-high-dimensional feature selection. Unlike standard individual feature ranking, the DAF ranking reflects "average feature quality in context" and as such is capable of providing significantly better results than BIF (provided the data actually do contain mutually dependent features). The method has been described in combination with Monte Carlo based feature selection permitting Wrapper Criteria even in very-high-dimensional setting. The tracker is not a search of its own: attach it to any search that generates many probe subsets (Monte Carlo search is the usual choice), let the search run, then call compute_stats() and read the ranking off getFirstDAF()/getNextDAF(). For ready-to-run examples see the demo34 and demo35t protocols (demos/demo34.cfg, demos/demo35t.cfg). For more detailed information see UTIA Technical Report No. 2295.

Member Typedef Documentation

◆ PSubset

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

typedef std::shared_ptr<SUBSET> FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::PSubset

shared pointer to a tracked feature subset

Constructor & Destructor Documentation

◆ Result_Tracker_Feature_Stats()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::Result_Tracker_Feature_Stats ( const IDXTYPE capacity_limit = 0 )

inline

Parameters

capacity_limit forwarded to Result_Tracker_Dupless; 0 (the fst4 CLI default for this tracker) means unlimited probe storage

Member Function Documentation

◆ compute_pair_stats()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::compute_pair_stats	(	const DIMTYPE	top_k,
		std::ostream &	os = std::cout )

Computes pairwise (group) DAF statistics: 2x2 presence-cell contrasts over all pairs of the top top_k DAF0-ranked features.

A post-processing pass purely over the probes already recorded by compute_stats() (search logic and the per-feature DAF0/DAF1/DAF2 statistics above are unaffected). It exposes the statistics only - no ranking heuristic is baked in. For each pair (f1,f2) drawn from the top-k DAF0-ranked feature set, splits the recorded probes into the four 2x2 presence cells (both selected, both absent, f1-only, f2-only); only the both-present cell is accumulated directly per probe, the other three are derived from it plus the per-feature and grand totals by inclusion-exclusion. Reported per pair: pair-DAF0 = mean(both present) - mean(both absent); pair-DAF1 = pair-DAF0 normalized by the frequency-weighted stdevs of those two cells (the DAF1 analogue); synergy = mean_both + mean_neither - mean_f1only - mean_f2only (the 2x2 interaction contrast). A pair is valid only if all four presence cells are non-empty; among valid pairs, pair-DAF1 is additionally marked invalid if its normalization denominator is zero. Builds the getFirstPairDAF()/getNextPairDAF() ordering (valid pairs only, decreasing pair-DAF0).

Parameters

top_k	requires a prior compute_stats() call: the top `top_k` DAF0-ranked features define the pair set; must be >=2
os	progress/warning messages are written here at NORMAL output detail or above

Returns: false if compute_stats() has not been run, if fewer than 2 features have a valid DAF0, if top_k<2, or if no pair turns out valid

◆ compute_stats()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::compute_stats ( std::ostream & os = std::cout )

Aggregates DAF ranking statistics (DAF0/DAF1/DAF2) from all probe subsets recorded so far.

For each feature, splits the recorded (subset,value) probes into those where the feature is selected ("is") and not selected ("isnot"), and computes per-partition mean/stdev of the criterion value plus DAF0 = mean_is-mean_isnot and DAF1 = DAF0 normalized by the frequency-weighted partition stdevs; DAF2 is a further variant, normalized per probe by the stdev of same-cardinality probes (the "DAF3" measure of UTIA Technical Report No. 2295) – unlike DAF0/DAF1, DAF2 is marked valid for every feature unconditionally, even when insufficient same-cardinality probes force its value to 0. Also aggregates per-cardinality (per subset size) mean/stdev of the criterion value. Builds the getFirstDAF()/getNextDAF() ordering for all three variants (descending by DAF value, features without a valid value excluded). Must be called (and re-called after adding more probes) before print_stats(), getFirstDAF()/getNextDAF() or compute_pair_stats() return meaningful results.

Parameters

os	progress/warning messages are written here at NORMAL output detail or above (see Result_Tracker::set_output_detail()); unused at SILENT

Returns: false if no probes have been recorded yet

◆ getFirstDAF()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::getFirstDAF	(	RETURNTYPE &	value,
		DIMTYPE &	feature,
		const unsigned int	DAFidx = 0 ) const

Starts an iteration (descending by value) over the feature ordering built by compute_stats() for the given DAF variant.

Parameters

value	set to the feature's DAF value on success
feature	set to the (global) feature index on success
DAFidx	selects the DAF variant: 0 (DAF0), 1 (DAF1) or 2 (DAF2); the fst4 CLI's --daf-rank only exposes 0 and 1, DAF2 is library-only

Returns: false if compute_stats() has not run or no feature has a valid value for this variant

◆ getFirstPairDAF()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::getFirstPairDAF	(	RETURNTYPE &	daf0,
		RETURNTYPE &	daf1,
		bool &	daf1_valid,
		RETURNTYPE &	synergy,
		DIMTYPE &	f1,
		DIMTYPE &	f2 ) const

Starts an iteration (decreasing pair-DAF0) over the pairwise statistics built by compute_pair_stats().

Parameters

daf0	set to mean(both present) - mean(both absent) for the pair
daf1	set to the DAF1-analogue normalization of `daf0`; 0 if `daf1_valid` is false
daf1_valid	set to false when the pair's normalization denominator is zero (`daf1` then holds 0)
synergy	set to the 2x2 interaction contrast (mean_both + mean_neither - mean_f1only - mean_f2only)
f1	set to the (global) index of the pair's first feature
f2	set to the (global) index of the pair's second feature

Returns: false if compute_pair_stats() has not run or found no valid pair

◆ getNextDAF()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::getNextDAF	(	RETURNTYPE &	value,
		DIMTYPE &	feature,
		const unsigned int	DAFidx = 0 ) const

Continues the getFirstDAF() iteration for the same DAFidx.

Returns: false once the ordering is exhausted (or if getFirstDAF() was never called for this DAFidx)

◆ getNextPairDAF()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::getNextPairDAF	(	RETURNTYPE &	daf0,
		RETURNTYPE &	daf1,
		bool &	daf1_valid,
		RETURNTYPE &	synergy,
		DIMTYPE &	f1,
		DIMTYPE &	f2 ) const

Continues the getFirstPairDAF() iteration.

Returns: false once the ordering is exhausted (or if getFirstPairDAF() was never called)

◆ print()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

virtual std::ostream & FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::print ( std::ostream & os ) const

inlineoverridevirtual

writes a human-readable identification of the object; base default writes nothing

Reimplemented from FST::Result_Tracker_Dupless< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >.

◆ print_pair_stats()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::print_pair_stats	(	std::ostream &	os = std::cout,
		const std::size_t	top_pairs = 0 )

Prints the pairwise statistics computed by compute_pair_stats() to os, best pair-DAF0 first.

Parameters

os	the output stream to print to
top_pairs	how many top pairs to print; 0 (the default) prints all valid pairs

Returns: false if compute_pair_stats() has not run (or found no valid pair)

◆ print_stats()

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

bool FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::print_stats ( std::ostream & os = std::cout )

Prints the per-cardinality and per-feature statistics computed by compute_stats() to os.

Returns: false if compute_stats() has not been run yet (nothing to print)

Member Data Documentation

◆ _n

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

DIMTYPE FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::_n

protected

total number of features in the tracked dataset (from the first recorded probe's Subset::get_n(), assumed the same for all probes); also the length of _stats and one less than the length of _dstat

◆ _pair_itersize

template<class RETURNTYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET>

std::size_t FST::Result_Tracker_Feature_Stats< RETURNTYPE, IDXTYPE, DIMTYPE, SUBSET >::_pair_itersize

mutableprotected

getFirstPairDAF()/getNextPairDAF() cursor position (index into _pair_order); 0 = iteration not started

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

/Users/psms/dev/devtest1/_src_search/result_tracker_feature_stats.hpp

Classes

Public Types

Public Member Functions

Protected Types

Static Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ PSubset

Constructor & Destructor Documentation

◆ Result_Tracker_Feature_Stats()

Member Function Documentation

◆ compute_pair_stats()

◆ compute_stats()

◆ getFirstDAF()

◆ getFirstPairDAF()

◆ getNextDAF()

◆ getNextPairDAF()

◆ print()

◆ print_pair_stats()

◆ print_stats()

Member Data Documentation

◆ _n

◆ _pair_itersize