Сколько может рассказать о человеке профиль в соцсети? Фотографии, посты, комментарии, подписки – непаханное поле для анализа. Сегодня поговорим о том, как мы определяем интересы пользователей на основе их подписок в сети Instagram.
Рубрика «графы» - 3
Обнаружение пересекающихся сообществ в Instagram для определения интересов пользователей
2019-10-09 в 8:32, admin, рубрики: big data, community detection, Instagram, snap, аналитика данных, Блог компании Dentsu Aegis Network, графы, Интернет-реклама, машинное обучение, медийная реклама, Социальные сети и сообществаКак правильно раскрашивать многочлены
2019-09-11 в 8:31, admin, рубрики: графы, математика, многочлены, Научно-популярное, раскраска графовМногочлены – это не просто упражнения в абстрактных материях. Они прекрасно подходят для выявления структур в неожиданных местах.
В 2015 году бывший поэт, ставший математиком, Джун Хо помог решить задачу, сформулированную около 50 лет назад. Она была связана со сложными математическими объектами, "матроидами", и графами (комбинациями точек и отрезков). А ещё она была связана с многочленами – знакомыми нам с уроков математики выражениями, состоящими из суммы переменных, возведённых в различные степени.
В какой-то момент в школе вы, наверное, проходили раскрытие скобок у многочленов. К примеру, вы можете помнить, что x2 + 2xy + y2 = (x + y)2. Удобный алгебраический трюк, но где он может пригодиться? Оказывается, что многочлены отлично помогают выявлять скрытые структуры – и в своём доказательстве Хо активно использовал этот факт. Вот простая загадка, иллюстрирующая это.
Читать полностью »
Визуализация больших графов для самых маленьких
2019-09-04 в 11:04, admin, рубрики: data mining, embeddings, graph, network, visualization, Блог компании Open Data Science, большие графы, визуализация, визуализация данных, графы, искусственный интеллект, машинное обучение
Что делать, если вам нужно нарисовать граф, но попавшиеся под руку инструменты рисуют какой-то комок волос или вовсе пожирают всю оперативную память и вешают систему? За последние пару лет работы с большими графами (сотни миллионов вершин и рёбер) я испробовал много инструментов и подходов, и почти не находил достойных обзоров. Поэтому теперь пишу такой обзор сам.
Читать полностью »
Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора. Ч.2
2019-08-23 в 15:07, admin, рубрики: big data, data mining, python, Алгоритмы, графы, исследование, кредитный скоринг, машинное обучение, обучение, теория графов, финансы в ITЧасть вторая, в которой Атосу все норм, а вот Графу де ля Фер чего-то не хватает
Вступление от авторов:
Добрый день! Сегодня мы продолжаем цикл статей, посвященный скорингу и использованию в оном теории графов. С первой статьей Вы можете ознакомиться здесь.
Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения
Цель данной статьи: не более, чем за 30 минут, описать основные способы хранения данных о графах и описать правила и принципы построения нашей модели для скоринга заемщика.
Термины и определения:
- Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Поиск по хеш-таблице, в среднем, осуществляется за время О(1).
Аудиторы, нанятые ПАО «Король» для оценки кредитоспособности НПАО «Один за всех», столкнулись с некоторыми проблемами. С одной стороны, описать схему взаимодействия 10-15 компаний и провести первичную оценку взаимодействия между компаниями очень просто, достаточно иметь под рукой лист бумаги и ручку. Но, что делать, если у вас имеется информация о взаимодействии десятков или сотен тысяч компаний? Например, если Вам нужно описать взаимодействия Арамиса со всеми его пассиями или Д’артаньяна со всеми, с кем он дрался?
Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора
2019-08-20 в 16:51, admin, рубрики: big data, data mining, python, Алгоритмы, графы, исследование, кредитный скоринг, машинное обучение, обучение, теория графов, финансы в ITЧасть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо
Вступление от авторов:
Добрый день! Сегодня мы начинаем цикл статей, посвященных скорингу и использованию в оном теории графов (Т.Г.). Надеюсь, нам хватит запала, сил и терпения, т.к. тема достаточно объемная и, на наш взгляд, интересная.
Несмотря на шуточное название, мы постараемся затронуть отнюдь не шуточные темы, которые уже сейчас влияют на жизнь многих из нас, а в ближайшем будущем могут коснуться всех, без исключения.
Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения
А теперь к делу.
Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.
Термины и определения:
- Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
- Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»
Полный граф может выглядеть следующим образом:
Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…
Российский математик опроверг 53-летнюю гипотезу о раскраске сетей
2019-08-02 в 7:00, admin, рубрики: гипотеза Хедетниеми, графы, математика, Научно-популярное, теория графов, хроматические числаВсего три страницы потребовалось российскому математику, чтобы описать способ раскраски сетей определённого типа, превзошедший ожидания экспертов
В опубликованной в онлайне работе опровергается гипотеза 53-летней давности, касающаяся наилучшего способа назначения цветов узлам сети. В работе всего на трёх страничках показано существование способов раскраски определённых цветов, превзошедших все ожидания экспертов.
Задачи по раскраске сетей [см. хроматическое число / прим. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.
Читать полностью »
Отладка алгоритмов на графах — теперь с картинками
2019-07-26 в 14:49, admin, рубрики: hse, Visual Studio, Visual Studio extension, vs, алгоритмы на графах, Блог компании Питерская Вышка, визуализация, визуализация данных, вшэ, графы, отладка, питерская вышка, плагин, ПрограммированиеПредставим типичную ситуацию на первом курсе: вы прочитали про алгоритм Диница, реализовали, а он не заработал, и вы не знаете, почему. Стандартное решение — это начать отлаживать по шагам, каждый раз рисуя текущее состояние графа на листочке, но это жутко неудобно. Я попробовала исправить положение в рамках семестрового проекта по Software Engineering, а в посте расскажу, как у меня в итоге получился плагин для Visual Studio. Скачать можно тут, исходный код и документацию можно посмотреть тут. Вот скриншот графа, который получился для алгоритма Диница.
Специалисты по информатике расширяют рубежи проверяемого знания
2019-07-18 в 7:00, admin, рубрики: IP, mip, neexp, np, графы, квантовая физика, квантовые компьютеры, квантовые технологии, математикаВселенная задач, проверяемых компьютером, выросла. Благодаря какому секретному ингредиенту это произошло? Из-за квантовой запутанности.
Представьте, что некто пришёл к вам и заявил, что у него есть оракул, способный раскрыть сокровенные тайны вселенной. Вы могли бы заинтересоваться этим, но вам тяжело было бы в это поверить. Вы бы хотели придумать способ подтвердить, что оракул говорит правду.
Такова основная проблема информатики. Некоторые задачи слишком сложно решить за разумное время. Но их решения просто проверить. Учитывая это, специалистам по информатике хочется знать: насколько сложной может быть задача, решение которой всё ещё можно проверить?
Оказывается, что ответ на этот вопрос: практически невообразимо сложной.
Читать полностью »
Элемент нулевого размера
2019-06-16 в 9:18, admin, рубрики: Анализ и проектирование систем, графы, изобретение, инженерные системы, комбинаторика, Научно-популярное, проектирование, ТРИЗ, функция
Графы — схематическое обозначение во многих сферах.
Модель реальных объектов.
Круги — вершины, линии — дуги графа (соединения).
Если рядом с дугой цифра — это расстояние между точками на карте или стоимость на диаграмме Ганта.
В электрике и электронике вершины — это детали и модули, линии — проводники.
В гидравлике котлы, бойлеры, арматура, радиаторы и трубы.
На карте — города и дороги.
Из школьной задачи по математике:
Из пункта А в пункт Б выехал автобус. Расстояние между пунктами 30 км.
А что если расстояние 0?
Читать полностью »
Оптимизация поиска в ширину: как обработать граф с 10 миллиардами состояний
2019-06-11 в 6:27, admin, рубрики: breadth-first search, Алгоритмы, алгоритмы поиска, головоломки, графы, Игры и игровые приставки, оптимизация кода, поиск в ширину, поисковые технологии, Программирование
Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.
Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.
Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Читать полностью »