Determina la gamma di frequenze più simile all'elenco di frequenze in ingresso

4

    Poiché questa domanda non riguarda il "codice non funzionante", sto chiedendo la mia prima domanda qui invece di StackOverflow. Informami se mancano le informazioni richieste dalla domanda.

Impostazioni

Ho due dizionari di tipo Dictionary<int, int> dove le chiavi sono un intervallo da 1 a n e i valori sono le frequenze di quei numeri. Ad esempio:

var frequenciesA = new Dictionary<int, int>
{
    { 1, 3 },
    { 2, 5 },
    { 3, 4 }
};

var frequenciesB = new Dictionary<int, int>
{
    { 1, 1 },
    { 2, 3 },
    { 3, 4 }
};

ingresso:

Ora avrò una lista di interi come input, nell'intervallo da 1 a n , come questo:

var numbers = new List<int> { 1, 2, 3, 3, 2, 1, 1, 2, 3, 1, 2, 2 };

Creo anche un dizionario di frequenza da questo elenco con il seguente codice:

var frequenciesFromInput = Enumerable.Range(1, 3)
                                     .ToDictionary(x => x,
                                                   x => numbers.Count(y => y == x));

Ciò risulterebbe nelle seguenti coppie chiave-valore:

K  V
----
1  4
2  5
3  3

Problema:

Supponiamo di dover determinare a quale degli altri dizionari (A o B) le frequenze siano uguali, sarebbe semplice: prendere i valori dei dizionari come una lista e usare Enumerable.SequenceEqual < T > metodo.

Ma nel mio caso ho bisogno di determinare quale dizionario (A o B) corrisponde più vicino alle frequenze del dizionario di input. Visualizzarlo rende più facile la comprensione. Ecco i grafici per le frequenze costanti del dizionario A e B:

Edeccoilgraficodeldizionariodiinput:

ComepuoivederelefrequenzediApiùvicinerispettoaquellediB.

Domanda:

Comeiniziareacreareunmetodo/algoritmoperdeterminarequaledizionario(AoB)èpiùvicinoaquellodeldizionariodiinput.Nonstochiedendounapienaimplementazione,solounapiccolaspinta,perchéoranonhoideadidoveecomeiniziare.

L'unicacosachepotevopensareeraqualchevariazionedel Problema dello zaino , ma io Non sono sicuro di essere sulla strada giusta lì.

    
posta Abbas 07.08.2015 - 15:12
fonte

3 risposte

3

La sottrazione vettoriale dovrebbe essere sufficiente. E trova la media (o il quadrato medio della radice) delle differenze assolute - la più piccola, la corrispondenza più stretta.

EDIT:

Esempio:

** Root mean squared = Sqr(Sum(xi²)/n) dove xi è Differences

    
risposta data 07.08.2015 - 16:58
fonte
2

Il nome googleable per il tuo problema è la creazione di un classificatore statistico . È un argomento abbastanza ampio. Puoi provare una sottrazione vettoriale di base come la risposta di kunthet e vedere se funziona per la tua applicazione. Tuttavia, se ti ritroverai con molte classificazioni errate, ci sono molte considerazioni che possono migliorare drasticamente la precisione del tuo classificatore.

Ad esempio, forse hai un sacco di documenti e vuoi sapere se sono stati scritti da Pharrell o Shakespeare. La sottrazione vettoriale diretta pondererà in modo sproporzionato le parole con grandi differenze di frequenza coincidenti come la parola the , rispetto alle parole meno frequenti che sono molto più utili nella classificazione, come forsooth o happy . Esistono algoritmi di estrazione delle caratteristiche che possono determinare automaticamente quelle parole più utili e algoritmi di classificazione che possono pesarli in modo appropriato.

In ogni caso, prova prima l'algoritmo semplice. Tieni presente che ci sono molte piccole insidie in questo tipo di problema, che potresti dover approfondire per risolvere.

    
risposta data 07.08.2015 - 20:27
fonte
1

Poiché i dati possono essere considerati vettori, l'aritmetica vettoriale offre una soluzione semplice. Questo approccio ha il vantaggio di consentire l'uso di una libreria vettoriale esistente o di creare una libreria vettoriale, che è possibile utilizzare per altri progetti.

"Più vicino" è una questione di distanza. Ci sono varie metriche che danno la distanza tra i vettori cartesiani, ma il più comune è Euclideo , ℓ₂ . La distanza euclidea può essere definita in termini di più operazioni di base del vettore.

Inizia con la sottrazione vettoriale, che viene eseguita in base al componente: la differenza tra vettori è il vettore di differenze. In un certo senso, la sottrazione si distribuisce attraverso la vettorizzazione. Simbolicamente:

<xᵢ> - <yᵢ> = <xᵢ - yᵢ>

Hai anche un prodotto componentwise:

⃑x * ⃑y = <xᵢ*yᵢ>

Il prossimo è il prodotto punto ( · ), che è la somma dei componenti del prodotto componentwise:

⃑x · ⃑y = ∑(⃑x * ⃑y)ᵢ

La norma euclidea ( norme in matematica sono funzioni di lunghezza astratta) è la radice quadrata del prodotto punto:

‖⃑x‖ = √(⃑x · ⃑x)

Nota la norma euclidea è fondamentalmente il teorema di Pitagora in n-dimensioni, che puoi vedere espandendo le operazioni:

‖⃑x‖ = √(∑(⃑x * ⃑x)ᵢ) = √(∑(xᵢ²)) = √(x₀²+x₁²+...+x₏²)

Infine, la distanza euclidea è la norma euclidea della differenza:

ℓ₂(⃑x,⃑y) = ‖⃑x - ⃑y‖

Trovare il vettore più vicino da una collezione è la generica funzione min : loop sulla raccolta, tenendo traccia dell'elemento (qui, vettore) con il valore più piccolo (qui, distanza) visto fino ad ora.

Vedi anche il metodo minimi quadrati , che è quasi equivalente ma è in termini di funzioni piuttosto che di vettori e omette che prendono la radice quadrata (che non è necessaria per questo particolare problema).

    
risposta data 07.08.2015 - 22:11
fonte

Leggi altre domande sui tag