استفاده از نظریه مجموعه های ناهموار در انتخاب شبکه خوشه نقطه ای و رودخانه

چکیده

در این مقاله، مجموعه‌های ناهموار را به خوشه نقطه و انتخاب شبکه رودخانه اعمال کردیم. به منظور برآورده کردن الزامات مجموعه‌های ناهموار، ابتدا اطلاعات مکانی اشیاء را با بدنه محدب، شبکه نامنظم مثلثی (TIN)، نمودار ورونوی و غیره ساختاری و کمی می‌کنیم. دوم، ما به صورت دستی ویژگی های تصمیم گیری را با توجه به ویژگی های شرطی به جدول اطلاعات اختصاص می دهیم. در انجام این کار، اطلاعات مکانی و اطلاعات ویژگی‌ها با هم ادغام می‌شوند تا اهمیت نقاط و رودخانه‌ها توسط نظریه مجموعه‌های ناهموار ارزیابی شود. در نهایت خوشه نقطه و شبکه رودخانه را به صورت پیش رونده انتخاب می کنیم. نتایج تجربی نشان می دهد که روش ما معتبر و موثر است. در مقایسه با کارهای قبلی،

واژه‌های کلیدی: نظریه مجموعه‌های ناهموار، تعمیم نقشه، خوشه نقطه، شبکه رودخانه، انتخاب پیشرو

1. مقدمه

نقطه و خط دو شی رایج برای نشان دادن ویژگی‌ها و پدیده‌های فضایی روی نقشه هستند، به عنوان مثال ما از نقاط برای نشان دادن روستا در نقشه مقیاس کوچک، نقطه علایق (POI) نتایج جستجو در نقشه‌برداری وب یا موبایل استفاده می‌کنیم. ما همچنین خطوطی را برای نشان دادن جاده، رودخانه و همچنین مرز منطقه در تقریباً همه نقشه ها به کار می گیریم. به طور کلی، نقشه ها در مقیاس های مختلف برای اهداف خاص تولید می شوند. یکی از مهم‌ترین تکنیک‌های تبدیل مقیاس، انتخاب است که می‌توان از آن برای کاهش پیچیدگی محتوای نقشه، تأکید بر پدیده‌های جالب و حذف جزئیات بی‌اهمیت با حفظ روابط هندسی و توپولوژیکی بین اشیاء استفاده کرد. دستیابی به داده های جغرافیایی بسیار ساده تر از گذشته است. به ویژه هنگامی که اطلاعات ویژگی به طور فزاینده ای در دسترس می شود. این تغییر به انتخاب شی مفهوم گسترده‌تری می‌دهد – ما باید نه تنها ویژگی‌های فضایی اشیاء، بلکه اطلاعات ویژگی‌ها را در طول فرآیند نیز در نظر بگیریم. در حال حاضر، بیشتر روش‌های انتخاب شی صرفاً اطلاعات ویژگی را در نظر می‌گیرند. با توجه به این موضوع، ما یک روش جدید برای استفاده از مجموعه‌های خشن برای ترکیب اطلاعات فضایی و ویژگی‌ها با هم برای ارزیابی اهمیت اشیاء فضایی برای انتخاب تدریجی پیشنهاد کردیم.

مجموعه‌های خشن توسط Z. Pawlak در دهه 1990 پیشنهاد شد که می‌تواند داده‌های ناقص و نادرست را بدون تکیه بر دانش پیشینی مدیریت کند. در سال‌های اخیر، برخی از محققین سعی کرده‌اند مجموعه‌های خشن را برای تعمیم نقشه‌کشی به کار ببرند. سونگ و همکاران [ 1 ] از کاهش ویژگی برای استخراج دانش انتخاب شبکه رودخانه استفاده کرد. لی و همکاران [ 2 ] – [ 4] روشی بر اساس مجموعه ناهموار برای تعمیم خوشه نقطه و همچنین شبکه رودخانه پیشنهاد کرد. با این حال، محدودیت‌هایی در روش آن‌ها وجود دارد، به‌ویژه برای اعمال مجموعه تقریبی در جدول اطلاعات ویژگی‌های غیر تصمیم‌گیری. کار ما با این دو متفاوت است، ما یک استراتژی برای اختصاص ویژگی تصمیم‌گیری برای جدول اطلاعات پیشنهاد می‌کنیم و از وابستگی ویژگی‌ها در مجموعه‌های ناهموار برای ارزیابی اهمیت اشیاء فضایی برای انتخاب پیشرو استفاده می‌کنیم.

بقیه مقاله به شرح زیر سازماندهی شده است: بخش 2 کار مرتبط را بررسی می کند. بخش 3 ایده اصلی انتخاب شیء بر اساس نظریه مجموعه های خشن را تشریح می کند. بخش 4 آزمایش های خوشه نقطه و انتخاب شبکه رودخانه را ارائه می کند. و بخش 5 کاربرد آتی روش ما را مورد بحث قرار می دهد.

2. کارهای مرتبط

تحقیق در مورد انتخاب شی نقطه و خط در تعمیم نقشه سابقه طولانی دارد که از نقشه کاغذی سنتی گرفته تا نقشه الکترونیکی در دستگاه تلفن همراه و وب را شامل می شود. Yan و Weibel [ 5 ] از نمودار Voronoi برای انتخاب خوشه نقطه استفاده می کنند. در روش خود، آنها معادله ای را با در نظر گرفتن اهمیت موضوعی و همچنین چگالی محلی برای ارزیابی امکان انتخاب ساختند. متأسفانه این روش توانایی تعیین وزن این دو نوع عامل را ندارد. Cai و Guo [ 6 ] شبکه Kohonen را برای اجرای انتخاب مجموعه نقاط معرفی کردند. این روش می‌تواند ویژگی توزیع نقاط را حفظ کند، اما اطلاعات ویژگی را در نظر نمی‌گیرد. دی برگ و همکاران [ 7] روشی را برای ساده‌سازی نقشه‌های نقطه‌ای پیشنهاد کرد. آنها با به کارگیری مفهوم ” تقریبا” مشکل را رسمی کردند – نقشه نقطه درشت را از نقشه خوب استخراج کردند. و سپس می توانند تقریب های خوبی از نقشه های مشتق شده و منبع را با یک روش اکتشافی محاسبه کنند. این رویکرد را می توان در نقشه با مقدار زیادی از نقاط اعمال کرد در حالی که فقط اطلاعات هندسی را در نظر گرفت. بروتر و همکاران [ 8 ] [ 9] مفهوم تعمیم بلادرنگ را برای نقاط روی دستگاه تلفن همراه پیشنهاد کرد. آنها از چهار درخت برای مدیریت نقاط با “ساختار زیربخش سلسله مراتبی” و “سطوح پیشروی جزئیات” استفاده می کنند. آنها با استفاده از شاخص‌های چهاردرخت به عنوان داده‌های کمکی، الگوریتم‌های انتخاب، ساده‌سازی، تجمع و جابجایی نقاط را اصلاح کردند. روش آنها عمدتاً بر کارایی و ویژگی توزیع نقاط تمرکز دارد. صرفاً با در نظر گرفتن اطلاعات ویژگی.

همچنین رویکردهای زیادی در رابطه با انتخاب رودخانه ایجاد شده است. آی و همکاران [ 10 ] [ 11 ] با استفاده از نمودار Voronoi الگوریتمی را برای محاسبه حوضه آبریز شبکه هیدروگرافی و استفاده از مساحت حوضه به عنوان عامل اصلی برای ارزیابی اهمیت رودخانه ها پیاده سازی کرد، اما نتایج تجربی رضایت بخش نیست. باتنفیلد و همکاران [ 12 ] – [ 14] یک روش سری برای تعمیم مجموعه داده های هیدروگرافیک ملی (NHD) پیشنهاد کرد. رویکردهای آنها داده های هیدروگرافی را با در نظر گرفتن عوامل جغرافیایی – زمین و آب و هوا، که شامل کوهستانی، تپه ای یا مسطح، و خشک یا مرطوب است، طبقه بندی می کند. سپس، با توجه به ویژگی انواع مختلف داده‌های هیدروگرافی، محقق می‌تواند توالی پردازش و همچنین پارامترهای الگوریتم‌ها را برای تولید نسخه درشت داده‌های هیدروگرافی دقیق تنظیم کند. نتایج تعمیم هیدروگرافی بر اساس این روش کاملاً مؤثر است. سن و همکاران [ 15 ] [ 16] روشی مبتنی بر خوشه‌بندی k-means و نقشه‌های خود سازماندهی (SOM) برای اجرای تعمیم داده‌های هیدروگرافی ارائه کرد. این روش از مزیتی برخوردار است که به طور مستقیم اطلاعات معنایی را در نظر می گیرد.

علاوه بر تمرکز عمده بر اطلاعات هندسی و اطلاعات توپولوژیکی، برخی از تحقیقات در مورد تعمیم شبکه رودخانه به اطلاعات موضوعی نیز می پردازند. داهیندن و سستر [ 17 ] روشی را برای انتخاب شبکه رودخانه بر اساس اهمیت آن توسعه دادند. اما اهمیت رودخانه ها با ویژگی های هندسی یا توپولوژیکی تعیین نمی شود. در واقع با “واقعیت و فراوانی استفاده از آنها” مرتبط است. نتیجه تعمیم این روش پایدار نیست، که به شدت به اطلاعات جمع‌سپاری – داده‌های موجود در مخازن عمومی و پارامترهای رویکرد ارزیابی مرتبط است. تینکر و همکاران [ 18 ] همچنین یک تعمیم هیدروگرافی را بر اساس اطلاعات موضوعی – میانگین بارندگی سالانه محلی – اجرا می کند.

از آنجایی که امروزه اطلاعات موضوعی بسیار آسان‌تر به دست می‌آیند، ما نیاز به توسعه ابزارهایی برای تعمیم نقشه داریم که بتواند اطلاعات مکانی (ویژگی هندسی، توپولوژیکی) و اطلاعات ویژگی (داده‌های موضوعی، معنایی) را به طور همزمان مدیریت کند. در این مقاله، یک روش انتخاب بر اساس مجموعه‌های خشن پیشنهاد می‌کنیم. روش ما می تواند اطلاعات مکانی را یکپارچه کند و اطلاعات را با هم نسبت دهد تا اهمیت شی فضایی را که معیار انتخاب شی است ارزیابی کند. علاوه بر این، ما فرآیند انتخاب را به روشی پیشرونده انجام می دهیم تا ثبات توزیع اشیاء فضایی را حفظ کنیم.

3. انتخاب اشیا بر اساس نظریه مجموعه های خشن

انتخاب اشیاء نقطه ای و خطی بر اساس اهمیت آنهاست که با اطلاعات مکانی و اطلاعات ویژگی ارزیابی می شود. ایده اصلی استفاده از نظریه مجموعه‌های خشن برای محاسبه اهمیت اشیاء مکانی، یافتن وابستگی بین ویژگی‌ها است. بنابراین، مفاهیم نظریه مجموعه‌های خشن را معرفی می‌کنیم، سپس روش ساخت جدول اطلاعات را ترسیم می‌کنیم و الگوریتم انتخاب پیشرونده را پیشنهاد می‌کنیم.

3.1. مفاهیم اولیه ست های خشن

با توجه به [ 19 ]، “نقطه شروع نظریه مجموعه های خشن، رابطه غیر قابل تشخیص است که توسط اطلاعات مربوط به اشیاء مورد علاقه ایجاد می شود”. رابطه تشخیص ناپذیری به عنوان یک جدول اطلاعاتی (که سیستم اطلاعاتی یا جدول ویژگی-مقدار نیز نامیده می شود) در نظریه مجموعه های خشن تعریف می شود. یک مدل از جدول اطلاعات را می توان به صورت زیر تعریف کرد : مجموعه محدودی از اجسام به نام جهان کجاست . مجموعه‌ای محدود از ویژگی‌ها است که در آن و زیر مجموعه ویژگی‌های شرطی و زیرمجموعه ویژگی تصمیم‌گیری هستند. برای هر ویژگی

، تابعی برای تعیین مقدار برای است. یک رابطه غیر قابل تشخیص ، که در آن

، است . به طور خلاصه ، خانواده همه غیر قابل تشخیص است. یکی دیگر از مسائل مهم در تجزیه و تحلیل داده ها، کشف وابستگی بین ویژگی ها است.

[ 19 ] . برای زیرمجموعه ها و ، اگر ، سپس به درجه k0 k 1 بستگی دارد . POS _C (D) ناحیه مثبت U/D نسبت به C است که شامل تمام عناصر U است که می توانند به طور منحصر به فرد به بلوک های U طبقه بندی شوند. /D توسط زیر مجموعه C.

جدول 1 را به عنوان تصویر در نظر بگیرید، شش نهاد گنجانده شده است. صفات شرطی و صفت تصمیمی به صورت جداگانه هستند. طبق تعاریف فوق U/C = {{e ₁ }, {e ₂ }, {e ₃ }, {e ₄ }, {e ₅ }, {e ₆ }} و U/D = {{e ₁ , e ₄ , e ₅ }, {e ₂ , e ₃ , e ₆ }}. بگذارید زیر مجموعه P = {c ₁ , c ₂ }، سپس U/P = {{e ₁ , e ₂ , e ₃ }, {e ₄, e ₆ }, {e ₅ }}. در این مورد، می‌توانیم نتیجه بگیریم که POS _C (D) = 6، و POS _P (D) = 1، که می‌توان اینطور تفسیر کرد که همه عناصر U را می‌توان به‌طور منحصربه‌فرد به پارتیشن U/D با استفاده از C طبقه‌بندی کرد. در حالی که تنها 1 را می توان با استفاده از P طبقه بندی کرد. سپس ویژگی تصمیمی d کاملاً به مجموعه ویژگی C بستگی دارد و 1/6 به مجموعه ویژگی P بستگی دارد. برای هر ویژگی ، اهمیت c _i برای ویژگی تصمیمی D می تواند تعریف شود. بنابراین، اهمیت c 3 ₁ – 1/6 = 5/6 است. یعنی بدون ویژگی c ₃ ، تنها 1/6 عنصر در U را می توان به درستی طبقه بندی کرد، سپس اهمیت ویژگی c ₃5/6 است.

با استفاده از وابستگی صفات، اگر بتوانیم یک جدول اطلاعاتی برای اشیاء فضایی که قرار است انتخاب شوند بسازیم، می‌توانیم اهمیت هر ویژگی شرطی را محاسبه کنیم.

3.2. ساخت جدول اطلاعات

اطلاعات ویژگی همیشه می تواند به راحتی به شاخص های کمی تبدیل شود. در حالی که گاهی اوقات نمی توان اطلاعات مکانی را مستقیماً به دست آورد، برای استخراج آن نیاز به ساختارسازی داریم. ساختاربندی اشیاء فضایی به معنای شناخت و کمیت کردن روابط توپولوژیکی بین اشیاء و ویژگی های توزیع فضایی اشیاء است. روش‌های زیادی برای ساختاربندی اشیاء نقشه وجود دارد، مانند بدنه محدب [ 20 ]، TIN محدود [ 21 ]، نمودار Voronoi [ 22 ] و غیره.

3.2.1. ساختاربندی خوشه نقطه ای

توزیع هتل یک شهر را در شکل 1(a) به عنوان مثال در نظر بگیرید. تمام داده های آزمایش ما داده های برداری هستند که می توانند در هر مقیاسی نمایش داده شوند. ابتدا، سطح تودرتوی بدنه محدب ساخته شده است که در شکل 1(b) نشان داده شده است . این اطلاعات می تواند ساختار مرزی نقاط را نشان دهد زیرا نقاط روی مرز تأثیر بیشتری بر ساختار کلی نسبت به نقاط داخلی دارند. دوم، نمودار ورونوی، که به صورت شکل 1(c) نشان داده شده است، برای نشان دادن حوزه محبت هر نقطه استفاده می شود. هر چه مساحت بزرگتر باشد، نقطه اهمیت بیشتری پیدا می کند. سوم، چگالی محلی، نشان داده شده به عنوان منطقه خاکستری شکل 1(c)و معادله (1) را می توان از نمودار ورونوی به دست آورد. هرچه چگالی محلی کمتر باشد، فرصت های بیشتری برای حفظ امتیاز در طول انتخاب وجود دارد.

.(1)

که در آن D _i چگالی محلی نقطه i است، S _i ناحیه ورونوی نقطه i، m تعداد همسایگان نقطه i، و S _k ناحیه ورونوی نقطه همسایه نقطه i است.

علاوه بر این، ما رابطه بین جاده و نقطه را که در شکل 1(d) نشان داده شده است، در نظر می گیریم . اقامت در هتل در نزدیکی جاده اصلی برای مسافران راحت تر است. سپس ترجیح می‌دهیم نقطه را نزدیک به جاده اصلی حفظ کنیم. با استفاده از این روش‌ها، می‌توانیم اطلاعات فضایی خوشه نقطه را کمی کنیم – مرز و درون نقاط را با سطح بدنه محدب، حوزه محبت و تراکم محلی توسط ورونوی نشان دهیم. منطقه، و مکان بر اساس فاصله تا جاده.

3.2.2. ساختاری سازی شبکه رودخانه

الگوی شبکه رودخانه پیچیده تر از خوشه نقطه است. در این مقاله، ما بر شبکه رودخانه درخت مانند که از یک رودخانه تنه و چند شاخه فرعی تشکیل شده است، تمرکز می کنیم. شکل 2(الف) نمونه ای از شبکه رودخانه ای است که از 14 رودخانه تشکیل شده است. رودخانه آبی 1 جریان اصلی است و دیگران به آن وارد می کنند.

ابتدا باید طول هر رودخانه برای ارزیابی اهمیت رودخانه ها در نظر گرفته شود. رودخانه های طولانی همیشه به عنوان اسکلت هندسی شبکه در نظر گرفته می شوند. دوم، ما از کد هورتون [ 23 ] به عنوان درجه برای نشان دادن رابطه سلسله مراتبی بین رودخانه ها استفاده می کنیم، که به صورت شکل 2(a) نشان داده شده است. هیچ رودخانه ای به رودخانه های با درجه 1 وارد نمی شود. رودخانه های قرمز با درجه 2، رودخانه های با درجه 1 را مستقیماً وارد می کنند. و رودخانه آبی با بیشترین درجه دارای رودخانه های زیادی با درجه 2 است که به طور مستقیم وارد شده است. ما نمی‌توانستیم رودخانه را قبل از اینکه آن رودخانه‌هایی که مستقیماً به آن وارد می‌شوند حذف شوند، حذف کنیم. سوم، سطح رودخانه های نشان داده شده در شکل 2(c)برای نشان دادن ساختار درخت مانند رودخانه ها در این مقاله استفاده شده است. سطح بسیار شبیه درخت دودویی است، هر گره حداکثر دارای دو گره فرزند است که به‌عنوان «چپ» و «راست» متمایز می‌شوند، و گره‌های دارای فرزند، گره‌های والد هستند. در شبکه رودخانه، برای هر رودخانه، شاخه های سمت چپ به عنوان گره سمت چپ و شاخه های راست، گره سمت راست در نظر گرفته می شوند. رودخانه ها در یک گره خواهر و برادر یکدیگر هستند. به عنوان مثال، در این شبکه رودخانه، رودخانه 4، 9، 12 خواهر و برادر یکدیگر هستند، رودخانه 1 والد مشترک این رودخانه ها است و رودخانه 4 دارای فرزند چپ رودخانه 5، رودخانه فرزند سمت راست 6 است. حذف رودخانه. با تراز بالاتر احتمال تخریب ساختار درخت مانند بیشتر از حذف رودخانه ای با سطح پایین تر است. سپس ترجیح می دهیم رودخانه هایی با تراز بالا را انتخاب کنیم. چهارم، حوضه آبریز رودخانه ها [11 ]، که در شکل 2(b) نشان داده شده است، به عنوان یک شاخص نیز استفاده شده است. ما از نمودار Voronoi رودخانه‌ها که توسط TIN تولید می‌شوند برای تقسیم فضا استفاده می‌کنیم و منطقه Voronoi را به عنوان حوضه آبریز رودخانه در نظر می‌گیریم. علاوه بر این، حوضه آبریز رودخانه مادر مالک تمام حوضه آبریز فرزندان خود است. این شاخص یک شاخص ترکیبی است که می تواند نه تنها رابطه سلسله مراتبی بین رودخانه ها، بلکه فواصل و تراکم محلی آنها را نیز نشان دهد. علاوه بر این، ما یک شاخص دیگر – یک متریک مکان – برای منعکس کردن مکان رودخانه‌های مربوط به والدینشان در ساختار درخت مانند معرفی می‌کنیم. شاخص به صورت معادله (2) نشان داده شده است.

.(2)

که در آن L _i متریک مکان رودخانه i، L طول والد رودخانه i، و n مقدار سیب رودخانه i است.

در درخت می زند طبق این تعریف، رودخانه هایی که برای هر یک خواهر و برادر هستند، متریک مکان یکسانی دارند. این شاخص به صورت زیر تفسیر می‌شود: اگر دو رودخانه از طرف‌های مختلف پدر و مادر یکسانی وارد کنند، رودخانه با خواهر و برادر کمتر مهم‌تر از رودخانه دیگر با خواهر و برادر بیشتر بدون توجه به همه شاخص‌های دیگر است.

با ساختاری‌سازی شبکه رودخانه، می‌توانیم اطلاعات فضایی شبکه رودخانه را به چند پارامتر کمیت کنیم – ساختار درخت مانند را با کد هورتون (درجه) و سطح درخت، حوضه آبریز (یا حوزه محبت) بر اساس منطقه Voronoi، و مکان بر اساس متریک مکان

3.2.3. جدول اطلاعات نقاط و رودخانه ها

پس از ساختاربندی، می توانیم جدول اطلاعات را به صورت جدول 2 و جدول 3 با افزودن اطلاعات ویژگی بسازیم. در جدول 2 ، “درجه” و “تعداد اتاق” اطلاعات ویژگی هتل ها هستند. درجه نشان دهنده سطح ستاره هتل است. این نیز یک شاخص ترکیبی است که به صورت دستی با توجه به امکانات، خدمات، مدیریت و دیگران تولید می شود. ما می توانیم این شاخص را از طریق اینترنت دریافت کنیم. علاوه بر این، تعداد اتاق ها می تواند مقیاس هتل را بلافاصله منعکس کند. در جدول 3، ما هیچ اطلاعات ویژگی اضافی به این جدول اضافه نکردیم. به این دلیل که اطلاعات ویژگی رودخانه ها به راحتی قابل دستیابی نیست. اما می‌توانیم چنین اطلاعاتی را در صورت موجود بودن، مانند بارش حوضه، به جدول اضافه کنیم.

با توجه به مجموعه‌های خشن، برای محاسبه اهمیت ویژگی‌های شرطی، باید یک ویژگی تصمیم‌گیری در نظر گرفته شود. در مورد انتخاب شیء فضایی، تصمیم بر این است که کدام اشیاء حذف و کدام یک انتخاب شوند. اما در جدول 2 و