Май 2009 - Posts

Ссылки на 30.05.2009. Датасеты и наборы данных
30 мая 09 04:08
  • INRIA Datasets - большие коллекции изображений INRIA (1GB и 1.6GB)  собранные с Flickr
  • 1.5 миллиона небольших картинок - датасет который я уже упоминал, но менее интересным он от этого не становится (3.5 GB)
  • ImageNet.org - объединение WordNet и огромной базы в количестве 3,247,902 изображений и 5247 синсетов. Есть возможность запросить доступ к полной базе и API.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Postedfrom Иван Бегтин | 0 Comments    
Filed under: ,
Электронное Правительство
30 мая 09 03:49

Пока я некоторое время пребывал в оффлайне произошла масса интересных событий. Прокомментирую хотя бы часть из них:

Новая программа “Электронное правительство”

Собственно новость на сайте правительства , я процитирую полностью и подчеркну самое интересное.

—-

Мы с вами посмотрим сегодня, как идет работа по федеральной целевой программе “Электронная Россия”. Я не буду сейчас говорить о важности этого направления нашей деятельности. Понятно, что это одно из ключевых направлений инновационного развития. И от того, насколько эффективно мы работаем в этой сфере, напрямую зависит эффективность и экономики, и государственного управления, и состояния социальной сферы. Напрямую от этого зависит положение в таких областях, как образование, здравоохранение и по некоторым другим направлениям.

Между тем, можно утверждать, что, к сожалению, до сих пор поставленных в рамках этой федеральной целевой программы базовых задач мы не добиваемся. И понятно почему.

Потому что до сих пор у нас не сведены в единую сеть информационные ресурсы различных органов и уровней власти и управления. У нас до сих пор при реализации государственной функции у граждан нет достаточной информации в электронном виде. До сих пор граждане для того, чтобы получить какие-то справки, согласования и прочие документы и бумажки, должны отстоять огромную очередь к чиновникам.

И что касается экономической сферы деятельности - мы только-только начинаем переходить к электронным торгам. Кстати говоря, об этом говорили так же на совещании в Торгово-промышленной палате.

Сегодняшняя наша встреча посвящена анализу того, что происходит по этому направлению. Это тем более актуально, что нам предстоит разработать новую программу - “Электронное Правительство” до 2015 года. В условиях экономического и финансового кризиса это тем более важно, поскольку внедрение соответствующих инструментов позволит нам более эффективно распорядиться государственными ресурсами и сделать нашу деятельность более эффективной.

—-

Собственно что можно почерпнуть из этого короткого текста:

1. Фактически программу “Электронную Россию” заменяют на “Электронное правительство”. Явные отличия пока ещё не видны, но уверен что будут.

2. Сведение информационных ресурсов в единую сеть - это может означать продолжение построения ФИЦ (Федерального Информационного Центра) в той или иной форме. Вопрос лишь в какой, но на него ответы будут известны позже.

3. По поводу того что у граждан нет достаточной информации, то странно почему напрямую не упоминаются госуслуги, а упоминается именно нет достаточной информации. Хорошо бы чтобы это был намёк на появление data.gov.ru, но скорее похоже на неточную терминологию.

4. По поводу электронных торгов. Выражу непопулярное мнение - не помогут. Во всяком случае в том виде как это планируются сейчас, с акцентом на процедуры размещения заказов, а не контролем подготовки закупок и контроля результатов.

5. Весьма интересен состав участников - несмотря на то что в последний месяц в СМИ активно прочили уход Щеголева, он там присутствовал, а вот Набиуллиной на этой встрече небыло, что опять на водит на размышления кто-же и как будет курировать “Электронное правительство”.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Демократизация данных
21 мая 09 10:49

В блоге Обамы появилась запись Democratizing Data -  где описано ничто иное как анонс data.gov

Этот анонс давно ожидался, и вот время настало и открытые данные стали неотъемлимой частью информационного присутствия государства в сети (в США).

Обратите также внимание на наличие ссылки - Suggest Dataset

Про то что в России необходим аналогичный проект (data.gov.ru) я уже писал ранее. Пока же его нет продолжает развиваться проект OpenGovData.ru

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Автоматическая классификация сайтов: возможные подходы
20 мая 09 04:11

Ранее я упоминал про недавнее исследование из Яндекса - Автоматическая классификация веб сайтов (в PDF) и что лично я несогласен с подходом использующим классификацию по ключевым словам.  Главное - это то что у Яндекса как и других поисковых систем, на самом деле, куда больше информации о сайтах, пользователях и их взаимодействии чем просто страницы и ключевые слова. Этой информации столь много - что принцип “больше данных, проще алгоритмы” должен подходить здесь на 100% и я опишу несколько вариантов классификации сайтов построенных именно на таких данных.

1. Классификация по аудитории

Ключевые слова на сайте - суть отражение его содержания, для понимания каждой из тематических областей необходимо формировать набор ключевых слов и выражений специфичных для этой области. С другой стороны для практически каждого человека работающего в сети и вообще справедливо то что он обладает ограниченным число тем в которые ему интересны.  Отсюда и аудитории  тематически близких сайтов пересекаются, порой значительно.  Если мы знаем на какие сайты (темы) заходил пользователь ранее и если можем получить оценки проведённого им на этих сайтах времени, то собрав агреггированную статистику мы можем предполагать темы других сайтов.

В случае Яндекса задача сбора информации об аудитории сложной быть не должна поскольку в качестве эталонной выборки сайтов могут использоваться сайты внесённые в Яндекс.Каталог, а для определения посетителя показы рекламы в Директе.

Таким образом как раз у Яндекса есть возможность определения тематики сайта по аудитории.

Ограничения этого подхода в том что для отслеживания аудитории необходим свой счетчик (или рекламный блок) на анализируемом сайте.

2. Классификация по карте объектов сайта

Карта объектов - это совокупность смысловых и структурных объектов (обладающих собственным значением или связанными со смысловыми понятиями элементов сайта).

Приведу несколько примеров элементов объектной разметки:

- новостная лента как частный случай списка включающего даты, который является частным случаем списка в принципе

- табличные данные

- навигационное меню сайта

- счетчики

- рекламные блоки

плюс множество других объектов.

Каждый объект обладает собственными свойствами, отношениями к другим объектам и, в некоторых случаях, веб ресурсам.

При классификации сайта, из карты объектов извлекаются необходимые для классификации характеристики и уже на их основе работает алгоритм классификации.

На основе упрощённой версии именно такого подхода работает мой алгоритм определения коммерциализованности сайта.

Лично я считаю именно этот подход наиболее переспективным.

3. Классификация по входящим и исходящим ссылкам

Это довольно простая классификация - анализ входящих и исходящих ссылок на ресурсы на которые ссылается анализируемый сайт и ссылки с внешних сайтов. По сути это почти тематическое цитирование, но адаптированное под классификацию, а не под ранжирование.

4. Классификация по интересам владельцев сайтов

Это один из “рунетоспецифичных подходов” которые можно отнести к экзотическим, но, тем не менее. Чаще всего создатели и владельцы сайтов придерживаются определённых тем в своих работах. Издательские дома делают сайты по книгам и газетам, квасные фабрики - про квас, финансисты - про финансы и так далее.

Анализируя WHOIS данные, мы можем делать предположения о тематике веб сайта на основе ранее классифицированных сайтов того же владельца.

5. Классификация по социальным закладкам

В отличии от классических каталогов сайтов в социальных закладках в разы больше ссылок на самые разные ресурсы. Мы можем провести классификацию сайта агреггируя тэги социальных закладок с различных сайтов социальных закладок и проводить классификацию даже без построения bag-of-words (набора слов) с анализируемых страниц на сайте. В этом подходе мы возвращаемся к ключевым словам, но он доступен не только крупным поисковым системам, но и условно простым пользователям

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Ссылки: Алгоритмы и массивы данных
19 мая 09 10:57
  • MNIST dataset of handwritten digits - большой массив данных (датасет) написанных вручную цифр и сравнений алгоритма по их идентификации
  • NEC Animal Dataset - датасет изображений фигурок животных в разных позах и ракурсах.
  • ManyEyes Datasets - подборка датасетов от IBM ManyEyes
  • «Автоматическая классификация web-сайтов» PDF - исследование из Яндекса по классификации веб сайтов по ключевым словам. Лично я несогласен что классификация по ключевым словам достаточна для тематической классификации и у Яндекса гораздо больше массивов данных чтобы такую классификацию обеспечить. В любом случае почитать рекомендую.
  • Swine Flu Dataset - датасет особенно актуальный, с данными по гриппу H1N1 (свиной грипп)
  • International Crisis Behavior Dataset (1918-2001) - данные по кризисам за указанные годы в формате SPSS
  • Federal Reserve Economic Data - датасеты по экономической активности на сайта резервного банка Сент-Луиса

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Postedfrom Иван Бегтин | 0 Comments    
Ближайшие личные планы
18 мая 09 03:20

На днях мне говорили что в кризис это нестандартное решение, но с 21 числа я покидаю число наёмных работников.  Делаю это по собственной инициативе и главная причина в том что считаю что любая работа - это в первую очередь созидательная деятельность или лишь во вторую заработок денег только ради самих денег.

Выходить куда-либо на работу на полную ставку, пока, если честно желание у меня небольшое. С этим не спешу и не загадываю.

В ближайшее время буду заниматься образованием, самообразованием, собственными проектами и контракными заказами по извлечению/обработке/классификации и анализу данных - благо они есть.

Из тем госзакупок и e-Gov я не исчезаю, хотя и буду уделять им чуть меньшее внимание чем ранее.

OpenGovData.ru продолжит наполняться данными, как я и обещал до конца мая будет обновление разделов.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Министерство Энергетики, банки изображений и TinEye
15 мая 09 05:18

Захожу я сегодня на новый сайт Министерства Энергетики, а поскольку я обычно просматриваю интересные сайты полностью хотя бы уровня до второго - вдруг что интересное, то и тут посмотрел внимательнее.

Про 8-ФЗ на этот раз не буду, они там даже ссылку на него разместили и это правильно.

Я на сей раз о другом, простом, но режущем глаза наблюдении.

В нескольких (не менее 3-х разделах) там ничто иное как типовые картинки из банков фотографий. Может быть не самых популярных банков изображений, но тем не менее факт имеет место быть.

Приведу конкретные примеры:

Наверное где-то и в других разделах есть.

Проверял я понятное дело не сайт МинЭнерго, а TinEye. Всё подыскивал под него какой-либо новый сайт где гарантированно контент был бы “новым”.

Лично меня работа их алгоритма впечатлила - находятся даже изменённые изображения в разных форматах и размерах.

Такие дела.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Postedfrom Иван Бегтин | 0 Comments    
Filed under: ,
Ссылки и документы: Анализ доклада ИНСОР и аналитическая записка Счетной Палаты
15 мая 09 02:39

Хочу порекомендовать к прочтению Экспресс-анализ доклада ИНСОРа о «развитии электронного правительства в Российской Федерации» проведённый Виктором Гридиным и комментарии Екатерины Аксеновой в gov-gov.ru по рейтингу государственных сайтов.

От себя я добавлю что любой доклад, любой рейтинг или отчёт всегда вызывает недоверие при отсутствии данных на основе которых он строился. Это можно сказать и про доклад ИНСОР - в нем нет ни первичных данных, ни методики.

В принципе, я лично считаю что любая работа нацеленная на социальную, а не на PR составляющую должна содержать открытые методики и возможность независимого воспроизведения результатов.

—-

Плюс дам ссылку на ещё один аналитический документ о котором я писал ранее и всё ждал когда жеСчетная Палата опубликует его у себя на сайте. Это аналитическая записка по результатам экспертно-аналитического мероприятия “Комплексный анализ эффективности функционирования существующей системы закупок для государственных нужд” документ можно посмотреть тут - http://www.ach.gov.ru/userfiles/bulletins/10-buleten_doc_files-fl-1750.pdf

Я уже и не ожидал что этот документ будет доступен - учитывая что прошло уже 9 месяцев со времени проведения коллегии 4 июля 2008 года, ан нет, вот и он.

Там присутствует много терминологии знакомой, в основном, тем кто работает с госзакупками, но даже не зная её можно убедится в том насколько мнение СП и МЭР с ФАС на госзакупки отличаются друг от друга.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Инструменты работы с данными. Мысли и наблюдения
15 мая 09 11:13

В последнее время много времени уделяю различным инструментам работы с информацией - очистка, обработка, конвертация, визуализация и всё что с этим связано. Общее число инструментов весьма велико, как и число их возможных применений.

Просуммирую собственные размышления:

  • большая часть инструментов работы с большими массивами информации написаны на Java. То же самое можно сказать про инструменты работы с semantic web. Может быть это именно мне попадались подобные, но думаю что действительно пока инструментов в Java больше.
  • Язык R (R Language) впечатляет удобством и всё более идёи в массы, например, лично мне нравится возможность вызова его через код Python посредством rPy (http://rpy.sourceforge.net/).  Один лишь недостаток - язык под GPL и использовать его в коммерческих продуктах не получится. Но коммерческие продукты - это не всё и я уже знаю несколько примеров (вне России) где R используют внутри компаний или же как аутсорсинг услуг.
  • большая часть задач по визуализации решается теми или иными плагинами для Excel, а также непосредственно возможностями Excel’я особенно версии 2007. Единственной более менее серьёзной заменой ему я знаю Tableau цена которого нереально выше - минимум $999 за персональную лицензию.
  • весьма примечателен выбор графика в JuiceAnalytics там можно подобрать график под свои нужды и сразу скачать его под Excel или Powerpoint.
  • а вот в для веб пока ничего более простого и удобного чем Amcharts (http://www.amcharts.com/) мне найти не удалось. При очень небольшой цене - весьма удобный и гибкий инструмент. Впрочем есть и бесплатные варианты вроде OpenFlashChart, бесплатной версии FusionCharts и Yahoo ASTRA Flash Components.
  • есть целый ряд тем по обработке данных отодвинутых от наиболее продвинутых инструментов. Например, есть пробел с извлечением метаданных из различного рода файлов - фактически, за исключением самых популярных форматов,  в остальном под каждый формат свои библиотеки и инструменты зачастую только с закрытым исходным кодом или даже полное отсутствие описания формата. Правда относительно форматов файлов и их пакетной обработки надо отметить что у разных форматов разная судьба - если изображения, видео, музыку и различного рода текстовые файлы часто подвергают пакетной обработке, то для остального рода файлов знание их форматов ограничено узкой областью использующих их продуктов, антивирусов и разного рода security and forensic Software. Определённо можно свести эти темы воедино, вопрос в том лишь дорос ли рынок до такого объединения и будет ли это востребованно именно сейчас.
  • Hadoop + HBase или альтернативы в виде Hypertable позволяют выходить на уровень BigData и работать с данными уже на принципиально ином уровне.  В англоязычном Интернете уже развиваются курсы по Hadoop, Hadoop Boot Camp и масса энтузиастов в России всё упирается в небольшие объёмы общедоступных массивов данных и ограниченностью предприятий/организаций заинтересованных в работе с большими объёмами.
  • тема которая не относится к работе с данными напрямую, но важна с точки зрения их потребления, предоставления конечным пользователям - это формы предоставления информации. Её можно начинать от динамических контролов в веб и на десктопе которые бы подстараивались под вкладываемые в них данные в зависимости от объёма, продолжать автоматизированным и автоматическим подбором типов графиков под анализируемые данные и развивать к другим не менее интересным направлениям. Всё это в совокупности некий “мостик” между работой с данными, в том числе и BigData, и юзабилити. И пока я не вижу как иначе эти темы связать.
  • продолжаю присматриваться к GreenPlum, пока на уровне понимания кейсов для чего может пригодится.
  • то что крупные игроки вроде Microsoft, Google, Amazon начинают не просто работать с большими объёмами данных, но и предоставлять общедоступные данные всем желающим - это очень хороший сигнал. Хотя и каждый из них играет в свою игру, тем не менее появление лоббистов в этой области даёт шанс что они начнут взаимодействовать непосредственно с государственными органами для раскрытия информации. К сожалению, не российскими госудраственными органами.
  • у меня накопилось порядка 200 гигабайт различных датасетов, при том что приходится себя ограничивать в скачке некоторых чтобы не забивать канал и потому как надо ещё и эти “переварить”.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Semantic Web for Dummies (Семантический Веб для Тупых)
15 мая 09 10:08

На Амазоне вышла книжка Semantic Web for Dummies написанная Jeffry Pollock автором Adaptive Information (Адаптивная информация)  которая меня лично подвигла ко многим размышлениям на тему природы и свойств информации, равно как и её самоценности. Я лично пока полистал то что можно посмотреть в открытом доступе и, хотя книжка для “Dummies”, интересного там должно быть много.

Кстати, Adaptive Information доступна и в книжках Google, хотя и не полностью, но достаточно для ознакомления.

Жаль в России книг по природе информации (не по алгоритмам или управлению знаниями), но именно по информации очень мало.

А эти книжки я лично добавил в свой список заказов на Amazon’е.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Postedfrom Иван Бегтин | 4 Comments    
Filed under: ,
Про Минкомсвязи - верить ли СМИ?
12 мая 09 01:48

Regnum.ru неожиданно разродился короткой статьей что Минкомсвязи может быть расформировано. (http://www.regnum.ru/news/1161978.html)

О том же, комментариями, пишет Катерина Аксенова в gov-gov.ru (http://gov-gov.ru/?p=321)

У меня, признаться, совсем нет уверенности что это действительно так и будет, более того есть уверенность что практически любое российское ведомство можно расформировать под тем или иным предлогом. Было бы желание.

У меня ощущение - странная статья. Точно также когда-то пророчили что Минэкономразвития разделят на несколько ведомств, а реально это вылилось только в передачу торговли МинПромТоргу.

В общем не вижу причин пока этому верить.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Ссылки. Открытые данные в мире
10 мая 09 11:41
  • Microsoft инциировали Open Government Data Initiative http://www.microsoft.com/industry/government/opengovdata/default.aspx где они собирают открытые данные, пока исключительно из США, на своей платформе. Инициатива интересная, жаль лишь что охватывает только GSA (General Services Administration) и Округ Колумбия.
  • Data Catalog Distict of Columbia (http://data.octo.dc.gov/) открытые данные публикуемые округом Колумбия. Я упоминал их и и ранее и этот проект достоин внимания.
  • Открытые данные сената штата New York - http://www.nysenate.gov/open-data

Особенность в том что пока ещё до понятия открытых данных развились только системы в США, в остальных странах, даже обычно довольно продвинутых, пока ещё прогресс невелик.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

OpenGovData. Спецификации раскрытия данных
09 мая 09 10:16

Продолжая тему открытых данных и OpenGovData.ru проект продолжает развитие маленькими, очень маленькими, но верными шагами. Сейчас я предлагаю к обсуждению спецификацию и принципы раскрытия информации плюс непосредственно пару массивов опубликованных по этой спецификации.

Скажу заранее - подготовка спецификаций и продумывание способов работы с данными проходили по принципу упрощения всего что только возможно и не вредит конечному результату. Определённым источником вдохновения была спецификация sitemaps которую не так давно начали использовать поисковые системы.

 

Спецификации

Итак, спецификация раскрытия данных, состоит из 3-х XSD схем:

И, для каждой из схем, доступна автоматически созданная документация:

 

 

Процесс импорта и экспорта данных

Теперь подробнее о том как с этими спецификациями будет происходить работа.

Фактически, вариантов работы с информацией два:

1. Данные подготовленные и загруженные на сайт opengovdata.ru

2. Общедоступные данные публикуемые на внешних ресурсах.

В первом случае описание источника данных производится внутри системы opengovdata.ru - технически это веб движок в котором можно заполнить все необходимые поля по данному источнику данных/массиву данных и который в итоге сформирует спецификацию источника в файла opendata.xml и присвоит зарегистрированному массиву данных постоянную ссылку permalink. Сами данные предварительно загружаются на сервер через HTTP/FTP/SFTP соответстветственно. 

Во втором случае данные источником данных является некий веб-сайт, например, если государственный орган или коммерческая компания желает сделать какие-либо свои данные общедоступными, то они подготавливают описание источника данных в виде файла opendata.xml с описанием массива и предоставляют его по некой постоянной ссылке на своём ресурсе. После чего регистрируют ссылку на описание источника данных на opengovdata.ru на специальной странице с указанием дублировать информацию или нет.

Если при регистрации источника данных указывается необходимость дублировать информацию, то все данные копируются на opengovdata.ru и раз в сутки, при необходимости, синхронизируются при том что эталонным источником данных остаётся внешний сайт. Если дублирования информации не происходит, а это может быть в случае если, например, объёмы данных очень велики, то синхронизируется только описание источника данных и присвоение ему постоянной ссылки в opengovdata.ru, а сами данные остаются на оригинальном сайте.

Все данные которые зарегистрированы в opengovdata.ru будут доступны для поиска по их описанию через в веб интерфейс, а в будущем и для поиска по самим данным.

Применение спецификаций

В сценариях работы системы выше у каждой спецификации есть своя роль.

  • opendata.xsd - используется для описания массива данных, включая описание полей, описание источника данных, описание организации ведущей данный источник информации, непосредственно сами данные или же ссылки на них. При этом данные могут предоставляться двумя способами:
    • включенными в описание массива данных - в этом случае данные описаны согласно спецификации в тэге table;
    • внешними источниками - в этом случае данные представлены в форматах: openDataXML, TSV, CSV, YAML, DBF и находятся во внешних файлах которые обнаружаемы по внешним ссылкам. Ссылки обязательно сопровождаются указанием типа данных и хэша рассчитанного по алгоритму SHA-512. Файлы данных могут также быть сжатыми с помощью Gzip - это должно определяться наличием у них расширения .gz (это сделано по аналогии со сжатием файлов sitemaps).
  • opendataxml.xsd - используется для унифицированного описания любых плоских табличных данных. Данный формат сознательно сделан предельно упрощённым и не несёт ничего кроме перечесления рядов таблицы и столбцов по каждому ряду. Фактически - это замена TSV формата, которая может быть удобна для некоторых систем которым из XML импортировать данные проще.  Цель этого формата представления данных не полнота описания, а унификация и простота последующей обработки.
  • opendataindex.xsd - используется для автоматизированной публикации открытых данных в виде индекса ресурсами готовыми их предоставлять. Например, сайт раскрывающий более одной базы данных может создавать сайт opendataindex.xml который, в свою очередь, зарегистрировать на сайте opengovdata.ru и при появлении новых массивов данных, они будут подтягиваться автоматически. В дальнейшем применение индекса открытых данных может быть через robots.txt (по аналогии с sitemaps) или же за счёт фиксированного имени файла в корне сайта, например, такого http://sitename.ru/opendataindex.xml 

Обновление информации в источниках

Данные представленные в описании массива данных (opendata.xml) могут присутствовать в двух формах:

 

  • статические неизменные данные
  • пополняемые данные.

 

Статические данные - это, фактически, данные которые уже собраны, зафиксированы и уже не будут меняться или пополняться. Например, к ним можно отнести какие-либо статистические данные за какой-либо уже прошедший временной период, а также редко изменяемые справочники по которым необходимо получать их последнюю редакцию, а не прошедшии версии.  При описании данных в спецификации opendata для статических данных используется тип full  в тэге tableref.

Пополняемые данные - это данные которые подвержены периодическому обновлению, ежедневному, еженедельному, по иному графику или по событию. К пополняемым данным можно отнести, например, статистические данные в развитии текущего периода или же данные реестров. 

В opendata для пополняемых данные используется указание типа initial в тэге tableref при первоначальной загрузке информации и при последующих обновлениях тип указывается в update, а также в атрибуте updateid  - указывается число возрастающее на единицу с каждым последующим обновлением. 

 

Особенности и ограничения

Все текущие спецификации и способы работы с данными были сознательно сделаны со множеством ограничений и не учитывают множества вариантов представления данных. 

Например, пока отсутствует возможность структурированного описания доступных веб сервисов и не табличных, а иерархических данных которые не укладываются в текущую простую форму описания. Сейчас, единственное что сделано в спецификациях отражающее такие случаи - это возможность указания нестандарных спецификаций во внешних файлах. Для этого предусмотрен специальный тэг specref в котором указывается ссылка на спецификацию которая может быть хоть описанием в виде документа, а в поле format тэга tableref указывается тип документа отличный от TSV, openDataXML и так далее. 

Также остаётся открытым вопрос как обеспечить унифицированное описание изменений в данных и их удаление и сейчас это отдаётся на откуп конечным системам потребителям данных. Несмотря на то что есть множество способов фиксации подобных изменений - от регистрации каждого изменения, до  псевдоязыка обновления данных, тем не менее вопрос как это сделать просто является открытым.

Готовые данные

Несколько первых, тестовых, но рабочих, массивов данных уже готовы по этим спецификациям.

Также эти данные перечислены в индексном файле http://export.opengovdata.ru/opendataindex.xml

Разумеется, эти данные только начало, и далее они будут появлятся в структурированной форме в разделе сайта http://opengovdata.ru/opendata/ 

Текущий статус спецификаций и данных

Проект сейчас идёт маленькими шажками и цель спецификаций и первых размещаемых массивов не в том чтобы охватить все возможные случаи и все возможные типы структур данных, а в том чтобы начать эту работу, итеративно усложняя и развивая данные. 

Как можно помочь проекту?

Многие задают вопрос как можно помочь проекту, я перечислю многие возможные способы:

1. Можно подготавливать данные по спецификациям и направлять их на публикацию в OpenGovData. Это можно сделать, например, через сообщество в Google Groups - http://groups.google.com/group/opengovdataru.

2. Можно участвовать в обсуждении спецификаций, выступая с конструктивными критикой и предложениями по развитию стандартов. Со временем я надеюсь что описания будут детализированы и представлены в виде более подробного документа чем то что я описываю сейчас.

3. Для государственных органов и других владельцев общедоступных данных можно начать публиковать данные на государственных сайтах в форматах и, далее, регистрировать массивы данных в реестре данных opengovdata.ru . 

4. На законодательном уровне - проведение в Российское законодательство нормы по обязательному наличию структурированного описания в случае любых требований по публичности размещаемых данных. Я объективно понимаю что это займёт годы, но если этого не делать, то не годы, а десятилетия.

5. Сейчас я ищу для проекта финансирование так чтобы была возможность заниматься им не по нескольку часов в неделю, а полноценно - если такое финансирование появится, то и разработка стандартов и скорость подготовки новых массивов данных сильно возрастут.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Исправление опечаток. Совокупность подходов
04 мая 09 04:09

Я ранее немало писал про исправление опечаток в нескольких заметках, например, можно прочитать здесь по ссылкам про исследования которыми я занимался.

Сейчас же я размышляю над тем как результаты использовать в других задачах или же зафиксировать их в виде продукта или сервиса и изложу ряд взаимосвязанных подходов к исправлению к которым я пришёл. Постараюсь излагать, по возможности, без терминологии и формул в форме свободного текста размышлений.

1. “Подбор ключей”

Это, собственно, предельно простой подход  основанный на том что расстояние Левенштейна между словами a  и b обладает зависимостью от значений расстояния Левенштейна между словами b и c. Подробное описание присутствует в заметке Решение с расчетом расстояния Левенштейна для исправления опечаток 

Такой подход позволяет сократить число сравнений от 2 до 10 раз. Если, к примеру, есть словарь в 100 000 слов и ищем опечатку в слове в 10 знаков, то максимальное число сравнений для расстояния Левенштейна равное 1 будет равно числу слов с  длиной в 9, 10, 11 знаков - в нашем случае суммарно 39161 слов. За счёт фильтра их число сокращается от 3000 до 10000 сравнений. Что всё ещё очень много и сильно зависит от того какое слово рассматривается и насколько оно близко к используемым ключам. 

Основной недостаток этого подхода - слабая предсказуемость и значительные объёмы индексов.

2. Зависимость от производных метрик

Расширим рассмотренный свыше подход.

Предположим что у нас есть функция позволяющая извлечь из слова некую статичную метрику, которая при сравнении с метрикой другого слова даёт численное значение обладающего зависимостью от расстояния Левенштейна между этими словами.

Иными словами нам необходимо создать фильтр по некому простому производному из рассматриваемого слова для быстрого фильтра по базе слов в словаре. При этом есть 

Пройдя чуть далее - можно прийти к выводу что производных может быть много больше и они могут составлять один или несколько взаимосвязанных индексов. Например, в своих исследованиях я применял именно такой подход - итеративно перебирая различные метрики и способы их получения. 

Это позволяет обеспечить лучшую фильтрацию и сократить число сравнений от 10 до 20 раз. То есть, фактически, для примера выше, этот фильтр оставляет лишь от 1500 до 3000 слов в выборке с которыми уже необходимо сравнивать искомое слово. 

3. Ветвление алгоритма  и использование слов выборки из словаря как ключевых слов.

При сравнении слова с опечаткой со словами из выборки слов у нас всегда имеется дополнительная метрика - результат расчета расстояния Левенштейна между этими словами. 

За счет построения индекса который бы охватывал все слова из выборки и ключевые значения при расчете расстояния Левенштейна - число сравнение можно сократить, как минимум, в 2-3 раза.

Ограничения этого подхода в использовании статической выборки и в том что всегда будут слова не попадающие в фильтр и проходящие всю цепочку сравнений. 

Подход потребует длительного расчета расстояния Левенштейна между всеми словами выборки, но это будет не более чем однократной операцией.

Лично я именно этот подход так и не реализовывал до конца, в первую очередь из за необходимости проведения длительных расчётов, особенно для больших словарей.  Конечно Hadoop и прочие инструменты позволяют эту задачу ускорить, но и в этом случае - предварительная подготовка данных ресурсоёмка.

4. Разбор структуры слова и алгоритма

Подробнее о таком подходе я писал здесь.

Собственно тот способ который я использую сейчас - все варианты преобразований слова укладывающиеся в расстояние Левенштейна равное 1 группируются суммарно в около 15 правил для каждого из которых рассчитывается своя статическая метрика однократно по словам в словаре и для каждого слова на проверку. Далее по этим метрикам производится выборка вариантов с совпадающими метриками). 

Плюс подхода в том что фильтрация позволяет сократить размер выборки в тысячи раз. Например, поиск по слову “автомобилъ” (последняя буква заменена на твердый знак) по словарю в 108 000 слов даёт выборку в 29 слов, поиск по слову “алексанндр” (лишняя буква “н” в середине) даёт выборку в 19 слов. 

Для сравнения выборка для слова “алексанндр” по словарю в 5 004 923 слов состоит из 1755 слов, а для слова “автомобилъ” на том же словаре выборка состоит из 1031 слова. 

Цена столь сильного сокращения выборки в сложности построения запросов - сейчас лично использую для этой задачи SQL сервер и это куда медленнее чем если создать свою структуру под хранение словаря с индексами и постоянно держать её в памяти. 

Можно обратить внимание что размер выборки практически растёт в соответствии с ростом словаря, но, за счёт того что фильтр изначально отсеивает до 99.9% слов, то основные временные затраты приходятся на получение выборки, а не на расчёт расстояния Левенштейна к словам в ней. Кроме того, за счёт усложнения фильтра возможно и последующее сокращение выборок в 2-3 раза вопрос лишь в подборе баланса временных затрат на фильтрацию и на последующие сравнения.

Кросспост из Иван Бегтин. Комментарии можно оставлять здесь или здесь.

Postedfrom Иван Бегтин | 0 Comments    
Filed under:

This Blog

Tags

Archives

Syndication