Punti nello spazio e separazione lineare (?)

[ePiMeRaSi]

Buongiorno a tutti, sto cercando aiuto per risolvere un problema:

Ho due insieme di punti rappresentati da 3 coordinate xyz nello spazio (sono coordinate di atomi).
Il mio scopo è quello di trovare il miglior piano (NON iperpiano) che separi i due insiemi.
Quale sarebbe l'approccio migliore?
E' necessario l'uso di algoritmi come Percettrone o Support Vector Machine, oppure in questo caso ci sono approcci più immediati?

Il punto è che il mio scopo NON e' quello di addestrare un classificatore, ovvero non è machine learning. Lo scopo è quello di trovare il piano per poi verificare la distanza dallo stesso piano (in Angstorm) degli atomi di altre proteine superimposte.

[dissonance]

Benvenuto nel forum. Non credo proprio di poterti essere d'aiuto, però segnalo un punto che suona strano:

coordinate xyz nello spazio ...
il miglior piano (NON iperpiano)...

Come "NON iperpiano"? Cosa vuoi dire? In uno spazio 3-dimensionale, piano e iperpiano sono sinonimi. Penso sia meglio chiarire subito questo punto per evitare perdite di tempo successive.

[ePiMeRaSi]

Benvenuto nel forum. Non credo proprio di poterti essere d'aiuto, però segnalo un punto che suona strano:

coordinate xyz nello spazio ...
il miglior piano (NON iperpiano)...

Come "NON iperpiano"? Cosa vuoi dire? In uno spazio 3-dimensionale, piano e iperpiano sono sinonimi. Penso sia meglio chiarire subito questo punto per evitare perdite di tempo successive.

Sì, probabilmente ho usato io un termine improprio.

Quello che intendo è che a me non interessa un sistema che proietti i punti in spazi a più dimensioni per classificare i dati (come fanno le SVT ad esempio, per separare dati non separabili linearmente).
A me interessa proprio calcolare il piano nello spazio tridimensionale che separi meglio i due gruppi di atomi.

[gugo82]

Dovresti anche definire che vuol dire per te "separare meglio"...
Quando posso dire che un piano \( \displaystyle \Pi \) separa i due sistemi \( \displaystyle S_1 \) ed \( \displaystyle S_2 \) meglio di un altro piano \( \displaystyle \Pi^\prime \) ?

Non che sia sicuro di poterti aiutare, ma almeno così avrei qualche spunto da cui partire.

[ePiMeRaSi]

Dovresti anche definire che vuol dire per te "separare meglio"...
Quando posso dire che un piano \( \displaystyle \Pi \) separa i due sistemi \( \displaystyle S_1 \) ed \( \displaystyle S_2 \) meglio di un altro piano \( \displaystyle \Pi^\prime \) ?

Non che sia sicuro di poterti aiutare, ma almeno così avrei qualche spunto da cui partire.

E anche qui hai ragione (è che oggi ho proprio fuso, farei meglio ad andare a dormire e ripensarci domani ): intendo che la distanza media fra i punti di ogni insieme e il piano sia massima.

[gugo82]

Insomma, se ho ben capito, il problema lo possiamo scrivere come segue:

Siano \( \displaystyle S:=\{ x_1,\ldots ,x_n\} ,\ S^\prime :=\{ x_{n+1} ,\ldots ,x_N\} \) sottoinsiemi di \( \displaystyle \mathbb{R}^3 \) ( \( \displaystyle n
Determinare un "versore normale" \( \displaystyle \nu \in \mathbb{S}^2:=\{ u\in \mathbb{R}^3:\ |u|=1\} \) ed un "termine noto" \( \displaystyle d\in \mathbb{R} \) tali che il piano \( \displaystyle \Pi_{\nu ,d} \) d'equazione \( \displaystyle \langle \nu ,x\rangle =d \) (qui \( \displaystyle \langle \cdot ,\cdot \rangle \) è il prodotto scalare di \( \displaystyle \mathbb{R}^3 \) ) verifichi le seguenti condizioni:

1) \( \displaystyle \forall x_h\in S,\ \forall x_k\in S^\prime ,\ \langle \nu ,x_h\rangle \leq d\leq \langle \nu ,x_k\rangle \) (separazione debole dei punti di \( \displaystyle S \) ed \( \displaystyle S^\prime \) )
2) sia massima la funzione \( \displaystyle F(\nu ,d):=\frac{1}{N} \ \sum_{i=1}^N |\langle \nu ,x_i\rangle - d| \) (media delle distanze dei punti di \( \displaystyle S\cup S^\prime \) dal piano \( \displaystyle \Pi_{\nu ,d} \) )

Se non si aggiungono condizioni su \( \displaystyle S,S^\prime \) il problema può non avere soluzione: ad esempio, se \( \displaystyle {\left({d}{i}{s}{p}{l}{a}{y}{s}{t}{y}\le{S}={\left\lbrace{\mathfrak{{{o}}}}\right\rbrace}\right.} \) \) ed \( \displaystyle S^\prime =\{ \pm e^1,\pm e^2,\pm e^3\} \) (qui \( \displaystyle \mathfrak{o} =(0,0,0) \) ed \( \displaystyle e^j=(\delta_1^j,\delta_2^j,\delta_3^j) \) , \( \displaystyle j=1,2,3 \) , sono i vettori della base canonica di \( \displaystyle \mathbb{R}^3 \) ), allora non esiste nessun piano che separi \( \displaystyle S \) ed \( \displaystyle S^\prime \) .

A ben vedere ciò accade perchè le uniche coppie di insiemi disgiunti che possono sempre essere separate da un piano sono quelle costituite da due insiemi convessi; per le altre coppie di insiemi non c'è la certezza che possano essere separate da un piano.
Quindi, in generale, il problema non ha soluzione.

Per ovviare a questo inconveniente, si potrebbe fare l'ulteriore ipotesi che gli inviluppi convessi \( \displaystyle \text{conv} S, \text{conv} S^\prime \) siano disgiunti (probabilmente basta richiedere che abbiano gli interni relativi disgiunti): in tal caso il problema di ottimizzazione avrebbe almeno senso (poiché c'è almeno un piano che separa \( \displaystyle \text{conv} S, \text{conv} S^\prime \) e quindi anche \( \displaystyle S \) ed \( \displaystyle S^\prime \) ) e si potrebbe andare a cercare di stabilire l'esistenza di una soluzione con qualche tecnica standard.

Ci dovresti lavorare un po' sù.

[Sergio]

Un bel problema, che non saprei come affrontare.
Tuttavia, dato che "Percettrone" e "Support Vector Machine" (che ignoro) sembrano avere a che fare con le reti neurali e dato che le reti neurali vengono usate in statistica, provo a proporti un approccio statistico: esegui una cluster analysis sui tuoi atomi col metodo k-means e li dividi in due gruppi, poi individui i centroidi dei due gruppi (potrebbe darteli il software che usi) e un piano ortogonale al segmento che li congiunge in un punto da determinare sulla base dei diametri dei gruppi.
Il tutto detto con grande ignoranza del tuo problema

[gugo82]

Certo, probabilmente, se gli insiemi di punti \( \displaystyle S,S^\prime \) non sono assegnati a priori, esiste qualche tecnica per separare i punti in modo che il problema di ottimizzazione abbia senso.
E non credo serva necessariamente la statistica per separare i punti (a meno di non voler puntare tutto solo su una soluzione numerica, che può anche essere del tutto sballata senza un teorema di esistenza); probabilmente c'è qualche algoritmo che consente una divisione "comoda" dei punti in due insiemi senza ricorrere ad indagini numeriche.

Ovviamente, non interessandomi di queste cose, più di qualche idea non so darti.

[ePiMeRaSi]

Insomma, se ho ben capito, il problema lo possiamo scrivere come segue:

Siano \( \displaystyle S:=\{ x_1,\ldots ,x_n\} ,\ S^\prime :=\{ x_{n+1} ,\ldots ,x_N\} \) sottoinsiemi di \( \displaystyle \mathbb{R}^3 \) ( \( \displaystyle n
Determinare un "versore normale" \( \displaystyle \nu \in \mathbb{S}^2:=\{ u\in \mathbb{R}^3:\ |u|=1\} \) ed un "termine noto" \( \displaystyle d\in \mathbb{R} \) tali che il piano \( \displaystyle \Pi_{\nu ,d} \) d'equazione \( \displaystyle \langle \nu ,x\rangle =d \) (qui \( \displaystyle \langle \cdot ,\cdot \rangle \) è il prodotto scalare di \( \displaystyle \mathbb{R}^3 \) ) verifichi le seguenti condizioni:

1) \( \displaystyle \forall x_h\in S,\ \forall x_k\in S^\prime ,\ \langle \nu ,x_h\rangle \leq d\leq \langle \nu ,x_k\rangle \) (separazione debole dei punti di \( \displaystyle S \) ed \( \displaystyle S^\prime \) )
2) sia massima la funzione \( \displaystyle F(\nu ,d):=\frac{1}{N} \ \sum_{i=1}^N |\langle \nu ,x_i\rangle - d| \) (media delle distanze dei punti di \( \displaystyle S\cup S^\prime \) dal piano \( \displaystyle \Pi_{\nu ,d} \) )

Se non si aggiungono condizioni su \( \displaystyle S,S^\prime \) il problema può non avere soluzione: ad esempio, se \( \displaystyle {\left({d}{i}{s}{p}{l}{a}{y}{s}{t}{y}\le{S}={\left\lbrace{\mathfrak{{{o}}}}\right\rbrace}\right.} \) \) ed \( \displaystyle S^\prime =\{ \pm e^1,\pm e^2,\pm e^3\} \) (qui \( \displaystyle \mathfrak{o} =(0,0,0) \) ed \( \displaystyle e^j=(\delta_1^j,\delta_2^j,\delta_3^j) \) , \( \displaystyle j=1,2,3 \) , sono i vettori della base canonica di \( \displaystyle \mathbb{R}^3 \) ), allora non esiste nessun piano che separi \( \displaystyle S \) ed \( \displaystyle S^\prime \) .

A ben vedere ciò accade perchè le uniche coppie di insiemi disgiunti che possono sempre essere separate da un piano sono quelle costituite da due insiemi convessi; per le altre coppie di insiemi non c'è la certezza che possano essere separate da un piano.
Quindi, in generale, il problema non ha soluzione.

Per ovviare a questo inconveniente, si potrebbe fare l'ulteriore ipotesi che gli inviluppi convessi \( \displaystyle \text{conv} S, \text{conv} S^\prime \) siano disgiunti (probabilmente basta richiedere che abbiano gli interni relativi disgiunti): in tal caso il problema di ottimizzazione avrebbe almeno senso (poiché c'è almeno un piano che separa \( \displaystyle \text{conv} S, \text{conv} S^\prime \) e quindi anche \( \displaystyle S \) ed \( \displaystyle S^\prime \) ) e si potrebbe andare a cercare di stabilire l'esistenza di una soluzione con qualche tecnica standard.

Ci dovresti lavorare un po' sù.

Hai ragione, infatti non c'è la sicurezza che i punti siano linearmente separabili (cioè detto in parole povere, ci potrebbero essere alcuni punti dell'insieme A che stanno al dilà del piano insieme ai punti dell'insieme B e viceversa, per qualunque piano).
E' proprio per questo che nascono le reti neurali a strato nascosto e, ancora meglio, le support vector machine.

Comunque per ora ho risolto con una soluzione che è molto simile a quella proposta da Sergio (l'analisi k-means non serve poichè so già a quale insieme appartiene ogni punto). Sono partito dal vettore A-B (dove A e B sono i centroidi dei due insiemi), l'ho riscritto nella forma gamma*versore e ho variato gamma in un certo intervallo con una funzione di scoring basata sulla distanza dei punti da questo piano (ortogonale appunto al vettore gamma*versore).

A quel punto ho preso il gamma che mi dava il minimo (non il massimo).

Per Sergio: se può interessarti, le SVM sono un metodo di machine learning inventato nei laboratori Bells negli anni '90. Per avere un'idea molto informale delle differenze con le reti neurali a strato nascosto (di cui risolvono alcuni problemi) c'è la pagina di wikipedia italiana:
http://it.wikipedia.org/wiki/Macchine_a ... i_supporto

In rete comunque si trova molto materiale, sono fighe, ma abbastanza incasinate per chi come me non è un matematico