La regresión lineal es útil cuando tenemos dos variables relacionadas linealmente o cuya relación se puede aproximar a la ecuación de un línea. La forma habitual de verlo es como una nube de puntos donde se calcula una recta que minimiza la distancia a todos los puntos. Se puede ver un ejemplo extraído de la wikipedia debajo:

De Sewaqu – Trabajo propio, Dominio público, Enlace

Nosotros vamos a usarlo para calcular de forma automática la relación entre dos variables, siempre y cuando esta sea lineal. Al final del proceso obtenemos la ecuación de una recta en la forma:

y = mx + b

Para ello se parte de una muestra de valores (x, y). Estos valores no deben de coincidir exactamente con la recta (serian los puntos azules de la imagen).

Las formulas para calcular lo parámetros:

m = σ²(x,y) / σ²(x)

b = µ(y) – m * µ(x)

Siendo σ²(x,y) la covarianza, σ²(x) la varianza y µ(x) la media

El mayor problema que hay en el caso de un arduino es que no hay memoria para guardar todas las muestras así que hemos de encontrar una forma de ir calculando estos valores estadísticos sin guardar todo el histórico de datos, de forma incremental. La solución la encontré aquí.  Así no hace falta guardar todos os valores, esto ademas permite que el algoritmo este siempre aprendiendo, aunque lo veremos más adelante.

También podemos calcular la correlación entre variables. Contra más cercano a a 1 o -1 mejor ya que indica una alta correlación entre ambas variables, sin embargo si es cercano a 0 indica una nula correlación.

r = σ²(x,y) / (σ(x) * σ(y))

Siendo r la correlación y σ(x) la desviación estándar, igual a √σ²(x).

Al final los cálculos en C para el arduino de m y b quedan en:

meanX = meanX + ((x-meanX)/n);
meanX2 = meanX2 + (((x*x)-meanX2)/n);
varX = meanX2 - (meanX*meanX);

meanY = meanY + ((y-meanY)/n);
meanY2 = meanY2 + (((y*y)-meanY2)/n);
varY = meanY2 - (meanY*meanY);

meanXY = meanXY + (((x*y)-meanXY)/n);

covarXY = meanXY - (meanX*meanY);

m = covarXY / varX;
b = meanY-(m*meanX);

Y para la correlación:

double stdX = sqrt(varX);
double stdY = sqrt(varY);
double stdXstdY = stdX*stdY;
double correlation;

if(stdXstdY == 0){
  correlation = 1;
} else {
  correlation = covarXY / stdXstdY;
}

Limites

En la vida real lo más probable es que no nos interese aplicar la regresión lineal a todos los posibles valores de la función solo a los que están contenidos entre  dos punto para ello se fijan los limites en los que la linea esta definida en el constructor.

LinearRegression lr = LinearRegression(0,100);

Fijar el valor de N

Una de las ventajas de este algoritmo es que es capaz de ir recalculando su valor de manera dinámica según se añaden más datos. El problema es que según crece n los nuevos datos cambian la media cada vez menos. Si por ejemplo tratamos con un valor que cambia con el tiempo y queremos que la recta se vaya adaptando debemos fijar el valor de n de tal forma que lo permita. Lo complicado esta en acertar con ese valor, si es muy bajo sera muy sensible al ruido y si es muy alto necesitara mucho tiempo para adaptarse a los nuevo valores.

En este caso se puede hacer con la función fixN

lr.fixN(100);

Regresión lineal segmentada

El principal problema de la regresión lineal es que es lineal. ¿Y si necesitamos que se adapte a una distribución que no sea una linea?. Se puede conseguir algo más de flexibilidad definiendo varias lineas de regresión. Podemos dividir una distribución de puntos en varios tramos y en cada tramo calcular su linea de regresión, así en lugar de una solo linea tenemos un conjunto de ellas, para ello podemos usar lo limites que se le pasa en el constructor

LinearRegression lr = LinearRegression(0,20);

LinearRegression lr = LinearRegression(0,40);

LinearRegression lr = LinearRegression(0,60);

LinearRegression lr = LinearRegression(0,80);

LinearRegression lr = LinearRegression(0,100);

Ejemplo

#include 

LinearRegression lr = LinearRegression(0,100);

void setup() {
  lr.learn(1,3);
  lr.learn(2,4);
  lr.learn(3,5);
  lr.learn(4,6);
  lr.learn(5,7);
  lr.learn(6,8);

  Serial.begin(9600);

}

void loop() {
  Serial.print("Result: ");
  Serial.println(lr.calculate(6));

  Serial.print("Correlation: ");
  Serial.println(lr.correlation());

  Serial.print("Values: ");

  lr.getValues(values);
  Serial.print("Y = ");
  Serial.print(values[0]);
  Serial.print("*X + ");
  Serial.println(values[1]);

  delay(2000);
}

La librería esta disponible en github

Números pseudoaletorios, función random()

Primero vamos a ver como generar números pseudoaleatorios usando la función random() de Arduino. Su uso es muy sencillo primero, normalmente en la función setup, se fija la semilla del generador usando la función randomSeed() y un valor que se le pasa como parámetro y luego se invoca a la función random() usadon una de sus dos versiones:

random(max)
random(min, max)

La primera calcula un valor entre 0 y max, la segunda entre min y max.

La semilla fijada en radomSeed() se usa para generar una secuencia de números pseudoaleatorios. A diferencia de los números aleatorios, que son distintos cada vez, los pseudoaletaorios son siempre los mismos. Cada semilla genera una secuencia única de números aleatorios que es siempre la misma. Por lo que si queremos que cada vez que reiniciemos la placa la secuencia de números sea diferente, tenemos que establecer la semilla con un valor que cambie cada vez. Hay varias opciones:

• Tener un valor almacenado en la memoria EEPROM e incrementarlo en cada vez que se inicie el programa y usarlo como semilla.
• Usar la función micros() que devuelve el número de microsegundos desde que el software se inicio.
• El más habitual es usar el valor de de un puerto analógico donde no haya nada conectado.

El problema de usar estos tres métodos es que el primero es predecible y los otros dos no son realmente buenas fuentes de aleatoriedad. Sin embargo para la mayoría de los casos (que no se requieran números realmente aleatorios por seguridad) pueden ser suficientes.

Un ejemplo de uso:

long randNumber;

void setup() {
  Serial.begin(9600);  
  randomSeed(analogRead(0));
}

void loop() {
  //devuelve un número entre 0 y 300  
  randNumber = random(300);
  Serial.println(randNumber);

  //devuelve un número entre 10 y 200
  randNumber = random(10, 20);
  Serial.println(randNumber);

  delay(2000);
}

Generar números realmente aleatorios con un trozo de cable y analogRead

Si buscas una manera de generar números realmente aleatorios con Arduino se suele aconsejar recurrir a leer el valor de un puerto analógico que no este conectado a nada. El problema es que realmente los valores obtenidos no son aleatorios. Suelen oscilar en torno a un valor sin alejarse demasiado de él. Es decir si el valor leído es el 150 los más probable es que el siguiente número sea cercano, es más probable que sea el 151 que el 3. Cómo generador de números aleatorios no solo no es ninguna maravilla, es que es en muchos casos peor que el generador de números pseudoaleatorios de random()

Hay montajes electrónicos que producen valores aleatorios a partir del ruido que sufren sus componentes, pero suelen ser complicados. (Además ya no sería con un Arduino y tengo que justificar que el articulo este en la sección de «Arduino»)

Volviendo a nuestra idea de leer valores del puerto analógico vemos que el problema es que los números que devuelven oscilan entorno a un valor, esto se debe a que lo que leemos es el ruido en el puerto analógico, el ruido actúa como función aleatoria, pero este ruido tienen una característica especial, que explicada breve y mal es: «A más fuerte sea el ruido menos probable es que ocurra». Por lo tanto variaciones grandes del valor del puerto analógico son poco probables. Sin embargo hay una parte muy pequeña de este valor que si que se ve sometida a variaciones, la parte más pequeña del valor del puerto y por tanto la que más fácilmente varia, el bit de menor peso. Vamos a tomar solo ese bit y con ocho de ellos componer un byte. Ese byte debería ser aleatorio.

Para obtener el bit de menor peso podemos usar el siguiente código:

analogRead(analogInput)%2

Veamos el ejemplo para obtener un byte leyendo el puerto 8 veces:

byte randomAnalog(int analogInput){
  byte rnd = 0;
  for(int i = 0; i <; 8; i++){
    int aux = analogRead(analogInput)%2 << i; 
    rnd += aux;
    delay(10);
  }
  return rnd;
}

El delay(10) lo añadí por que sin ninguna espera analogRead me devolvía el mismo valor varias veces.

¿Pero donde esta el cable? Os preguntareis. Para aumentar el ruido, nada mejor que conectar un cable suelto en el  puerto que se va a leer, contra más largo y retorcido esté mejor.

Combinar varias fuentes

Si te fías poco de este sistema puedes usar dos fuentes, o más, de aleatoriedad obteniendo bytes de dos puertos analógicos distintos y luego combinándolos con un xor.

byte r0 = randomAnalog(A0);
byte r1 = randomAnalog(A1);

byte r = r1 ^ r0;

Puede encontrar el código en el repositorio de github de ArduTips.

Un problema que pueden tener estos sistemas es que generalmente cuando hablamos de números aleatorios nos referimos a que producen produce el bit 0 y el bit 1 con un 50% de probabilidades (lo que se denomina un sistema justo), pero en este caso no podemos estar seguros de que sea así, sin embargo hay una manera de convertir cualquier sistema aleatorio a justo se puede leer aquí.

Puedes ver la explicación en vídeo de como generar números pseudoaleatorios en mi canal de youtube:

También esta disponible el vídeo de como generar números aleatorios:

Parece imposible cifrar de forma segura en un arduino con una potencia de cálculo equiparable a la de un despertador. Pero eso es porque siempre que se habla de cifrado se acaba hablando de complicados algoritmos matemáticos, sin embargo se puede lograr un cifrado perfectamente seguro usando operaciones matemáticas más simples. Os presento la forma de cifrado más simple.

Cifrar:

Ci = Mi xor Ki

Descifrar:

Mi = Ci xor Ki

Una simple operación xor de un byte del mensaje M con un byte de la contraseña de cifrado K. Os estaréis preguntando que si es tan seguro por qué no lo usamos en lugar de complicados algoritmos. Bueno tiene una pega, la contraseña ha de ser completamente aleatoria (o en su defecto lo más aleatoria posible) y ambos han de tener la misma longitud. Este sistema se conoce como libreta de un solo uso. Su nombre no es caprichoso, usar la misma contraseña de cifrado más de una vez para cifrar otro mensaje compromete la seguridad del sistema.

//Cifrar
C[i] = M[i] ^ K[i+j]; // j es el punto del cuaderno usado hasta la fecha.

//Descifrar
M[i] = C[i] ^ K[i+j]; // j es el punto del cuaderno usado hasta la fecha.

El problema de generar la larguísima "libreta" para cifrar lo dejo en vuestras manos. Podéis usar un generador en cualquier lenguaje, comprar números aleatorios, escribir en papelitos un montón de números tirarlos a aire y apuntarlos según se recogen...hay infinitas posibilidades y contra menos predecible sea el sistema usado, mejor. De hecho esa es su principal vulnerabilidad que la secuencia usada sea predecible.

Con esa larga secuencia de bytes usados para cifrar ya conseguida. El siguiente paso es cifrar lo que se quiera enviar. Para ello se toma un byte de datos y un byte de la "libreta", se realiza un xor entre ambos y listo. Es sencillo y el coste computacional es mínimo.  Los byte de la libreta siempre se cogen de forma secuencial sin nunca repetirlos pase lo que pase.

Por supuesto todos los dispositivos que participan en la conversación tienen que tener una copia de la contraseña. Que se les ha tenido que "entregar" de forma segura (conectadolos con un cable o con una tarjeta SD) eso significa que el acceso físico a uno de estos dispositivos compromete la seguridad del cifrado (como con casi todos los sistemas). También es necesario incluir en el mensaje un numero de secuencia que indique a partir de que punto de la "libreta" usar para descifrar.

Para intentar agotar la "libreta" lo más tarde posible hay que procurar no cifrar datos innecesarios. Por otro lado, en algunos casos es necesario cifrar algún tipo de contador para votar ataques de repetición. Es posible que en algunos casos necesitemos "libretas" grandes por lo que habrá que ampliar la capacidad de almacenamiento del dispositivo por ejemplo montando un lector de tarjetas microSD con eso podemos tener espacio para una "libreta" que nos dure siglos y sale más barato que recurrir a otro tipo de soluciones.

En caso de terminar con la "libreta" hay que evitar reutilizarla. Podemos hacer un truco para tratar de alargar su utilidad. Aunque este truco no nos asegura que el cifrado vuelva a ser completamente seguro. El truco consiste en aplicar dos tipos de operaciones a la clave:

• Intercambiar posiciones de los caracteres
• A cada carácter aplicarle rotaciones de bits, negaciones o xor. Mejor si se combinan varias de  ellas.

Es buena idea no realizar exactamente las mismas operaciones en cada carácter si no variarlas siguiendo un patrón lo mas grande posible carácter. Estás operaciones han de conocerse por todos los dispositivos que participan en la comunicación ya que si no obtendrán "libretas" distintas.

Con eso la libreta obtenida no es segura ni mucho menos, y lo correcto seria cambiarla, pero es mejor opción que reutilizarla directamente. Como ventaja está de nuestra parte que este tipo de dispositivos suelen transferir pocos datos así que hasta que el atacante consiga una cantidad suficiente de datos como para descifrar nuestros mensajaes puede tardar mucho tiempo. Del orden de semanas, meses o años.