Algoritmos De Busqueda para la ciencia de datos

algoritmos de busqueda aplicados a la ciencia de datos

1. ALGORITMOS DE BÚSQUEDA POR: EVELYN ORELLANA INGENIERA EN SISTEMAS DE INFORMACIÓN Y CIENCIAS DE LA COMPUTACIÓN MASTER EN INTELIGENCIA ARTIFICIAL MASTER EN SISTEMAS INTELIGENTES UNIVERSIDAD MARIANO GÁLVEZ DE GUATEMALA FACULTAD DE INGENIERÍA EN CIENCIA DE DATOS Y ANALÍTICA INGENIERÍA EN CIENCIA DE DATOS Y ANALÍTICA Curso: 1 04 - Algoritmos y Fundamentos de Programación Sección: “A” Modalidad: En línea 1er . Semestre 202 5 . UMG Central

2. Pág No. ‹#› Los algoritmos de búsqueda son procedimientos que se utilizan para encontrar un elemento dentro de una colección de datos. Pueden aplicarse en estructuras como listas, árboles, grafos, bases de datos o incluso en el espacio de soluciones de un problema de optimización. Los algoritmos de búsqueda son la base de la eficiencia en la recuperación y optimización de datos. Qué son los algoritmos de búsqueda

3. Algoritmos de búsqueda Clásicos Pág No. ‹#›

4. Pág No. ‹#› Estos algoritmos se utilizan cuando se necesita encontrar un elemento dentro de una estructura de datos ordenada o desordenada. ✅ Búsqueda Lineal Recorre secuencialmente la lista hasta encontrar el elemento. Complejidad: O(n) en el peor caso. Ejemplo: Buscar un nombre en una lista desordenada. ✅ Búsqueda Binaria Requiere que los datos estén ordenados . Divide el conjunto en dos mitades y busca en la mitad donde pueda estar el elemento. Complejidad: O(log⁡ n) Ejemplo: Encontrar un número en una lista de valores ordenados. ✅ Búsqueda en Espacios No Estructurados Algoritmos como Interpolación o Jump Search optimizan la búsqueda en listas ordenadas cuando los datos siguen una distribución predecible. Algoritmos de Búsqueda Clásicos

5. Pág No. ‹#› Algoritmos de Búsqueda Clásicos Comparativo de los Algoritmos de búsqueda Clásicos

6. Pág No. ‹#› Son utilizados en problemas de optimización, redes, y rutas más cortas. ✅ Búsqueda en Profundidad (DFS - Depth First Search) Explora un camino completamente antes de retroceder y probar otro. Útil en problemas de laberintos o análisis de redes sociales. Complejidad: O(V+E) donde V son vértices y E son aristas. ✅ Búsqueda en Amplitud (BFS - Breadth First Search) Explora primero los nodos vecinos antes de moverse más profundo en el grafo. Se usa en redes para encontrar la ruta más corta. Complejidad: O(V+E). ✅ Algoritmos de Caminos Más Cortos Dijkstra: Encuentra la ruta más corta desde un nodo fuente. A* : Algoritmo heurístico que usa funciones de costo para optimizar la búsqueda. Algoritmos de Búsqueda en Grafos

7. Pág No. ‹#› Algoritmos de Búsqueda en Grafos Búsqueda en Amplitud (BFS - Breadth First Search) Búsqueda con algoritmo Dijkstra o el camino más corto Búsqueda con algoritmo A* Heurística

8. Pág No. ‹#› Algoritmos de Búsqueda en Grafos Comparativo de los Algoritmos de búsqueda en GRAFOS

9. Pág No. ‹#› En ciencia de datos, muchas veces trabajamos con millones o billones de registros , por lo que se requieren estrategias avanzadas. ✅ Búsqueda en Bases de Datos Índices B-Tree: Se usan en bases de datos SQL para optimizar la búsqueda. Hashing: Asigna claves a valores para recuperar información rápidamente. ✅ Búsqueda en Texto TF-IDF (Term Frequency-Inverse Document Frequency): Evalúa la relevancia de términos en documentos. Algoritmo de Levenshtein: Mide la distancia entre palabras para búsqueda aproximada. ✅ Búsqueda en Espacios de Alta Dimensión k-NN (k-Nearest Neighbors): Encuentra los puntos más cercanos en un espacio de características. Locality Sensitive Hashing (LSH): Reduce la dimensionalidad en grandes volúmenes de datos. Búsqueda en Grandes Volúmenes de Datos Búsqueda con B-tree

10. Pág No. ‹#› Búsqueda con Hashing con sondeo cuadrático Búsqueda en Grandes Volúmenes de Datos TF-IDF (Term Frequency-Inverse Document Frequency)

11. Pág No. ‹#› Algoritmo de Levenshtein Búsqueda en Grandes Volúmenes de Datos k-NN (k-Nearest Neighbors)

12. Pág No. ‹#› Búsqueda en Grandes Volúmenes de Datos L ocality Sensitive Hashing (LSH)

13. Pág No. ‹#› Búsqueda en Grandes Volúmenes de Datos Algoritmo Descripción Complejidad Ejemplo Búsqueda en Bases de Datos Índices B-Tree Se usan en bases de datos SQL para optimizar la búsqueda, permitiendo búsquedas más rápidas y eficientes. O(log n) Uso en bases de datos relacionales (SQL). Hashing Asigna claves a valores para recuperar información rápidamente, ideal para búsquedas directas. O(1) en promedio, O(n) en el peor caso Uso en tablas hash para almacenamiento eficiente. Búsqueda en Texto TF-IDF (Term Frequency-Inverse Document Frequency) Evalúa la relevancia de términos en documentos, utilizado en motores de búsqueda y recuperación de información. O(n) (para cada término) Búsqueda de información en grandes colecciones de texto. Algoritmo de Levenshtein Mide la distancia entre palabras para búsqueda aproximada, útil en corrección ortográfica. O(m * n), donde m y n son las longitudes de las dos cadenas Corrección ortográfica y búsqueda difusa en motores de texto. Búsqueda en Espacios de Alta Dimensión k-NN (k-Nearest Neighbors) Encuentra los puntos más cercanos en un espacio de características, usado en clasificación y regresión. O(n * d), donde n es el número de puntos y d es la dimensión del espacio Clasificación en aprendizaje supervisado o recomendación de productos. Locality Sensitive Hashing (LSH) Reduce la dimensionalidad en grandes volúmenes de datos, preservando la cercanía de los puntos en el espacio. O(n) Búsqueda de vecinos más cercanos en bases de datos de imágenes o textos. Comparativo de los Algoritmos de búsqueda en grande Volúmenes de Datos

14. Pág No. ‹#› En aprendizaje automático y optimización se usan algoritmos de búsqueda para encontrar parámetros óptimos: ✅ Optimización de Hiperparámetros Grid Search: Prueba todas las combinaciones de hiperparámetros. Random Search: Prueba combinaciones aleatorias. Bayesian Optimization: Encuentra los mejores hiperparámetros con un enfoque probabilístico. ✅ Metaheurísticas para Optimización Algoritmos Genéticos: Simulan la evolución para encontrar soluciones óptimas. Recocido Simulado (Simulated Annealing): Explora el espacio de búsqueda con un enfoque probabilístico. Algoritmos de Búsqueda en Ciencia de Datos Aplicada

15. Pág No. ‹#› Grid Search : Prueba todas las combinaciones de hiperparámetros. Algoritmos de Búsqueda en Ciencia de Datos Aplicada: Optimización de hiperparámetros Random Search: Prueba combinaciones aleatorias.

16. Pág No. ‹#› Bayesian Optimization: Encuentra los mejores hiperparámetros con un enfoque probabilístico. Algoritmos de Búsqueda en Ciencia de Datos Aplicada

17. Pág No. ‹#› Algoritmos Genéticos: Simulan la evolución para encontrar soluciones óptimas. Algoritmos de Búsqueda en Ciencia de Datos Aplicada: Metaheurísticas para Optimización Recocido Simulado (Simulated Annealing): Explora el espacio de búsqueda con un enfoque probabilístico.

18. Pág No. ‹#› Algoritmos de Búsqueda en Ciencia de Datos Aplicada: Metaheurísticas para Optimización Algoritmo Descripción Complejidad Ejemplo Optimización de Hiperparámetros Grid Search Prueba todas las combinaciones de hiperparámetros posibles en una cuadrícula definida. O(n * m), donde n es el número de combinaciones y m el número de iteraciones Ajuste de hiperparámetros en modelos de aprendizaje automático. Random Search Prueba combinaciones aleatorias de hiperparámetros en el espacio de búsqueda definido. O(k), donde k es el número de combinaciones aleatorias probadas Optimización de modelos de machine learning con exploración aleatoria. Bayesian Optimization Encuentra los mejores hiperparámetros mediante un enfoque probabilístico, optimizando el proceso de búsqueda. O(T * d²), donde T es el número de iteraciones y d es la dimensión del espacio Optimización de modelos complejos en machine learning. Metaheurísticas para Optimización Algoritmos Genéticos Simulan el proceso de evolución biológica para encontrar soluciones óptimas mediante selección, cruzamiento y mutación. O(N * G), donde N es el tamaño de la población y G es el número de generaciones Optimización de diseños y problemas de selección de características. Recocido Simulado (Simulated Annealing) Explora el espacio de búsqueda con un enfoque probabilístico, aceptando soluciones peores temporalmente para evitar óptimos locales. O(n * log n) Resolución de problemas de optimización combinatoria, como el viajante de comercio. Comparativo de los Algoritmos de búsqueda Metaheurísticas para Optimización

19. Pág No. ‹#› Conocer Más PDF: Métodos clasicos de ordenamiento y búsqueda: https://gc.scalahed.com/syllabus/cloud/visor.php?container=L1IS104_1035_615_35228_0&object=M%C3%A9todos%20de%20Ordenaci%C3%B3n.pdf VIDEO: Algoritmos metaheurísticos: optimización y búsqueda basada en la naturaleza. https://www.youtube.com/watch?v=442wNqXCjrU VIDEO: Optimización de Sistemas de Control: Metaheurísticas y Diseño Automático de Algoritmos en Ingeniería https://www.youtube.com/watch?v=MyMwzhKleS8

20. Actividades Anotarse en el listado de asistencia que se encuentra en el siguiente link: https://forms.gle/tU77dvGeUgiX97QP7 Realizar la hoja de trabajo No. 2 que ha sido enviada a su correo de la umg. Al terminar de resolverla, enviar el resultado al correo: [email protected] Pág No. ‹#›

21. Gracias por su atención…